Typical DP Contest - C トーナメント

C: トーナメント - Typical DP Contest | AtCoder

class c_tournament {
public:
    // x が y に勝つ確率
    double win(int x, int y, const vector<int> &el) {
            return 1.0/(1.0+pow(10.0,(el[y]-el[x])/400.0));
    }
    void solve(void) {
            int K;
            cin>>K;
            int N = (1<<K);
            vector<int> el(N,0);

            REP(i, N) cin>>el[i];

            // dp[i][j] := i 人目が j round 目を勝ち上がる確率
            vector<vector<double>> dp(N, vector<double>(K+1,0));
            REP(i, N) dp[i][0] = 1.0;

            // O(K^2*N)
            FOR(k, 1, K+1)
            {
                //
                // (0            d    )
                // (0,    a )( b    c )
                // (0,1)(2,3)(4,5)(6,7)
                //
                // 勝ち進むにつれ戦う可能性のある相手が含まれる区間が大きくなる。
                // k round 目では現在の区間から k-1 round 目の区間をのぞいた場所に
                // に含まれる番号の人と戦うことになる。
                //
                int len = (1<<k); // 区間の長さ
                REP(x, N)
                {
                    // [l,r)
                    int l = x/len*len; // 丸め
                    int r = l+len;
                    int mid = l+len/2;

                    // [l,mid)[mid,r) にxを含む前のroundの区間がこのどちらかにふくまれるはず
                    // 含まれないほうにいる人が現在の round での対戦相手となる
                    if (x<mid)
                        FOR(y, mid, r) dp[x][k] += dp[x][k-1]*dp[y][k-1]*win(x, y, el);
                    else
                        FOR(y, l, mid) dp[x][k] += dp[x][k-1]*dp[y][k-1]*win(x, y, el);
                }
            }
            REP(i, N)
                cout<<dp[i][K]<<endl;
    }
};