002 - Encyclopedia of Parentheses
AtCoderの問題をPythonで解いてみた。
ただし、DPについてはまだ学習中のため使えていないのでご容赦を。
（コメントでDPを使った解法をご教示頂けますと幸いです。）
問題は下記リンクから参照してください。
https://atcoder.jp/contests/typical90/tasks/typical90_b
Step1 Bit全探索を用いて実装
ここでのポイントはBit全探索を用いるときに、どこまで探索すれば良いかということです。 Nはかっこ『(』、『)』の数を表しているため、N=4の場合『(』or『)』の数が4つになります。『(』、『)』を2進数で表していきますが、今回は『(』=0、『)』=1とします。
N桁の2進数全パターンを用いるため、2^N個のパターンが必要になります。
ex.) N = 4の場合
2^4 = 16パターンとなります。
2^Nの実装はこんな感じです。（bitに変換した値を配列やらなんやらに入れて使ってください）
for i in range(2**N):
bit = format(i, f'0{num}b')
0パッディング記法（0埋め）で使いたいため、文字列になっています。
Step2 制約のおさらい
制約として、)()(や))((などは正くないカッコ列となります。
つまり、先頭が『)』で始まるものは最初からパターンとして除くことができます。
（末尾が『)』のものも対象外となりますが、後ほど）
つまり、再度N=4のパターンで見ると、以下の赤枠部分が対象外となります。
そうなるとStep1で計算した2^Nのパターンは2^N-1個になります。
2^N-1 は 2^n/2（全パターンを半分にする）でもOKですが、2^N-1の方が個人的にスマートかなと思います。あと感覚的に2^N-1の方が計算速度早そう...
また、(()や())みたいな『(』と『)』の数が一致していない場合も正くないカッコ列となります。
Nが奇数の場合は早期リターンしましょう。
『(』と『)』の数が一致していない場合だと赤枠が対象外となります。
つまり最終的に残るのは以下の2つとなります。
出力結果
(())
()()
Step3 必要条件
N=4ではたまたまStep2までで解くことができましたが、N=6の場合だと(』と『)』の数は一致するが、こんなパターンが存在してしまいます。
・())(()
・(()))(
・()())(
・())()(
・()))((
Step2でちらっと、末尾が『)』のものも対象外となりますが、後ほど と記載をしましたが、末尾が『)』となるものは削除しましょう。すると以下の１パターンだけ残ります。
・())(()
一見正しそうにも見えますが、かっこの閉じ方がおかしいです。
見やすいように(と{を使い分けてみます。すると、
()}{()
}{の部分がおかしいことが分かります。
つまり、これがおきないようにするためには、『(』と『)』を左から順番に連結させていく際に、ある連結時点で『(』の数より『)』が大きくなってはなりません。
これを先ほどの『(』と『)』の数が一致するかのチェック処理と合わせて実装するとこんな感じ。
# 0と1の数が一致する かつ 0 1を連結する時点iで、0の個数 >= 1の個数が必ず成り立つ
def check_validity(str):
zero_cnt = 0
one_cnt = 0
is_midway_verification = True # 0の個数 >= 1の個数のチェック用フラグ
for s in str:
if int(s) == 0:
zero_cnt += 1
else:
one_cnt += 1
if zero_cnt < one_cnt:
is_midway_verification = False
break
# 1の個数が0の個数を超えることがある場合
if not is_midway_verification:
return False
return zero_cnt == one_cnt and str[len(str)-1] == '1'
このStep1〜3により、対象外をすべて除去することができます。
コード全部
N = 6
def calc():
if N % 2 == 1: # 奇数の場合は早期リターン（何も出力しない）
return
for s in convert_bit_split_arr(int(N)):
output_str = s.replace('0', '(').replace('1', ')')
print(output_str)
def convert_bit_split_arr(n):
ret_arr = []
for i in range(2**(n-1)):
str = format(i, f'0{n}b')
if check_validity(str):
ret_arr.append(str)
return ret_arr
def check_validity(str):
zero_cnt = 0
one_cnt = 0
is_midway_verification = True
for s in str:
if int(s) == 0:
zero_cnt += 1
else:
one_cnt += 1
if zero_cnt < one_cnt:
is_midway_verification = False
break
if not is_midway_verification:
return False
return zero_cnt == one_cnt and str[len(str)-1] == '1'
calc()