AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。
今回は、競プロ典型90問の002 - Encyclopedia of Parentheses(★3)を解きました。
途中 if
文が長くなってしまいました。もっとスマートに書く方法はないでしょうか...。
長さ N のカッコ列のうち、正しいカッコ列(全ての括弧が対応している)を辞書順に列挙する問題です。今回の場合、N の最大値は 20 なので全パターン列挙しても 2^20 となり、全探索が可能です。提出コードのうち、カッコ列を全列挙する部分が以下のプログラムとなります。
最後の出力は for
式の戻り値の ()
なので気にしないでください。ビットシフト と ビット論理積 を利用しています。
次に if
文にて、カッコ列が正しいカッコ列かどうかを判別しています。正しいカッコ列の条件は
'('
)と終わり(')'
)が同じ数'('
の数」<「')'
の数」となるケースが1回もないとなります。
最後に、正しいカッコ列を辞書順にソートして出力すれば解答となります。
python では itertools.product('()', repeat=n)
のようにすれば辞書順に列挙してくれるのですが、rust ではそのようなスマートな書き方はないのか気になります。
itertools.product('()', repeat=n)
の rust バージョンを考えてみました。multi_cartesian_product()
を利用すると良さそうです。