問題
http://community.topcoder.com/stat?c=problem_statement&pm=11342&rd=14429
解き方
投票数が一番多い人が最後に残る候補となる。
よってそれがX人だとすると、最後に1人残るのであれば
確率は1/Xとなる。
最後に一人残るかどうかの判定は、NをX人で割った余りを更新していき
割り切れるのであれば全員消滅してしまうので答えは0になる。
最後に1人残れば上記の確率を返す。
コード
class MafiaGame {
public: double probabilityToLose(int N, vector<int> decisions) {
map<int,int> m;
FORE(i,0,decisions.size())m[decisions[i]]++;
int mx=0,cnt=0;
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
mx=max(mx,it->second);
}
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
if(mx==it->second)cnt++;
}
if(mx==1)return 0.0;
double ret=1.0/cnt;
while(cnt>1){
if(N%cnt==0)return 0.0;
cnt=N%cnt;
}
return ret;
}
};
public: double probabilityToLose(int N, vector<int> decisions) {
map<int,int> m;
FORE(i,0,decisions.size())m[decisions[i]]++;
int mx=0,cnt=0;
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
mx=max(mx,it->second);
}
for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
if(mx==it->second)cnt++;
}
if(mx==1)return 0.0;
double ret=1.0/cnt;
while(cnt>1){
if(N%cnt==0)return 0.0;
cnt=N%cnt;
}
return ret;
}
};