yukicoder No.298 話の伝達

はい･････････････････････････････

問題

No.298 話の伝達 - yukicoder

解法

割と引っかかる人多い気がするので誤解法も紹介します。
想定誤解法では, dp[i] = (i に話が伝達しない確率)として, 1-dp[N-1] を求めることを目標にします。各 i の dp[i] を求めるためには, メモ化再帰を使います。

まず, i に話を直接伝達させる可能性のある頂点の集合 S を列挙します。で, その各頂点に対して dp[j] を求めます。その後, S の部分集合を全列挙して, 「部分集合に含まれる頂点には話が伝達している, それ以外には話が伝達していない, という条件で, i に話が伝達しない確率はいくつか」というのを求めます。これの合計が dp[i] になりそうですね(嘘です)。

この解法をコードにしたのがこちら。

#39763 No.298 話の伝達 - yukicoder

ですが, これは嘘解法です。なぜかを考えるために challenge01.txt の入力を見てみます。
4 4
0 1 50
1 2 50
1 3 50
2 3 50

これで 3 に話が伝達しない確率を考えたいですが, このようなグラフの場合だと, そもそも 1 に話が伝達していなければ 2 に話が伝達していることはありえないです。つまり, 2 に話が伝達するかどうかは 1 の頂点に話が伝達しているかどうかに依存しています。
よって, 先ほどのような場合分けをしてしまうと, 独立でない事象の足し算になってしまい, 正しい答えが得られない可能性があります。これが嘘解法である原因です。

ではどうすれば良いのかというと, 「伝達する頂点はここ」と決め打ちした後, そのようになる確率を求めれば良いです(もちろん頂点 0 と頂点 N-1 は伝達する頂点にします)。
伝達する頂点に実際に伝達する確率を求めるために, 余事象を考えます。頂点 i に話を直接伝達させる可能性のある頂点 j それぞれについて,
・j に話が伝達することになっているなら, j -> i の辺を経由してはいけない。その確率は 1-c
・j に話が伝達しないことになっているなら, j -> i の辺は経由しようがしまいがどうでも良い。その確率は 1
これらの値を掛けあわせてもので 1 を引くと, i に話が伝達する確率が得られます。

このような考え方をすると, 先ほどのような依存関係を回避でき, それぞれの場合を独立事象と考えることができるので, 正しい答えを求めることが出来ます。

struct Edge {
    int from;
    double p;
    Edge(){}
    Edge(int f, double p) : from(f), p(p) {}
};
const int MAXM = 300;
int A[MAXM], B[MAXM], C[MAXM];
vector<Edge> es[22];
bool is[22];

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i] >> C[i];
        es[B[i]].emplace_back(A[i], C[i]/100.);
    }
    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }
    double ans = 0;
    for (int s = 0; s < 1<<(N-2); s++) {
        memset(is, false, sizeof(is));
        is[0] = is[N-1] = true;
        for (int i = 1; i < N-1; i++) if ((s>>(i-1))&1) is[i] = true;
        vector<double> p(N, 1);
        p[0] = 0;
        for (int i = 0; i < N; i++) {
            for (Edge e : es[i]) if (is[e.from]) {
                p[i] *= 1-e.p;
            }
        }
        double prob = 1;
        for (int i = 0; i < N; i++) {
            if (is[i]) prob *= 1-p[i];
            else prob *= p[i];
        }
        ans += prob;
    }
    printf("%.15lf\n", ans);
    return 0;
}