らての精進日記

修行をします

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;
}