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