C++で円上のすべてのノードを交差しない辺で接続する配置方法の数を求めるプログラム

問題概要

n 個のノードが円形に配置されていると仮定します。すべてのノードがちょうど 1 本の辺で接続され、かつどの 2 つの辺も互いに交差しないように、n / 2 本の辺を配置する方法の数を求める必要があります。答えが非常に大きくなる可能性があるため、その場合は結果を 10^9 + 7 で割った余りを返します。

たとえば、入力が n = 4 の場合、出力は 2 になります。これは、4 つのノードを交差なくペアにする方法が 2 通り存在するためです。

解決のためのアプローチ

この問題は動的計画法(DP)を用いることで効率的に解けます。実は、この問題の答えはカタラン数(Catalan Number)と深い関係があります。円周上に並んだ点を交差しないようにペアリングする方法の数は、カタラン数の列と一致することが知られているからです。

具体的には、以下の手順で解きます。

• サイズ (n/2 + 1) の配列 dp を定義します。

• 初期値として dp[0] := 1、dp[1] := 1 を設定します。

• 剰余演算用の定数 m := 10^9 + 7 を用意します。

• i := 2 から i <= n / 2 まで、i を 1 ずつ増やしながら以下を繰り返します。

  • high := i とします。

  • dp[i] := 0 で初期化します。

  • j := 1 から j <= high / 2 まで、j を 1 ずつ増やしながら以下を繰り返します。

    • dp[i] := (dp[i] + (2 * dp[j - 1] * dp[high - j])) mod m と更新します。

  • high % 2 が 0 以外(奇数)の場合、次を行います。

    • dp[i] := (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) mod m と更新します。

  • 最後に dp[i] := dp[i] mod m とします。

• dp[n / 2] を返します。

考え方のポイント

この DP では、「あるノードと直接結ばれる相手」を固定することで問題を分割しています。円周上の一点に注目すると、その点と結ばれる点によって円弧が 2 つの領域に分かれ、それぞれの領域内でのペアの組み方は互いに独立に数えられます。この性質を利用することで、小さな部分問題の答えを組み合わせて全体の答えを構築できるのです。

C++ 実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
    vector<long long> dp(n / 2 + 1);
    dp[0] = 1;
    dp[1] = 1;
    int m = 1000000007;
    for (int i = 2; i <= n / 2; i++) {
        int high = i;
        dp[i] = 0;
        for (int j = 1; j <= high / 2; j++) {
            dp[i] = (dp[i] + (2 * dp[j - 1] * dp[high - j])) % m;
        }
        if (high % 2) dp[i] = (dp[i] + (dp[(high - 1) / 2] * dp[(high - 1) / 2])) % m;
        dp[i] %= m;
    }
    return dp[n / 2];
}
main(){
    int n = 4;
    cout << solve(n);
}

入力

4

出力

2

計算量

このアルゴリズムの時間計算量は O(n²)、空間計算量は O(n) となります。n が大きい場合でも、10^9 + 7 での剰余を取りながら計算を進めることで、オーバーフローを防ぎつつ正確な答えを得ることができます。