SRM500 Div1Easy MafiaGame

https://community.topcoder.com/stat?c=problem_statement&pm=11342

英弱に悪文当てんな
投票→最大票数の人数で場合分け

1人→敗者が決定しゲームが終了
複数人→vulnerableに入れる→投票→…

ゲームが終わるときは敗者になる確率の最大値を、終わらないときは0を返す。

投票の手順

decisionsに番号がある人は書かれている分だけ得票する
1の後に余っている票はvulnerable内で均等になるように割り当てる

ゲームが終わらないのはvulnerable内の得票数が等しいとき。この判定法は投票1回目と2回目以降で違う。

1回目：vulnerableには $N$ 人全員がいるので、decisionsに重複があるか否か。ない場合、全員の得票数は1となってループ。
2回目以降：手順1終了時点でvulnerable内の得票数は等しいので、残りの票が均等に割り振られればループ。vulnerableの人数を $i$ とするとループの条件は、 $(N - i)\equiv 0\pmod i⇔N\equiv 0\pmod i$

敗者が決まるのは余りが1のときであるから、これをシミュレーションすればよい。敗者は1回目の投票後にvulnerableにいる人のいずれかであり、彼らに区別はない。よって確率は、 $1/i$

#include <bits/stdc++.h>
using namespace std;

class MafiaGame {
public:
   double probabilityToLose( int N, vector <int> decisions ) {
       vector<int> member(N,0);
       for(auto itr=decisions.begin();itr!=decisions.end();itr++){
           member[*itr-1]++;
       }
       sort(member.begin(),member.end()); reverse(member.begin(),member.end());
       // 投票1回目
       int loseVote=0,loseNum=0;
       for(int i=0;i<N;i++){
           int vote=member[i];
           if(vote>loseVote){
               loseVote=vote; loseNum=1;
           }else if(vote==loseVote){
               loseNum++;
           }else{
               break;
           }
       }
       // 敗者の票数が1なので決まらない
       if(loseVote==1) return 0;
       // 投票2回目以降
       int tmp=loseNum;
       while(1){
           if(loseNum==1) return 1.0/tmp;
           if(loseNum==0) return 0;
           loseNum=N%loseNum;
       }
   }
};