読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

TCO 2015 Round 1B Med - TheTips

programming SRM

問題

TopCoder Statistics - Problem Statement

問題概要

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

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

イデア

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

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

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

実装(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を見つけるための手がかりを1つも見つけられない確率
            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;
    }
};