模擬国内2016bD 夏合宿の朝は早い (AOJ2748)

解法わかった時びっくりしたので書きます

問題概要
- 制約
解法
結論
提出コード
感想

問題概要

https://onlinejudge.u-aizu.ac.jp/problems/2748

$N$ 人について、朝寝坊する確率 $P_{i}$ を与えられる。各人はそれぞれ何人かの連絡先を知っており、寝坊せずに起きることができたなら連絡先全員に電話して起こすことができる(起こされた人は寝坊せずに起きたことになるので、またその人も連絡先全員に電話をする)

全員が寝坊しない確率を求めてください

制約

$1\ \le\ N\ \le\ 100$

解法

誰も他人の連絡先を知らない場合

$1 - P_{i}$ の総乗算が解です

はてなブログさん。\prodが使えないんですか？

電話が発生する時の観察

人1が人2の連絡先を知っていると仮定します。

人1が起きる確率は $1 - P_{1}$ です

人2が起きる時について、人1が起きた or 人1は寝坊したが自力で起きた時の2通りがあります。しかし、今回求めたいものは「全員が起きる確率」なので、人1が寝坊した時はその時点で全員が起きることが不可能なので考慮する必要がなくなります。

つまり、人2が寝坊したかどうかは関係なくなり、人1のみを考慮すれば良いことがわかります。

一般に考えると、人 $i$ に連絡先を知られている人 $j$ は、人 $i$ が起きているかどうかを考慮すれば良いので、無視して良いことがわかります。

例外、サイクル

上記の主張は、連絡先がサイクルのようになっている時嘘になります。

サイクル $C$ について、

ある $C$ に属する人 $i$ が存在して、ある $C$ に属さない人 $j$ に連絡先を知られている場合

$i$ が起きる場合は $j$ が起きる場合or $j$ が寝坊したけど $i$ が自力で起きる場合の二通りがあります。これはさっきと同じ考え方で、 $i$ が起きるかは無視して良いです。また、 $i$ が起きることができたなら $C$ に属する人全員が起きることができて、そうでない場合はやはり考慮しなくて良いので、 $C$ に属する人全員考慮しなくて良い( $j$ が起きるかどうかに依存するとして良い)ことがわかります。

そうでない場合

$C$ 内の誰か一人が起きれば $C$ 全員が起きることが可能で、そうでない場合は全員そろって寝坊します。

以上より、サイクルは一人の人間とみなして良いです。その人が寝坊する確率はサイクルに属する人全員の $P$ の総乗です。

結論

SCCしてDAGにする -> 入次数が $0$ の頂点の $1 - P$ の総乗が答え。

提出コード

実装が終わった後に $P$ が起きる確率では無く寝坊する確率であることに気づいた・・・・

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

vector<int> SCC(const vector<vector<int>>& G) {
    int N = (int)G.size();
    vector<int> ord;
    vector<bool> vis(N);

    auto dfs1 = [&](auto dfs, int v) -> void {
        vis[v] = true;
        for (auto x : G[v]) if (!vis[x]) {
            dfs(dfs, x);
        }
        ord.push_back(v);
    };

    for (int i = 0 ; i < N ; i++) if (!vis[i]) {
        dfs1(dfs1, i);
    }
    reverse(ord.begin(), ord.end());

    vector<vector<int>> G2(N);
    for (int i = 0 ; i < N ; i++) for (auto t : G[i]) {
        G2[t].push_back(i);
    }

    vector<int> res(N, -1);
    int id = 0;
    auto dfs2 = [&](auto dfs, int v) -> void {
        res[v] = id;
        for (auto x : G2[v]) if (res[x] == -1) {
            dfs(dfs, x);
        }
    };

    for (auto o : ord) if (res[o] == -1) {
        dfs2(dfs2, o);
        id++;
    }

    return res;
}

bool solve() {
    int N; cin >> N;
    
    if (N == 0) return false;

    vector<ld> P(N);
    vector<vector<int>> G(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> P[i];
        P[i] = 1.0 - P[i];
        int m; cin >> m;
        for (int _ = 0 ; _ < m ; _++) {
            int a; cin >> a;
            G[i].push_back(a - 1);
        }
    }

    auto id = SCC(G);
    int N2 = *max_element(id.begin(), id.end()) + 1;
    vector<bool> ins(N2, true);
    vector<ld> P2(N2, 1.0l);

    for (int i = 0 ; i < N ; i++) {
        P2[id[i]] *= 1.0 - P[i];
    }
    for (int i = 0 ; i < N2 ; i++) {
        P2[i] = 1.0l - P2[i];
    }

    for (int i = 0 ; i < N ; i++) {
        for (auto x : G[i]) if (id[i] != id[x]) {
            ins[id[x]] = false;
        }
    }
    
    ld ans = 1.0;
    for (int i = 0 ; i < N2 ; i++) {
        if (ins[i]) {
            ans *= P2[i];
        }
    }

    cout << ans << endl;

    return true;

}

int main() {
    cout << fixed << setprecision(10) << endl;
    while (solve()) ;
}

感想

ギャグに帰着して面白いと思った
ギャグに帰着して面白いと思う時とつまらないと思う時がある。その線引きが自分でもわからない・・・・

zawatinはてなブログ

あぁ.....