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