Typical DP Contest C - トーナメント

問題

tdpc.contest.atcoder.jp

解法

普通に dp[k][i] = (i が k 回戦まで勝ち抜く確率) とやれば良いんですが, 微妙に遷移で迷ったので書いておきます。

i が k 回戦で戦う可能性がある競技者を考えます。p = 1<= med であるとすると, いままでは [med, maxi) と戦っていて, これから [mini, med) のいずれかの競技者と対戦します。i < med の場合は, いままでは [mini, med) と戦っていて, これから [med, maxi) のいずれかの競技者と対戦します。

ここまでわかれば後は簡単で, k 回戦で戦う可能性がある各競技者 j について, (j が k-1 回戦まで勝ち抜く確率) * (i が j に勝つ確率) の和が dp[k][i] になります。

double winProb(int Rp, int Rq) {
    return 1/(1+pow(10, (Rq-Rp)/400.));
}

int R[1<<10];
double dp[12][1<<10];

int main() {
    int K;
    cin >> K;
    for (int i = 0; i < (1<<K); i++) scanf("%d", R+i);
    for (int i = 0; i < (1<<K); i++) dp[0][i] = 1;
    for (int k = 1; k <= K; k++) {
        int p = 1<<k;
        for (int i = 0; i < (1<<K); i++) {
            int maxi = (i+p)/p*p;
            int mini = maxi-p;
            int med = (maxi+mini)/2;
            double prob = 0;
            if (i >= med) {
                for (int j = mini; j < med; j++) prob += dp[k-1][j]*winProb(R[i], R[j]);
            } else {
                for (int j = med; j < maxi; j++) prob += dp[k-1][j] * winProb(R[i], R[j]);
            }
            dp[k][i] = prob*dp[k-1][i];
        }
    }
    for (int i = 0; i < (1<<K); i++) printf("%.7lf\n", dp[K][i]);
    return 0;
}