問題
競プロ典型90問 002 Encyclopedia of Parentheses
解法
以下の2つを主に考えてコードを書きました。
- 再起関数を使い長さNになるまで文字を追加していく。
- 正しいカッコ列の条件を外れた場合、文字を追加しない。
正しいカッコ列の条件
まず、正しいカッコ列の条件を考えたところ、以下の2つになりました。
- カッコ列を左から見て行った時に
")"の数が"("を超えないこと。 - カッコ列の
"("の数と")"の数が等しいこと。
ここで長さNのカッコ列を全探索して、全てにおいて上記の判定をしても良いのですが、大変そうだなぁと思ったのでもう少し考えてみました。
2の条件から以下の2つがわかります。
- Nが奇数の場合正しいカッコ列は存在しないこと。
- カッコ列を左から見て行った時に
"("の数がN//2を超えないこと。
ということで、空の文字列から1文字ずつ追加してカッコ列を作る際に、以下の2つを条件判定しながら追加していけば正しいカッコ列が作れるのではないかと思いました。
-
"("を追加する際は"("の数がN//2を超えないこと。 -
")"を追加する際は")"の数が"("の数を超えないこと。
再起関数
上の条件がわかったところで再起関数を使えばあとは簡単にコードが書けるのではないかと思いました。
再起関数とは、「ある関数の中で自分自身を呼び出す関数」のことです。
例
N = int(input())
def saiki(i):
if i == 1:
return 1
else:
return saiki(i-1)*i
print(saiki(N))
ソース
今回カッコ列の1つ目は必ず"("であるため、呼び出す際に引数に"("を渡しています。
また、最後は必ず")"であるため、作っている文字列の長さがN-1になった時点で最後に")"を追加して出力しています。
N = int(input())
if N%2 == 1:
print()
exit()
def addChar(str,numL,numR):
if numL+numR == N-1:
print(str+")")
return
else:
if numL < N/2:
addChar(str+"(",numL+1,numR)
if numL - numR >0:
addChar(str+")",numL,numR+1)
addChar("(",1,0)
最後に
公式の解法を見るとbit全探索で解けると書いてあり、全然違う方針でした。
bit全探索自体は調べてみてかなり有効な方法だと思ったのでまた勉強して、この問題もその通り書いてみようかなと思います。
今回は問題自体の難易度がそこまで高くなかったこともあり、プログラム自体は割とすんなりかけたと思います。(最初少し迷走して不安でしたが)
それだけに今回は記事を書いている時間の方がかなり長くなってしまいました。
もう少し記事の方もすんなり書けるようになればと思っているのですが、こっちはプログラミングと違って考え方が分かればすんなり書けるようになると言ったものでもなくて難しいですね。「ここの記述はいらない」や逆に「ここをもう少し詳しく書いた方が良い」などあれば参考にさせていただきますのでコメントお願いします。
以上、拙い記事ではありますが何かの参考になれば幸いです。
最後まで読んでいただきありがとうございました。