ラスト15分で実験始めて気が付いて、ラスト10分で実装をはじめ、ラスト6分で通すという綱渡りをしていた。
https://code.google.com/codejam/contest/10224486/dashboard#s=p1
問題
N人の人がいる。
各人がYes/Noの投票をするとき、Yesを投じる確率はP[i]である。
N人中K人を選んで投票させたとき、Yesを投じる人がちょうどK人の半分となる確率の最大値を求めよ。
解法
SmallはK人の選び方を2^N通り列挙し、かつK人中Yesに投じる人を2^K通り総当たりしても間に合う。
その時、どのK人が選ばれたかを見てみるとP[i]の小さい方と大きい方からのみ数人ずつ選ばれることがわかる。
真ん中の人が選ばれたり、飛び飛びに選ばれたりしない。
Largeもこの知見をもとに解くことができる。
小さい方からb人、大きい方からK-b人選ぶケースを総当たりし、うちK/2人yesに投じる確率を求めよう。
bの選び方はK通りで、K/2人yesに投じる確率を求めるDPはO(K^2)なので、全体でO(N*logN + K^3)で解ける。
なぜ確率が両極端な人を選ぶのがいいかを少し考えてみる。
一件確率が0.5に近い人を選ぶのがよさそうだが、そのような人はYes/Noどちらを答えるかわからないので使いにくいともいえる。
むしろYesと答えやすい人とNoと答えやすい人を半々にそろえた方が結果的にYes/Noを均等にしやすい。
実際はP[i]の値にはばらつきがあるので、常に正確に半々が良いとは限らないようだ。
int N,K; double P[1010]; double from[202]; double to[202]; void solve(int _loop) { int f,i,j,k,l,x,y; cin>>N>>K; FOR(i,N) cin>>P[i]; sort(P,P+N); double ma=0; FOR(x,N) { ZERO(from); ZERO(to); from[0]=1; FOR(i,K) { j=(i+x)%N; ZERO(to); FOR(y,201) if(from[y]) { to[y]+=from[y]*(1-P[j]); to[y+1]+=from[y]*P[j]; } swap(from,to); } ma=max(ma,from[K/2]); } _P("Case #%d: %.12lf\n",_loop,ma); }
まとめ
途中散々O(N^3)位のDPを検討して悩んだけど、最終的にはどうにかなったので良かった。
これ両端取るのがいいのは感覚としてはわかるけど、正確に証明するにはどうしたらいいんだろうな。