TopCoder SRM620: RandomGraph

ある１つの頂点 \(X\) に着目したとき、その頂点がサイズ３以下の連結成分に含まれる時のパターンは以下の５つになる。

1. 連結成分が１つの場合
2. 連結成分が２つの場合
3. 連結成分が３つの場合 - \((X, Y), (Y, Z)\) のように枝が伸びている場合
4. 連結成分が３つの場合 - \((X, Y), (X, Z)\) のように枝が伸びている場合
5. 連結成分が３つの場合 - \((X, Y), (X, Z), (Y, Z)\) のように枝が伸びている場合

DP[n] = 「n 頂点のグラフが サイズ３以下の連結成分だけで構成されている確率」とすると

DP[n] = 「これらのパターンに収まる確率 × その連結成分を除外した頂点がサイズ３以下の連結成分だけで構成されている確率」の和

のように漸化式を構築できるので、これを使って動的計画法を適用する。 \(O(n)\)

public class RandomGraph {
    public double probability(int n, double p) {
        var dp = new double[n + 1];
        p /= 1000;
        for (int i = 0; i <= n; i++) {
            if (i <= 3) dp[i] = 1.0;
            else {
                double val = 0;
                // 0 edge : a
                val += Math.Pow(1 - p, i - 1) * dp[i - 1];
                // 1 edge : a - b
                val += (i - 1) * Math.Pow(1 - p, (i - 2) * 2) * p * dp[i - 2];
                // 2 edge: b - a - c
                val += (i - 1) * (i - 2) / 2 * Math.Pow(1 - p, (i - 3) * 3) * p * p * (1 - p) * dp[i - 3];
                // 2 edge: a - b - c
                val += (i - 1) * (i - 2) * Math.Pow(1 - p, (i - 3) * 3) * p * p * (1 - p) * dp[i - 3];
                // 3 edge: a-b, b-c, c-a
                val += (i - 1) * (i - 2) / 2 * Math.Pow(1 - p, (i - 3) * 3) * p * p * p * dp[i - 3];
                dp[i] = val;
            }
        }

        return 1 - dp[n];
    }
}