UVa 542 : France '98

問題リンク：France '98

問題概要：
16個の国と
各国間での勝率があたえられる
これらの国が図のようなトーナメントを行った時、各国が優勝する確率を求めよ

解法：
状態が少ないので再帰ですべて数えた

実装時間：
1時間４分
たった一つのバグを50分近く見つけることができなかった

コード：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<climits>
#include<cassert>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 16
#define DEPTH 5

using namespace std;

string country[20];
double win[20][20];
double ans[20];
vector<int> winner[10];
vector<double> prob[10];

void dfs(int phase,int cur){

  if(phase >= DEPTH-1){
    ans[winner[phase][cur]] += prob[phase][cur];
    return;
  }

  int nphase = phase;
  int next = cur + 2;
  if(next >= winner[phase].size()){
    nphase++;
    next = 0;
  }

  int fr = winner[phase][cur];
  int en = winner[phase][cur+1];

  winner[phase+1][cur/2] = fr;
  prob[phase+1][cur/2]   = prob[phase][cur] * prob[phase][cur+1] * win[fr][en];
  dfs(nphase,next);

  winner[phase+1][cur/2] = en;
  prob[phase+1][cur/2]   = prob[phase][cur] * prob[phase][cur+1] * win[en][fr];
  dfs(nphase,next);

}

int main(){

  for(int i=0,limit=MAX;i<DEPTH;i++,limit/=2){
    winner[i].resize(limit),prob[i].resize(limit);
  }

  rep(i,MAX){
    cin >> country[i];
    winner[0][i] = i, prob[0][i] = 1, ans[i] = 0;
  }
  rep(i,MAX)rep(j,MAX){
    cin >> win[i][j];
    win[i][j] *= 0.01;
  }

  dfs(0,0);

  rep(i,MAX){
    printf("%-10s p=%.2lf%%\n",country[i].c_str(),ans[i]*100.0);
  }
  return 0;
}