Typical DP Contest C トーナメント
方針
dp[i][j] := iがj回戦で勝つ確率
としてこれを更新するDP.
j回戦目で戦う相手の候補は、2^j人いて、
それは、iのj番目のビットを反転させて、その下を0〜2^jにした人たち。
(その人たちがそれぞれ勝ち上がる確率) * (その人に勝利する確率)が、
その人がj回戦を勝ち上がる確率。
計算量はO(n^2logn)より小さいと思うんだけどいくつなんだろうか。
ソースコード
int n, k, r[1024]; double dp[1024][11]; double P(int a, int b){ //aがbに勝つ return 1.0 / (1 + pow(10.0, (b - a) / 400.0)); } int main(){ cin >> k; n = 1 << k; rep(i, n) cin >> r[i]; rep(i, n) dp[i][0] = 1; rep(j, k) rep(i, n){ double p = 0; rep(l, 1 << j){ int idx = ((i ^ 1 << j) & ~((1 << j) - 1)) + l; p += dp[idx][j] * P(r[i], r[idx]); } dp[i][j+1] = p * dp[i][j]; } rep(i, n) printf("%.9f\n", dp[i][k]); return 0; }