GCJ 2016 Round2 B - Red Tape Committee
問題
Dashboard - Round 2 2016 - Google Code Jam
問題概要
人の人がいる.そして,Yes
かNo
かで投票をしてもらい多数決をしようとしている.人に関して,Yes
に投票する確率がである(つまり,No
に投票する確率は).
今,この中から人を選んでその人に投票してもらうことにした.このとき,Yes
とNo
の投票数が同じになる(この状況をtie
と呼ぶ)確率が最も高くなるように人を選んだ時のtie
になる確率を求めよ.
- ,は偶数
アイデア
問題として,人として誰を選ぶべきなのかということ,そして確率をどのように効率よく計算していくかという二点について考える必要がある.
確率を効率よく計算するためには,選んだ人が決まっているならば(今何人目,Yes
-の数No
の数)というのを保存しながらDPをしていけばで計算することが可能である.
それでは,どのように人から人を選べばよいか考えていく.できるだけ「中庸な」,つまり確率が0.5に近い人から人を選んでいけば良いんじゃないかという感じがするが,実はその逆で,できるだけ0.5からから離れている人から人を選ぶのが実は最適である.人を0にできるだけ近い方から選び,人をできるだけ1に近い方から選ぶということを考える.これが正しいのか,直感的には正しそうな感じがする(0.5の人を2人選ぶよりは,0と1を選んだほうがtie
になる確率の方が高いのはすぐわかる).この正当性を証明したい.以下背理法で示す.
まず,Yes
と答える確率で昇順でソートしておく.このソートによって,一般性が失われることはない.今,tie
になる確率が最大になるメンバーを選べたと仮定する(もし複数の組み合わせがある場合にはその中でもindexの和が最も小さい1つを選んだと仮定しよう).そして,上でも書いたようにindexの最初から人と,indexの末尾から人選んできた時を考える.そして,index番号について,がメンバーに入っていて,とがメンバーに入っていないとする.そして,このとき3つの値の大小関係がだとする.
他のすべてのメンバーを固定して,tie
になる確率を のYes
と答える確率の関数として考えることにすると,この関数は線形になる.その傾きが0の時には,tie
になる確率にの確率が影響がないということになるので,tie
になる確率が同じになる時にはできるだけindexの和が小さいものをえらぶのなら,を選んだほうが良いということになるので,はできるだけ先頭の方に寄る事になる.また,傾きが正なら,できるだけ確率が高いものを選ぶべきということになるので,よりもを選んだほうが確率が高くなる.よって,はできるだけ末尾に寄る.傾きが負ならその逆で先頭に寄る.よって,このように前後にどちらもメンバーに入らないようなを選ぶのは最適ではないということが分かる.
よって,ソートにかかる計算量がで,選ぶ組み合わせを通り試し,その1つにかかる計算量がであるから,全体としてはということになる.
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second int main() { int T; cin >>T; rep(t,T) { int n,k; double p[200]; cin >>n >>k; rep(i,n) scanf(" %lf", &p[i]); sort(p,p+n); double ans=0; //左からi人,右からk-i人とる for(int i=0; i<=k; ++i) { vector<double> q; for(int j=0; j<i; ++j) q.pb(p[j]); for(int j=n-k+i; j<=n-1; ++j) q.pb(p[j]); //i人目まで投票終わり,Yes-No値j(200がevenとする) double dp[201][401]={0}; //初期値 dp[0][200]=1.0; rep(x,k) { for(int y=1; y<400; ++y) { dp[x+1][y+1]+=dp[x][y]*q[x]; dp[x+1][y-1]+=dp[x][y]*(1.0-q[x]); } } //更新 ans=max(ans,dp[k][200]); } printf("Case #%d: ", t+1); printf("%.10lf\n", ans); } return 0; }