kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2015 Round1B Medium TheTips

最初えらく手間のかかる解法を取ってしまったが、落ち着いて考えれば単純だった。
http://community.topcoder.com/stat?c=problem_statement&pm=13716

問題

N人が隠れるかくれんぼを行う。
それぞれを単独で見つけられる確率はP[i]である。

また、各人は一部他人の位置を知っており、その関係が行列Cで与えられる。
他人の位置を知っている人を見つけた場合、その他人も見つけることができる。

見つけることができる人数の期待値を求めよ。

解法

ある人が見つけられない確率はその人が単独で見つけられない他、その人の位置を知っている人、もしくは間接的にその人の位置を知っている人のすべてが見つからない場合である。

まず、Warshall-Floyd法で間接的なものも含め、誰が見つかると自分が見つかってしまうかを求める。
各人iに置いて、WF法で求めた「(自分含め)この人が見つかると、自分も見つかる」と言った人の集合をS(i)とすると、人iが見つかる確率は \displaystyle 1-\prod_{j\in S(i)} (1-P_j)となる。

これをN人分足し合わせるので、全体では \displaystyle \sum_{i \lt N} \left(1-\prod_{j\in S(i)} (1-P_j) \right)が解。

class TheTips {
	public:
	double solve(vector <string> clues, vector <int> probability) {
		int N=clues.size();
		int i,x,y;
		
		FOR(i,N) FOR(x,N) FOR(y,N) if(clues[x][i]=='Y' && clues[i][y]=='Y') clues[x][y]='Y';
		double ret=0;
		FOR(i,N) {
			double fail=1;
			FOR(x,N) if(clues[x][i]=='Y' || i==x) fail *= 1-probability[x]/100.0;
			ret += 1-fail;
		}
		return ret;
	}
}

まとめ

最初は強連結成分分解とかやってしまった。