N人のゲーム参加者からゲームから脱落させる人を1人選びます.
何人かは脱落させたい人がいて,その情報はdecisionsに保存されている.
人を選ぶ方法は以下の通り.
もっとも高確率で当選する人の確立を求める.
何回やっても決定しない場合は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; } } };