2282 France '98
問題概要
16チームによるトーナメントが行われる。
チームのそれぞれの名前および、チーム同士の勝率のテーブルが与えられるとき、
それぞれのチームが優勝する確率を求めよ。
解法
試合の番号を、決勝を0,準決勝を1,2,準々決勝を3,4,5,6...とする。
するとヒープ木と同じ番号のつき方なので、試合iの二つの子の試合はi*2+1,i*2+2となる。
番号iの試合においてj番目のチームが勝ち残る確率をdp[i][j]とすれば、
dp[i][j]=Σdp[i*2+1][j]*dp[i*2+2][k]*p[j][k]+dp[i*2+1][k]*dp[i*2+2][j]*p[j][k]
という漸化式が立つのでDPできる。
ソースコード
int n=16; char nm[16][11]; double dp[31][16],p[16][16]; int main(){ rep(i,n)scanf("%s",nm[i]); rep(i,n)rep(j,n)scanf("%lf",p[i]+j),p[i][j]/=100; for(int i=15;i<31;i++)dp[i][i-15]=1; for(int i=14;i>=0;i--)rep(b,n)rep(a,b) dp[i][a]+=dp[i*2+1][a]*dp[i*2+2][b]*p[a][b], dp[i][b]+=dp[i*2+1][a]*dp[i*2+2][b]*p[b][a]; rep(i,n)printf("%-10s p=%.2f%%\n",nm[i],dp[0][i]*100); return 0; }