Typical DP Contest C - トーナメント

解法

まず各山について考える.たとえば,8人いるなら [0, 7], [0, 3], [4, 7], [0, 1], … などが各山にあたる.
ある山 X に属する個人が,X の中で優勝する確率と,次に X が対戦することになる山 Y の同様の確率が求まるとする.
すると,山 X と Y を統合した山 Z について,Z の中で X および Y に属する個人が勝利する確率を求めることができる.
これをループあるいは再帰で実装すればよい.

計算量は O(K * 2^(2K)).

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
double win(int Rp, int Rq) {
    return 1.0 / (1 + pow(10, (double)(Rq - Rp)/400));
}
 
// [l, r]
vector<double> solve(int l, int r, vector<int> const& rating) {
    if(l == r) {
        return vector<double>(1, 1);
    }
 
    const int m = (l + r) / 2;
    auto left = solve(l, m, rating);
    auto right = solve(m+1, r, rating);
    auto res = vector<double>(left.size() * 2);
    for(int i=l; i<=m; ++i) {
        for(int j=m+1; j<=r; ++j) {
            res[i-l] += win(rating[i], rating[j]) * left[i-l] * right[j-(m+1)];
            res[j-l] += win(rating[j], rating[i]) * left[i-l] * right[j-(m+1)];
        }
    }
    return res;
}
 
int main() {
    int K;
    cin >> K;
    vector<int> rating(1 << K);
    for(int i=0; i<1<<K; ++i) {
        cin >> rating[i];
    }
    auto res = solve(0, (1 << K) - 1, rating);
    for(double x : res) {
        cout << fixed << setprecision(10) << x << endl;
    }
}