Hatena::Grouptopcoder

blue_jamのTopCoder日記

 | 

2011-09-02

SRM500 Div1 Easy 練習

| 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;
        }
    }
};
 |