Typical DP Contest C - トーナメント

問題文 : トーナメント

解法 :

dp[i][x] := i 番目の人がx 回目の試合で勝てる確率, とし$S$ をx 回目の試合で当たる可能性のある人達の集合とすると
$dp[i][0] = 1.0$
$dp[i][x] = dp[i][x - 1] \times \displaystyle \sum_{j \in S} (dp[j][x - 1] \times \mathrm{Pr}[人j に勝てる]$)

となるので, 順次求めて$dp[x][k]$ を出力すれば良い. $O(k2^k)$ 時間で求まる.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>

using namespace std;

double dp[2048][11];

int main()
{
	int k;
	int r[2048];
	
	scanf("%d", &k);
	
	for (int i = 0; i < 1 << k; i++){
		scanf("%d", &r[i]);
		dp[i][0] = 1;
	}
	
	for (int i = 1; i <= k; i++){
		for (int j = 0; j < 1 << k; j++){
			dp[j][i] = 0;
			int low = (j / (1 << i)) * (1 << i);
			int up = low + (1 << i);
			int low2 = (j / (1 << (i - 1))) * (1 << (i - 1));
			int up2 = low2 + (1 << (i - 1));
			for (int L = low; L < up; L++){
				if (low2 <= L && L < up2) continue;
				dp[j][i] += dp[L][i - 1] * (1.0 / (1 + pow(10, (r[L] - r[j]) / 400.0)));
			}
			dp[j][i] *= dp[j][i - 1];
		}
	}
	for (int i = 0; i < 1 << k; i++) printf("%lf\n", dp[i][k]);
	
	return (0);
}