たのしくbit全探索: 競プロ典型 90 問 002 - Encyclopedia of Parentheses(★3)
問題
解説
正整数Nが与えられるので,長さがNの正しく整合している括弧列をすべて出力する問題です.
ここでの整合とは左括弧と右括弧が正しく対応していることです.
OK ( ( ) ( ) ) , ( ( ) ( ( ) ( ) ) ) ( ),
NG ( ( ), ( ) ), ) ( ( ) ),
最も高速なアルゴリズムを設計するのはなかなか難しそうですが,今回の問題はNの最大値が20であるため,全探索ができそうです*1.
今回は左括弧と右括弧の2通りと見ることができるため,bit全探索が使えます.
bit全探索は0と1からなる要素数がNの配列を全列挙することで組合せをすべて作る手法です.入力の要素数が少ないときに有効です.
要素3の例 [ 000 ⇒ 001 ⇒ 010 ⇒ 011 ⇒ 100 ⇒ 101 ⇒ 110 ⇒ 111 ]
今回長さNの文字列を作るため,全探索の数としては2Nになります.0から2N - 1までの全通りを2進数表記にすることでN文字のそれぞれの括弧を左括弧にするか右括弧にするか決定します.
0なら左括弧,1なら右括弧と見立てて,生成された組合せが正しく整合しているか確認します.
確かめるために用いる変数vを0で初期化します.bit列を前から見ていき,0なら+1,1なら-1します.
次のいずれかに当てはまる場合,そのbit列は正しく整合していないです.
- ループの途中で変数vが負になる.
- ループが終了したときに,v = 0ではない.
これに当てはまらなかったbit列を括弧に直して出力します.
簡単な動作例
N = 4
組合せの数は24 = 16
- [0 ⇒ 0000] ⇒ 2.に当てはまるため正しくないです.
- [1 ⇒ 0001] ⇒ 2.に当てはまるため正しくないです.
- [2 ⇒ 0010] ⇒ 2.に当てはまるため正しくないです.
- [3 ⇒ 0011] ⇒ 正しいです. ⇒ ( ( ) )
- [4 ⇒ 0100] ⇒ 2.に当てはまるため正しくないです.
- [5 ⇒ 0101] ⇒ 正しいです. ⇒ ( ) ( )
- [6 ⇒ 0110] ⇒ 1.に当てはまるため正しくないです.
- [7 ⇒ 0111] ⇒ 1.に当てはまるため正しくないです.
- [8 ⇒ 1000] ⇒ 1.に当てはまるため正しくないです.
- [9 ⇒ 1001] ⇒ 1.に当てはまるため正しくないです.
- [10 ⇒ 1010] ⇒ 1.に当てはまるため正しくないです.
- [11 ⇒ 1011] ⇒ 1.に当てはまるため正しくないです.
- [12 ⇒ 1100] ⇒ 1.に当てはまるため正しくないです.
- [13 ⇒ 1101] ⇒ 1.に当てはまるため正しくないです.
- [14 ⇒ 1110] ⇒ 1.に当てはまるため正しくないです.
- [15 ⇒ 1111] ⇒ 1.に当てはまるため正しくないです.
ソースコード例(C++)
*1:220 = 1048576で,判定がO(N)であれば十分現代のコンピュータで2秒以内に計算できそうと予想できます.現代のコンピュータは1秒でおおよそ1億ステップ計算できると考えて良いです