RustとAtCoderを勉強する(typical90_b)

はじめに

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 ではそのようなスマートな書き方はないのか気になります。

追記（2022/5/5）

itertools.product('()', repeat=n) の rust バージョンを考えてみました。multi_cartesian_product() を利用すると良さそうです。