概要
- 対応の取れた括弧は何パターンあるか
- ()()()
- ((()))
- など
解法
- 各位置にどちらの括弧を置くか全パターン生成してからチェックする
- またはカタラン数
- 青チャート1Aにも載ってた
桁あふれに注意
- N=13の場合 26! を計算するが桁あふれする
- 13!なら収まる
- 先に約分して分子が大きくなりすぎないようにする必要があった
// Nが小さい時用。大きい時はnCrバージョンを探してください ll catalan_number(ll N){ ll answer = 1; FOR(i, N+2, 2*N+1){ answer *= i; } FOR(i, 1, N+1){ answer /= i; } return answer; }
参考書
- マスターオブ場合の数 p82
追記:2021/06/14
- カタラン数、出た!
- E - White and Black Balls https://atcoder.jp/contests/abc205/tasks/abc205_e