TopCoderOpen 2014 Round1B Hard EagleInZoo

コード量的にはこちらの方が楽。
http://community.topcoder.com/stat?c=problem_statement&pm=13117

問題

根付き木が与えられる。
ここから以下のような動作で各頂点に鷲が止まっていく。

• 動作は根から始まる。
• 今いる頂点に他の鷲がいないなら、そこに止まる。
• 今いる頂点に他の鷲がいるなら、子の頂点を等確率でランダムに選び、そちらに移動して上記条件を確認する。
• 今いる頂点に他の鷲がいて、かつ子の頂点がないならその鷲は木に止まれない。

K匹目の鷲が木に止まれる確率を求めよ。

解法

先に全部の頂点に鷲が埋まってるとして、次の鷲が各頂点に来る確率を求めておく。
これは(親頂点の確率)/(子頂点の数)を再帰的に求めておくだけ。

x匹目の鷲が頂点iに止まる確率は、(x-1)匹目までに親の頂点に鷲が止まっていてかつ頂点iに鷲が止まっておらず、かつx匹目の鷲が頂点iに来る確率である。
そこで(x-1)匹目までが頂点に止まる確率を覚えておけば簡単に求められる。

頂点数N・鷲数Kに対しO(NK)で解ける。
以下のコードはK==1の時は必ず根の頂点に止まれるので特別扱いした。
また、この問題は頂点数が最大51なので注意。

class EagleInZoo {
	public:
	int C[55];
	double P[55],S[55];
	double calc(vector <int> parent, int K) {
		int i,x,y,N;
		N=parent.size()+1;
		
		if(K==1) return 1;
		
		ZERO(C);
		FOR(i,parent.size()) C[parent[i]]++;
		P[0]=1;
		for(i=1;i<N;i++) P[i]=P[parent[i-1]]/C[parent[i-1]];
		
		ZERO(S);
		S[0]=1;
		double ret=0;
		for(x=2;x<=K;x++) {
			for(y=N-1;y>=1;y--) {
				if(x==K) ret+=(S[parent[y-1]]-S[y])*P[y];
				S[y]+=(S[parent[y-1]]-S[y])*P[y];
			}
		}
		return ret;
	}
};

まとめ

他の解答はCombinationとか使ってるけど、こちらの方が簡単だと思うんだよね。