Typical DP Contest C - トーナメント

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament

解法

まず各山について考える．たとえば，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 calc_prob(double r1, double r2) {
    return 1.0 / (1 + pow(10, (r2 - r1) / 400));
}

int main() {
    cout << fixed << setprecision(10);

    int k; cin >> k;
    vector<int> R(1 << k);
    for(auto& x : R) cin >> x;

    function<vector<double>(int, int)> solve = [&] (int l, int r) {
        if(r - l == 1) {
            return vector<double>{1.0};
        }
        vector<double> res(r - l);
        const int sz = (r - l) / 2;
        auto l_res = solve(l, l + sz), r_res = solve(l + sz, r);
        for(int i = 0; i < sz; ++i) {
            for(int j = 0; j < sz; ++j) {
                res[i] += calc_prob(R[l + i], R[l + j + sz]) * l_res[i] * r_res[j];
                res[j + sz] += calc_prob(R[l + j + sz], R[l + i]) * l_res[i] * r_res[j];
            }
        }
        return res;
    };

    for(auto&& ans : solve(0, 1 << k)) {
        cout << ans << endl;
    }
}