yukicoder : No.298 話の伝達

想定誤解法やらかした上、「２問目の方が簡単じゃない？」とか発言してしまった…。
http://yukicoder.me/problems/702

問題

0～(N-1)番のN個のグループがある。

グループAである話題が話されると、グループBでもその話題が確率Cで話される、という関係がいくつか与えられる。
(この関係が循環することはない)

0番のグループがある話題を話したとき、(N-1)番のグループもその話題を話す確率を求めよ。

解法

N個のグループがそれぞれ話題を話す/話さないケースは計2^N通り考えられる。
うち、0番と(N-1)番は話す固定で、残り(N-2)グループが話す/話さない場合2^(N-2)通りについて、そのような事象が発生する確率を求めると、その和が解となる。

Nグループの話す/話さないの組み合わせが決まっているとき、各グループYがその狙った状態になる確率の積を求めよう。
あるグループYがその話題を話さない確率は、「グループXがYに確率Cで話す」という関係があるグループXに対し

• グループXも話していないなら、XからYに話が伝わることはない。
• グループXは話しているが、話が伝わらない確率(1-C)側を引いた

の積を取ったものである。
グループXの話す/話さないは、すでに決まっているので上記積は容易に求まる。

Yがその話題を話す確率は、1から話さない確率を引いたもの。

int N,M;
int rr[21][21];
int yes[21];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>M;
	
	FOR(i,M) cin>>x>>y>>r, rr[x][y]=r;
	
	double ret=0;
	for(int mask=0;mask<1<<N;mask++) {
		FOR(x,N) yes[x]=(mask>>x)&1;
		if(yes[0]==0 || yes[N-1]==0) continue;
		
		double pat=1;
		for(x=1;x<N;x++) {
			double hoge=1;
			FOR(y,N) if(yes[y]&&rr[y][x]) hoge*=(100-rr[y][x])/100.0;
			if(yes[x]) pat*=1-hoge;
			else pat*=hoge;
		}
		ret += pat;
	}
	_P("%.12lf\n",ret);
	
}

まとめ

想定誤解法、怪しいと思いながらもサンプル通ったので出してしまった。
その後しばらくゲームしてたら終盤「３問目が実はWriter解が違う」とか言われてびっくり。