Yukicoder066 輝け☆全国たこやき杯

問題概要

$2^M$人でトーナメントを行う。1人目の人が優勝する確率は？
ある人とある人との勝率は与えられる。

$M\leqq10$、$M\leqq10^3$、$c(u,v)\leqq10^3$

yukicoder066

解法

$dp(i,j)$:= $i$回戦目で、$j$さんが勝つ確率として、DPをする。
遷移がちょっと詰めないとめんどくさそうと感じる。bitで演る人は変態だと思う。(褒め言葉)
区間$[L,R)$を下から処理していく際に、再帰っぽく書くととても楽にかける。(segtreeで自分の子をみてmergeするかんじ)

計算量:$O(2^{M}*M^{2})$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    double pro(int A, int B, VI& S) {
        return 1.0*(S[A] * S[A]) / (1.0*S[A] * S[A] + S[B] * S[B]);
    }
    
    vector<double> solve(int l, int r, VI& S) { // [l,r)
        if (l == r - 1) {
            return vector<double>(1, 1);
        }
        int m = (l + r) / 2;
        vector<double>left = solve(l, m, S);
        vector<double>right = solve(m, r, S);
        vector<double>res(SZ(left) * 2);
        FOR(i, l, m) {
            FOR(j, m, r) {
                res[i - l] += pro(i, j, S)*left[i - l] * right[j - m];
                res[j - l] += pro(j, i, S)*left[i - l] * right[j - m];
            }
        }
        return res;
    }
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int N; cin >> N;
        VI S(1 << N);
        FOR(i, 0, 1 << N) {
            cin >> S[i];
        }
        vector<double> res = solve(0, 1 << N, S);
        double ans = res[0];
        cout << fixed << setprecision(10) << ans << "\n";
    
        return 0;
    }