1ミス位するかと思ったら、すんなり解けた。
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番目の人は2回戦では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で既出だったか。