概要
競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。
※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）
問題002-Encyclopedia of Parentheses
問題概要
長さNの「正しい」カッコ列を辞書順で出力する。
正しいとは、
- ()のペアが揃っている。
- 右から見て行った時に、"("より")"の方が多くなってはいけない
- ()以外の文字列が含まれてはいけない
制約
1 <= N <= 20 \\
Nは整数
解き方
Nが小さく、文字列のシンプルさから、工夫して全探索で求められそう。
一応、同じものを含んだ並び替えで全パターン列挙することも考えたが、パターンが最大で $20!$ となってしまうため、
しんどそう。（厳密には、$20!/(10!*10!)$）
そこで今回は、
- "(" を1, ")" を0とみなして、ビット全探索
- １で出てきた文字列において "(" より先に ")" が多く出現しないか確認
といった流れで実装していく。
１に関して、0か1かの２通り × N文字 なので、$O(2^N)$の計算量。
（ビット全探索に関してはこちら）
2に関して、N文字を左から検索するだけなので、$O(N)$。
2^Nのパターンにおいて、N回の検索を行うので、
合計で$O(N*2^N)$。これは、10^7のオーダーになるので、十分に間に合う。
引用元：競プロ典型90問 Github
実装
answer.py
# 入力の受け取り
N = int(input())
# カッコ列を格納する配列
pare = []
# ビット全探索
for i in range(1 << N):
# 1の時 "(" を、0の時 ")" を文字列に追加していく
l = ""
for j in range(N):
if i >> j & 1:
l += "("
else:
l += ")"
# 文字列の長さがNの時のみ、左から検索する。その時cntで"("と")"の出現回数を計算する。cntが0より小さくならなかった＋cntが0(出現回数が等しかった)文字列のみをpareに格納する
if len(l) == N:
cnt = 0
flag = True
for k in range(N):
if l[k] == "(":
cnt += 1
else:
cnt -= 1
if cnt < 0:
flag = False
if flag and cnt == 0:
pare.append(l)
# pareを辞書順にソート、順番に出力する
pare.sort()
for i in range(len(pare)):
print(pare[i])
※ちなみに、上記のコードは、Pythonで提出するとTLEになり、pypyだとACになります。
やたらと長い配列や再起関数を用いる場合を除いては、pypyの方が基本的に早いので、提出はpypyがおすすめです。
参考記事
最後に
問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
ここまでお読みいただきありがとうございました。