POJ 2261 - France '98

http://poj.org/problem?id=2261

概要

16個のチームの名前と，i 番目のチームが j 番目のチームに勝つ確率 p[i][j] が与えられる．

トーナメントで優勝を決めるとき，各チームの優勝する確率を答える．

制約

解法

i 番目のチームと j 番目のチームは，(i >> k) == (j >> k) ならば k 回戦目よりも前に既に勝負している． k 回戦目で戦うのは，k ビット目が異なり，k ビット目より上のビットはすべて一致するような組み合わせ．

つまり，((i >> k) ^ (j >> k)) == 1 となるような i, j の組み合わせが k 回戦目で戦う．

あとはこれに従って，i 番目のチームが k 回戦目まで勝ち残っている確率を dp[i][k] として，k = 1 ... 5 と計算していけばいい．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   char cs[16][20];
 8   for (int i = 0; i < 16; i++) {
 9     scanf("%s", cs[i]);
10   }
11   int prob[16][16];
12   for (int i = 0; i < 16; i++) {
13     for (int j = 0; j < 16; j++) {
14       scanf("%d", &prob[i][j]);
15     }
16   }
17 
18   double dp[16][5];
19   for (int i = 0; i < 16; i++) {
20     fill_n(dp[i], 5, 0.0);
21     dp[i][0] = 1.0;
22   }
23   for (int k = 1; k < 5; k++) {
24     for (int i = 0; i < 16; i++) {
25       for (int j = 0; j < 16; j++) {
26         int x = i >> (k-1);
27         int y = j >> (k-1);
28         if ((x ^ y) == 1) {
29           dp[i][k] += dp[i][k-1] * dp[j][k-1] * (prob[i][j] / 100.0);
30         }
31       }
32     }
33   }
34   for (int i = 0; i < 16; i++) {
35     printf("%-10s p=%.2f%%\n", cs[i], dp[i][4] * 100.0);
36   }
37   return 0;
38 }
poj/2261.cc