カタラン数〜括弧の対応のパターン〜

カタラン数 yukicoder

概要

  • 対応の取れた括弧は何パターンあるか
    • ()()()
    • ((()))
    • など

解法

  • 各位置にどちらの括弧を置くか全パターン生成してからチェックする
  • またはカタラン数
    • 青チャート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

マスター・オブ・場合の数―大学への数学 (分野別重点シリーズ (2))

マスター・オブ・場合の数―大学への数学 (分野別重点シリーズ (2))

Amazon

追記：2021/06/14