mayoko’s diary

プロコンとかいろいろ。

TCO15 Round 1B med:TheTips

TCO Round 1Bの練習です。easyは全探索するだけっぽいので省略。

問題:TopCoder Statistics - Problem Statement

解法:それぞれの人が見つかる確率を考える。ある人iが見つかるのは,
プレイヤーが自力でaさんを見つける->bさんがaさんの情報で見つかる->cさんがbさんの情報で見つかる->...->iさんが情報で見つかる
という感じで,まず誰かを自力で見つけた後誰かの情報を通して見つけるという形になるので,iさんを見つけられない確率は,
j(j=0〜N-1)さんを通してiを見つけることができるすべてのjに対して,jを見つけない確率
と等しい。見つける確率はこの余事象で求められる。
以下ソースコード

vector<int> G[64];
bool vis[64];

bool dfs(int v, int t) {
    if (v == t) return true;
    vis[v] = true;
    for (int u : G[v]) {
        if (vis[u]) continue;
        if (dfs(u, t)) return true;
    }
    return false;
}

class TheTips {
public:
    double solve(vector <string> clues, vector <int> probability) {
        for (int i = 0; i < 64; i++) G[i].clear();
        int N = clues.size();
        vector<double> p(N);
        for (int i = 0; i < N; i++) p[i] = probability[i] / 100.;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (clues[i][j] == 'Y') G[i].push_back(j);
            }
        }
        double ans = 0;
        for (int i = 0; i < N; i++) {
            double no = 1;
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) vis[k] = false;
                if (dfs(j, i)) no *= (1-p[j]);
            }
            ans += 1-no;
        }
        return ans;
    }
};

わかった時結構テンション上がったけど皆結構普通に解いててしかも平均点より自分の取った点数低かったし悲しい。