TopCoder SRM 724 Div2 Hard: UnfinishedTournamentEasy

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

人のリーグ戦の表が与えられる (引き分けなし)。試合は全て終わっているわけではなく、勝敗がまだ決していない箇所は '?' で表される。

'?' を埋めたとき、勝率の分散の最大値を求めよ。

解説

番目の人が勝った回数を とし、勝率を 、勝率の平均を とします。

このとき、分散 は以下のように変形できます。

\begin{align} V &= \frac{ (s_{1} - \mu)^{2} + \dots + (s_{N} - \mu)^{2} }{N} \\ &= \frac{ \sum_{i} s_{i}^{2} - 2 \mu \sum_{i} s_{i} + N \mu^{2} }{N} \\ &= \frac{ \sum_{i} w_{i}^{2} }{N (N-1)^{2} } - \frac{1}{4} \end{align}

は定数ですから、この式を最大化するには勝利数の二乗和を最大化すれば良いことが分かります。つまり、上位の人はなるべく多く勝ち、下位の人はなるべく少なく勝つべきです。

勝利数の二乗和最大を求める DP を考えます。先の議論から、上位は空いている試合で全て勝つのが良いため、次のようにします。

上から順位が確定した人の集合を としたときの勝利数の二乗和の最大値

与えられたリーグ表において始めから勝ちになっている場所、およびまだ順位が確定していない人との試合で勝ったことにして更新すれば、これを求めることができます。

ソースコード

int dp[1 << 20];
class UnfinishedTournamentEasy {
    public:
    double maximal(vector<string> G) {
        int N = G.size();
        fill(dp, dp+(1<<N), 0);

        for(int bit=0; bit<(1<<N); bit++) {
            for(int i=0; i<N; i++) {
                if(bit >> i & 1) continue;

                int win = 0;
                for(int j=0; j<N; j++) {
                    if(i == j) continue;
                    if(G[i][j] == 'W') win++;
                    if(G[i][j] == '?') {
                        if(!(bit >> j & 1)) win++;
                    }
                }
                chmax(dp[bit | (1 << i)], dp[bit] + win * win);
            }
        }

        int sum_win = dp[(1 << N) - 1];
        return 1.0 * sum_win / (N*(N-1)*(N-1)) - 1.0 / 4.0;
    }
};