C++でN本の交差しない弦を使って円を分割する方法の数を数える

問題概要

整数 N が入力として与えられます。これは、円周上に 2×N 個の端点があるときに引く弦（chord）の本数を表します。目的は、どの弦も互いに交差しないように、これらの弦を使って円を分割する方法の数を数えることです。

例えば N=3 の場合、円周上の点は 6 個になります。3 本の弦を引く 1 つの方法は、1−2、3−4、5−6 を結ぶものです。

その他の引き方は以下のとおりです。

1−6, 2−5, 3−4
1−2, 3−6, 4−5
1−4, 2−3, 5−6
1−6, 2−3, 4−5

合計で 5 通りあります。

入力例と出力例

例 1

入力：

N=4

出力：

Count of ways to divide circle using N non-intersecting chords are: 14

説明： 円周上には合計 8 個の点があります。最初の弦を 1 本引くと、残りの点は 2 つの集合に分けられます。異なる集合に属する点同士を結ぶ弦を引くと、最初の弦と必ず交差してしまうため、そのような弦は引けません。

例 2

入力：

N=6

出力：

Count of ways to divide circle using N non-intersecting chords are: 132

説明： 円周上には合計 12 個の点があり、考え方は例 1 と同じです。

解法のアプローチ

このアプローチでは、すでに求めた小さなケースの答えを利用して全体の答えを組み立てる動的計画法を使います。2 点間に弦を 1 本引くと、残りの点は 2 つの集合（set1 と set2）に分けられます。この 2 つの集合にまたがる点同士の間に弦を引くと最初の弦と交差してしまうため、各集合の内部だけで独立に弦を引くことになります。

• 整数 N を入力として受け取ります。
• 関数 divide_circle(int N) は、N 本の交差しない弦で円を分割する方法の数を返します。
• 点の総数は total_points = 2×N です。
• 方法の数を格納する配列 total_cuts[] を用意します。
• 点が 0 個または 2 個の場合、弦の引き方は 1 通りだけなので、total_cuts[0] と total_cuts[2] を 1 で初期化します。
• 点数が 4 以上の場合、total_cuts[i] には「j 個の点での方法数」と「残り i−2−j 個の点での方法数」の積を、j を 2 ずつ増やしながらすべて加算していきます。
• つまり total_cuts[i] += (total_cuts[j] * total_cuts[i−2−j]) と更新します。
• ループ終了後、total_cuts[total_points] が方法の総数になるので、これを結果として返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

int divide_circle(int N){
    int total_points = 2 * N;              // 点の総数は 2N
    int total_cuts[total_points + 1] = { 0 };
    total_cuts[0] = 1;                     // 点が 0 個の場合は 1 通り
    total_cuts[2] = 1;                     // 点が 2 個の場合も 1 通り
    for (int i = 4; i <= total_points; i += 2){
        for (int j = 0; j < i-1; j += 2){
            // j 個の点側と残り i-2-j 個の点側の組み合わせを加算
            total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j]);
        }
    }
    return total_cuts[total_points];
}

int main(){
    int N = 3;
    cout<<"Count of ways to divide circle using N non-intersecting chords are:"<<divide_circle(N);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count of ways to divide circle using N non-intersecting chords are: 5

補足：カタラン数との関係

この問題の答えは、実はカタラン数（Catalan number）と一致します。N 本の交差しない弦による円の分割数は N 番目のカタラン数 C(N) = (2N)! / ((N+1)! × N!) で表され、N=3 のとき 5、N=4 のとき 14、N=6 のとき 132 となり、上記の出力と一致します。この動的計画法による計算量は O(N²) です。