blue_jamのTopCoder日記

SRM500 Div1 Easy 練習

SRM, Practice | 18:12

概要

N人のゲーム参加者からゲームから脱落させる人を1人選びます．

何人かは脱落させたい人がいて，その情報はdecisionsに保存されている．

人を選ぶ方法は以下の通り．

1. 脱落させたい人がいる参加者は，脱落させたい人に投票する．（すでに脱落させる候補にいない場合は下の方法に従う）
2. 脱落させたい人がいない参加者は，投票する時点で最も投票数が少ない参加者に投票する．
3. もっとも得票数が多かった人たちのみを脱落候補に残す．
4. これを繰り返して，1人に決まるまで行う．

もっとも高確率で当選する人の確立を求める．

何回やっても決定しない場合は0.0を返す．

解法

decisionsの出現頻度がもっとも高い人（達）は，1回目に必ず当選する．（1回目では脱落候補の人数=投票する人数であることに注意）

2回目以降は，できるだけ均等に割り振られながら投票される．

よって，Nを脱落候補の人数で割った余りが次の脱落候補に加わる．

Nを脱落候補の人数で割った余りが0なら，無限ループ．

Nを脱落候補の人数で割った余りが1なら，その時点で終了．

その確率は，1回目の投票が終わった時点の脱落候補者分の1．(脱落候補者の中から1人選ぶときの確立．コンビネーションとか使って計算しても同じ結果になるはず．楽な方を選ぼう．）

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <functional>
using namespace std;

class MafiaGame {
public:
    double probabilityToLose(int N, vector <int> decisions) {
        double res;
        int firstNum = 0;
        int cnt = 0;
        int M = N;
        
        sort(decisions.begin(), decisions.end());
        for(vector<int>::iterator i=decisions.begin();i!=decisions.end();){
            vector<int>::iterator next = upper_bound(decisions.begin(), decisions.end(), *i);
            if(firstNum < next - i){
                firstNum = next - i;
                cnt = 1;
            }
            else if(firstNum == next - i){
                ++cnt;
            }
            i = next;
        }
        if(firstNum == 1){
            cnt = N;
        }
        res = 1.0 / cnt;
        M = cnt;
        for(;;){
            if(M == 1){
                return res;
            }
            else if(M == 0){
                return 0.0;
            }
            M = N % M;
        }
    }
};