TCO 2015 Round 1B Med - TheTips

問題

TopCoder Statistics - Problem Statement

問題概要

脱出ゲームみたいなもの。部屋の中に個の手がかりが隠されている。次の正方行列によって番目の手がかりを見つけると番目の手がかりを見つけられるかどうかがY/Nで書かれている。Yなら番目の手がかりを見つけた時に番目の手がかりを確実に見つけることが出来る。Nなら絶対できない。また、それとは別にそのような手がかりを全く頼りにすることなく番目の手がかりを見つけることが出来る確率はとして与えられる。

この時に、最終的に見つけている手がかりの個数の期待値を答えよ。

アイデア

手がかりごとに考えていく。期待値の線形性から、求めるべきものは各手がかりが見つけられる確率の総和であるという問題に言い換えられる。つまり、ここから番目の手がかりを見つけられる確率に着目していく。番目の手がかりにたどり着く方法を考えてみると、他の番目の手がかりを見つけて、そこからたどっていくことで番目の手がかりにたどり着く、もしくは番目の手がかりを直接見つけるかの２つに分けられる。

前者に関しては、そのような手がかりを少なくとも１つ見つけられれば良いので、余事象を取る感じにすればよい。つまり、番目の手がかりにたどり着くための手がかりを１つも見つけることが出来ない確率を求めていく。後者に関しては、番目の手がかりにたどり着くための手がかりを１つも見つけることが出来なかった時に、直接見つける確率ということなので、p*probability[i]/100とすればよい。

番目の手がかりにたどり着くための手がかりを見つける方法だが、事前の処理として、「番目の手がかりを見つけた時に、そこからたどれる手がかりは何か」というものを、幅優先探索的な感じで見つけて用意しておくと良い。

実装(C++)

class TheTips {
    public:
    double solve(vector<string> clues, vector<int> probability) {
        int n=clues.size();

        //iを見つけた場合、どのclueにたどり着けるか
        set<int> s[50];
        rep(i,n)
        {
            //BFS
            queue<int> que;
            que.push(i);
            s[i].insert(i);
            while(!que.empty())
            {
                int v=que.front();
                que.pop();
                rep(j,n)
                {
                    if(clues[v][j]=='Y')
                    {
                        if(s[i].find(j)==s[i].end())
                        {
                            s[i].insert(j);
                            que.push(j);
                        }
                    }
                }
            }
        }

        double ret=0;

        rep(i,n)
        {
            //iを見つけるための手がかりを見つけるか、iを直接見つけるか

            //iを見つけるための手がかりを１つも見つけられない確率
            double p=1;
            rep(j,n)
            {
                if(i==j) continue;
                //jからiにたどり着くことが出来る
                if(s[j].find(i)!=s[j].end()) p*=(1-probability[j]/100.0);
            }

            ret+=p*probability[i]/100.0+1-p;
        }

        return ret;
    }
};