Rustの勉強ログ　競プロ典型90問をRustで説いてみる　その3　002 Encyclopedia of Parentheses

# はじめに

最近はクソコードや他のプロジェクトに興味ややる気を持っていかれることが多くて、なかなか手が出せていなかった競プロの勉強を久々に再開してみる。
今回の対象は[002 Encyclopedia of Parentheses](https://atcoder.jp/contests/typical90/tasks/typical90_b)。

# 問題の考え方

N = 20で各文字の考えられる可能性は2通りだからbit探索で良い…かもしれないが、もう少しスマートに、深さ優先の全探索ができそうだ。

正しいカッコ列は必ず、左からK文字とったときに開きカッコ"("の数は閉じカッコ")"の数と同じか多くなる。
そのため、文字数の制限がなければ開きカッコの数が閉じカッコの数より多い場合、K+1文字目はどちらのカッコも適正で、
両方同じ数の場合、K+1文字目は開きカッコ固定になる。

これを満たしたまま深さ優先探索を行い、開きカッコで終わる文字列が優先的に処理されるようにすれば、
求める回答が得られそうだ。

# 回答用コード

<details><summary>長いため折りたたみ</summary><div>

```rust
use std::io;
use std::collections::VecDeque;

fn main() {
    let n : i8 = read_i8();

    if n % 2 == 1 {
        return;
    }

    let mut q: VecDeque<AnswerLine> = VecDeque::new();

    let start : AnswerLine = AnswerLine{
        max_size: n,
        lines: vec![BracketType::Start]
    };

    q.push_back(start);

    // 深さ優先の全探索
    while q.len() > 0 {
        let next_item = q.pop_back().unwrap();
        for item in next_item.get_next_gen(){
            q.push_back(item);
        }
    }

}

fn read_i8() -> i8{
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();

    input.trim().parse().unwrap()
}

enum BracketType{
    Start,
    End
}

impl Clone for BracketType{
    fn clone(&self) -> BracketType{
        match self{
            BracketType::Start => BracketType::Start,
            BracketType::End => BracketType::End
        }
    }
}

impl BracketType{
    fn as_i8(&self) -> i8{
        match self{
            BracketType::Start => 1,
            BracketType::End => -1
        }
    }

    fn to_char(&self) -> char{
        match self{
            BracketType::Start => '(',
            BracketType::End => ')'
        }
    }
}

struct AnswerLine{
    max_size: i8,
    lines: Vec<BracketType>
}

impl Clone for AnswerLine{
    fn clone(&self) -> AnswerLine{
        AnswerLine{
            max_size:self.max_size,
            lines:self.lines.clone()
        }
    }
}

impl AnswerLine{
    fn allowed_end_blancket(&self) -> i8{
        self.lines.iter().map(|x| x.as_i8()).sum()
    }

    fn can_push_end_brancket(&self) -> bool{
        self.allowed_end_blancket() > 0
    }

    fn can_push(&self) -> bool{
        self.max_size as usize > self.lines.len() + self.allowed_end_blancket() as usize
    }
    
    fn to_string(&self) -> String{
        let mut result : String = self.lines.iter().map(|x| x.to_char()).collect();
        result = format!("{}{}", result, ")".repeat(self.max_size as usize - result.chars().count()));
        return result;
    }

    fn get_next_gen(&self) -> Vec<AnswerLine>{
        let mut result = Vec::new();

        if self.can_push(){
            // 辞書順：(が先にスタックから出るように(で終わる方を後ろに回す
            if self.can_push_end_brancket(){
                let mut next_end_item = self.clone();

                next_end_item.lines.push(BracketType::End);

                result.push(next_end_item);
            }
            
            let mut next_start_item = self.clone();
            next_start_item.lines.push(BracketType::Start);
            result.push(next_start_item)
        }else{
            println!("{}",self.to_string());
        }

        return result;
    }

}
```
</div>
</details>

# 今回の習得ポイント

## 構造体の扱い方

Rustの場合、データはすべて構造体にまとめて、それにimplブロックを紐付ける形でメソッドを追加していくようだ。
implブロックは同じ構造体にたくさん紐付けられるため、必要に応じて機能を追加できる、つまり最低限の機能だけ有効化できるのがポイントなのかな。

今回はスタックから一つポップする→コピーしてスタックにプッシュするを繰り返すので、コピー用のトレイト(Clone)も実装したが…実質インタフェースっぽいしおいておくか。

## 列挙体の扱い方

今までC#やJavaなどの列挙体しか扱ってきてなかったから躓いてるポイント。
構造体と同じく、下記のimplブロックのようにメソッドを実装できるのは良いのだが、
列挙体をコピーする場合はきちんとそれ用の処理を実装しなければ行けないようだ。

C#とは使い方が違いすぎるからこの差は覚えるしかなさそうだ。

```rust
impl BracketType{
    fn as_i8(&self) -> i8{
        match self{
            BracketType::Start => 1,
            BracketType::End => -1
        }
    }
}

impl Clone for BracketType{
    fn clone(&self) -> BracketType{
        match self{
            BracketType::Start => BracketType::Start,
            BracketType::End => BracketType::End
        }
    }
}
```