裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Round2 B - Red Tape Committee

問題

Dashboard - Round 2 2016 - Google Code Jam

問題概要

N人の人がいる.そして,YesNoかで投票をしてもらい多数決をしようとしている.人i(0 \le i \le N-1)に関して,Yesに投票する確率がp_iである(つまり,Noに投票する確率は1- p_i).

今,この中からK人を選んでそのK人に投票してもらうことにした.このとき,YesNoの投票数が同じになる(この状況をtieと呼ぶ)確率が最も高くなるようにK人を選んだ時のtieになる確率を求めよ.

  • 2 \le N \le 200
  • 2 \le K \le NKは偶数
  •  0 \le p_i \le 1

イデア

問題として,K人として誰を選ぶべきなのかということ,そして確率をどのように効率よく計算していくかという二点について考える必要がある.

確率を効率よく計算するためには,選んだK人が決まっているならば(今何人目,Yes-の数Noの数)というのを保存しながらDPをしていけばO(K^2)で計算することが可能である.

それでは,どのようにN人からK人を選べばよいか考えていく.できるだけ「中庸な」,つまり確率が0.5に近い人からK人を選んでいけば良いんじゃないかという感じがするが,実はその逆で,できるだけ0.5からから離れている人からK人を選ぶのが実は最適である.M人を0にできるだけ近い方から選び,K-M人をできるだけ1に近い方から選ぶということを考える.これが正しいのか,直感的には正しそうな感じがする(0.5の人を2人選ぶよりは,0と1を選んだほうがtieになる確率の方が高いのはすぐわかる).この正当性を証明したい.以下背理法で示す.

まず,Yesと答える確率で昇順でソートしておく.このソートによって,一般性が失われることはない.今,tieになる確率が最大になるメンバーを選べたと仮定する(もし複数の組み合わせがある場合にはその中でもindexの和が最も小さい1つを選んだと仮定しよう).そして,上でも書いたようにindexの最初からM人と,indexの末尾からK-M人選んできた時を考える.そして,index番号について,Xがメンバーに入っていて,YZがメンバーに入っていないとする.そして,このとき3つの値の大小関係がY \lt X \lt Zだとする.

他のすべてのメンバーを固定して,tieになる確率をXYesと答える確率の関数として考えることにすると,この関数は線形になる.その傾きが0の時には,tieになる確率にXの確率が影響がないということになるので,tieになる確率が同じになる時にはできるだけindexの和が小さいものをえらぶのなら,Xよりも[tex:Yを選んだほうが良いということになるので,Xはできるだけ先頭の方に寄る事になる.また,傾きが正なら,できるだけ確率が高いものを選ぶべきということになるので,XよりもZを選んだほうが確率が高くなる.よって,Xはできるだけ末尾に寄る.傾きが負ならその逆で先頭に寄る.よって,このように前後にどちらもメンバーに入らないようなXを選ぶのは最適ではないということが分かる.

よって,ソートにかかる計算量がO(NlogN)で,選ぶ組み合わせをK通り試し,その1つにかかる計算量がO(K^2)であるから,全体としてはO(NlogN)+O(K^3)ということになる.

実装(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;
}