問題

Dashboard - Round 2 2016 - Google Code Jam

問題概要

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

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

$2 \le N \le 200$
$2 \le K \le N$ ， $K$ は偶数
$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の和が最も小さい１つを選んだと仮定しよう)．そして，上でも書いたようにindexの最初から $M$ 人と，indexの末尾から $K-M$ 人選んできた時を考える．そして，index番号について， $X$ がメンバーに入っていて， $Y$ と $Z$ がメンバーに入っていないとする．そして，このとき3つの値の大小関係が $Y \lt X \lt Z$ だとする．

他のすべてのメンバーを固定して，tieになる確率を $X$ のYesと答える確率の関数として考えることにすると，この関数は線形になる．その傾きが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;
}