Typical DP Contest C:トーナメント
解法
dp[i][j]:i番目の人がj回戦って勝ち残る可能性
とした。(当然、j=0のときはdp[i][0]=1)
dp[i][j](j>0)を埋める時には、i番目の人のj回目の戦いを想像するといいです。トーナメントの木を考えると、対戦候補は2^(j-1)人います。これはある連続する区間の人たちです。よって、その区間の右端と左端を頑張って見つけました(酷いコードを書いた)。あとは、その区間の任意の人kについて
dp[k][j-1]*(人iと人kが戦ったときに人iが勝つ確率)
を求め、それらの合計にdp[i][j-1]を掛け合わせたものをdp[i][j]とすればよいです。
コード
#include<bits/stdc++.h> using namespace std; double dp[2000][11]; int N,K,R[2000]; double calc(int p,int q){ double x=pow(10,(R[q]-R[p])/400.0); return 1.0/(1+x); } int main(){ scanf("%d",&K); N=(1<<K); for(int i=0;i<N;i++)scanf("%d",&R[i]); for(int i=0;i<N;i++)dp[i][0]=1.0; for(int i=1;i<=K;i++){ for(int j=0;j<N;j++){ int l=j,r; for(int k=0;k<i-1;k++)l/=2; l=r=l+((l&1)?-1:1); for(int k=0;k<i-1;k++){ l*=2; r=r*2+1; } dp[j][i]=0; for(int k=l;k<=r;k++){ dp[j][i]+=dp[k][i-1]*calc(j,k); } dp[j][i]*=dp[j][i-1]; } } for(int i=0;i<N;i++)printf("%.8lf\n",dp[i][K]); return 0; }