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; }