yukicoder : No.66 輝け☆全国たこやき杯

１ミス位するかと思ったら、すんなり解けた。
http://yukicoder.me/problems/93

問題

0番～(2^M)-1番の2^M人で、0～(M-1)回戦まである勝ち抜き戦を行う。(原題は1-indexだが、ここでは0-indexにしておく)
強さxとyの人が戦うと、強さxの人が勝つ確率W(x,y)は(x*x)/(x*x+y*y)である、

各人の強さをS[i]とする。
0番の人が優勝する確率を求めよ。

解法

i番の人がj回戦まで進む確率をP[j][i]とする。

P[j+1][i]は、j回戦まで進む確率P[j][i]にj回戦で勝利する確率を掛けたものである。
j回戦で勝利する確率は、j回戦で戦う可能性のある人の各番号kに対し、勝率W(S[i],S[k])をk番の人がj回戦に来る確率P[j][k]で重みづけ平均を取ったものとなる。

j回戦で戦う番号kの候補は、自分の番号iとj桁目以上が同じで、j桁目が逆の人である。
例えば、2進数で11101番目の人は２回戦では110**番目の人と戦う可能性がある。（桁番号や回戦は0-index）

int M;
int S[2000];
double P[11][2000];
double W[2000][2000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,1<<M) cin>>S[i], P[0][i]=1;
	FOR(x,1<<M) FOR(y,1<<M) W[x][y]=(S[x]*S[x]*1.0)/(S[x]*S[x]+S[y]*S[y]);
	
	int mask=0xFFFFFF;
	FOR(i,M) {
		mask -= 1<<i;
		FOR(x,1<<M) {
			FOR(y,1<<M) if((x&mask)==(y&mask) && ((x^y)&(1<<i))) P[i+1][x]+=P[i][y]*W[x][y];
			P[i+1][x]*=P[i][x];
		}
	}
	
	_P("%.12lf\n",P[M][0]);
}

まとめ

TDPCで既出だったか。