GCJ Round 2 2016 Problem B. Red Tape Committee

問題

Dashboard - Round 2 2016 - Google Code Jam

N 人の人がいる。それぞれの人は, YES という確率が P[i] で, NO という確率が 1-P[i] である。N 人の中から K 人の人を選んで YES という人と NO という人の確率が K/2 人ずつになる確率を最大化したい(K は偶数)。このときの確率を求めよ。

解法

Small は N 人の中から K 人選ぶ集合を全通り試せばいけます。

Large について考えます。

もし選ぶ K 人が決まったとすると, この K 人が半々に分かれる確率は, dp[n][yes][no] = (n 人目まで見たとき, YES という人が yes 人, NO という人が no 人の確率)を考えれば, O(K^3) の dp でこれを解くことができます。なので, K 人をどうやって決めるのか, というのが問題なんですが, 確率を増やすためには, 情報量の多い(分散の少ない)人をたくさん選ぶほうが得な気がします。つまり, P についてソートした時, 両端から取っていくのが良さそうな気がします。

これは実際に正しいです。これを考えると, 左端から k 人, 右端から K-k 人取った際に K/2 人ずつに分かれる確率を考えて最大化すればよくなります。

なんで両端から見るのが良いか, っていうのは上の直観でなんとかした(時間がなかったので適当な解法を試していたら Small と完全一致した)んですが, 終わった後 TL を見て証明を把握したので紹介します。

最後の一つ以外を決定したとすると, 最後に選ばれる人の YES という確率が p として, dp[K][K/2][K/2] は, dp[K-1][K/2-1][K/2]*p + dp[K-1][K/2][K/2-1]*(1-p) というように一次式になります。ようするに a*p + b という形になるわけですが, a が正の場合は p が大きいほうがよく, 負の場合は p が小さいほうが良いです。なので, 必然的に p は最小のものか最大のものを取るのが良い, ということになります。

人の選ぶ順番は関係ないので, これで選ばれた人は確定したとして, 他の人もどんどん確定させていけば, 結局両端から人を取っていくことが最適であることがわかります。

namespace Small {
    void solve() {
        int N, K;
        cin >> N >> K;
        vector<double> P(N);
        for (int i = 0; i < N; i++)
            cin >> P[i];
        double ans = 0;
        for (int s = 0; s < 1<<N; s++) {
            if (__builtin_popcount(s) != K) continue;
            int sub = s;
            double tmp = 0;
            do {
                if (__builtin_popcount(sub) == K/2) {
                    double plus = 1;
                    for (int i = 0; i < N; i++) if ((s>>i)&1) {
                        if ((sub>>i)&1) plus *= P[i];
                        else plus *= 1-P[i];
                    }
                    tmp += plus;
                }
                sub = (sub-1) & s;
            } while (sub != s);
            ans = max(ans, tmp);
        }
        printf("%.10lf\n", ans);
    }
}

namespace Large {
    int N, K;
    double dp[222][222][222];
    double dpr[222][222][222];
    void solve() {
        cin >> N >> K;
        vector<double> P(N);
        vector<int> Pint(N);
        for (int i = 0; i < N; i++) {
            cin >> P[i];
        }
        sort(P.begin(), P.end());
        for (int i = 0; i <= K; i++) for (int j = 0; j <= K; j++) for (int k = 0; k <= K; k++) {
            dp[i][j][k] = 0;
            dpr[i][j][k] = 0;
        }
        dp[0][0][0] = 1;
        for (int i = 0; i < N; i++) {
            for (int ok = 0; ok <= i; ok++) for (int ng = 0; ng <= i-ok; ng++) {
                if (dp[i][ok][ng] > 0) {
                    dp[i+1][ok+1][ng] += P[i]*dp[i][ok][ng];
                    dp[i+1][ok][ng+1] += (1-P[i])*dp[i][ok][ng];
                }
            }
        }
        dpr[0][0][0] = 1;
        for (int i = 0; i < N; i++) {
            for (int ok = 0; ok <= i; ok++) for (int ng = 0; ng <= i-ok; ng++) {
                if (dpr[i][ok][ng] > 0) {
                    dpr[i+1][ok+1][ng] += P[N-1-i]*dpr[i][ok][ng];
                    dpr[i+1][ok][ng+1] += (1-P[N-1-i])*dpr[i][ok][ng];
                }
            }
        }
        double ans = 0;
        for (int k = 0; k <= K; k++) {
            double tmp = 0;
            for (int i = 0; i <= K/2; i++) {
                tmp += dp[k][i][k-i] * dpr[K-k][K/2-i][K/2-k+i];
            }
            ans = max(ans, tmp);
        }
        printf("%.10lf\n", ans);
    }
}
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": ";
        Large::solve();        
    }
    return 0;
}