Magicode logo
Magicode
1

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() を利用すると良さそうです。


Discussion

コメントにはログインが必要です。