No.790 ちきんの括弧並べ
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 164
作問者 :
severrabaen
/ テスター :
Kuske
タグ : / 解いたユーザー数 164
作問者 :
severrabaen
/ テスター :
Kuske
問題文最終更新日: 2019-02-21 18:49:18
問題文
ちきんは'('の文字を$N$個、')'の文字も$N$個持っています('は文字に含まれません)。ちきんはこの2種類の文字を全て使用した対応の取れた括弧列が全部で何通り作れるか知りたくなりました。ただし、対応の取れた括弧列とは問題文末尾の定義を満たしている必要があります。ちきんの代わりに全部で何通りの対応の取れた括弧列が作れるかを出力してあげてください。
定義:
・空文字列は正しい括弧列の条件を満たす。
・文字列$s$が正しい括弧列の条件を満たすなら、($s$)は正しい括弧列である。
・文字列$s$と$t$がどちらも正しい括弧列の条件を満たすなら、$s$と$t$を連結した文字列は正しい括弧列である。
入力
$N$
1行目にちきんが所持している括弧の個数$N(1 \le N \le 13)$が与えられます。
出力
対応の取れた括弧列の個数を出力し、最後に改行してください。
サンプル
サンプル1
入力
2
出力
2
(())、()()の２通りのみが対応の取れた括弧列です。例えば、())(は括弧が完全には閉じられていないので対応の取れた括弧列ではありません。
サンプル2
入力
3
出力
5
((()))、()()()、()(())、(())()、(()())の5つが条件を満たします。例えば、())(()はダメです。定義を満たしていません。
なお、3番目と4番目は違う文字列としてカウントされることに注意してください。
サンプル3
入力
11
出力
58786
多いですね。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。