yukicoder No.790 ちきんの括弧並べ 解説記事
問題概要
'('と')'の2種類の文字がN個ずつある。全部の文字を使用して対応の取れた括弧列は何通り作れるか。対応の取れた括弧列の定義については問題文参照。
writer、tester解は以下の3つです(他の解き方は特に考えていませんがあるかもしれませんね(普通にありそう(ありますね(提出一覧を見た))))。僕はDPをあまり書かない人間なのでDPは想定解ではありません(暴論)。普通にACできますけどね。
解法1
bit全探索をします。こっちは大半の人が取る解き方だと予想しています*1。今回登場する文字は2種類だけなので、bitの0='('、1=')'とそれぞれ置いてやればよいです。対応の取れた括弧列になるための条件は文字列全体を見た時に、'('の数が')'の数と同じであり、なおかつ、左端から任意の箇所までを取り出した時に'('の数が')'の数以上であるという条件を満たさないといけないのでそれを判定してやる必要があります。これをbitのループの所で判定して、満たさないなら即breakをすることで間に合います。
gist1004856ef1f44a8100b76ff406eed9d7
解法2
カタラン数を使います。プロの方は何も見なくてもこれが思いつくのでしょうか?僕はウィキペディアを見て知りました。
ここにそのまま書いてありますが、カタラン数のN項目が今回の答えです。ただし、ウィキペディアにはカタラン数の一般項が書いてありますが、これをそのまま計算しようとすると、(2N)!がオーバーフローする場合があるため、式変形が必要です(Pythonとかで殴れば大丈夫ですかね?僕はC++erなので式変形します)。式変形すると、下のようになります。
後はこれを求めるだけです。何も見ないでこのやり方で解く人は果たして現れるのか...?(追記:これで通している人を発見しました。数学のプロだなあと思いました。もしかして常識だったりしますか？)
gist6f96e9e2395e4c2273d4f8a9f287c395
解法3
テスターのKuskeガチプロ(@SpidCorCandy)が通した解法です。再帰で通している。やっぱりプロだなあ(は？)*2。これに関しては、掲載許可を得ているとは言っても*3、他人のコードなので今までみたいに逐一コメントを付していません。ご了承ください。
gist98afc076a12bc483340af7659afb5f98
余談
初めての作問で疲れました*4。最後に、解いてくださった方へ。解いてくださってありがとうございました!
