SRM500 Div1 Easy(250), Div2 Medium(500) MafiaGame
decisionsの要素ごとに個数を数える。最大個数が1個ならば、vulnerableな人数はN人のままなので答えは0。それ以外の場合、第2ラウンドでvulnerableになるのはdecisionsに含まれる個数が最大の人達で、その人達に区別は無いので、以降のラウンドのvulnerableな人数を考えれば良い。途中で人数が変わらなくなれば答えは0。
#include <vector> #include <algorithm> using namespace std; class MafiaGame{public: double probabilityToLose( int N, vector <int> decisions ) { vector<int> v(N); for ( int i=0; i<(int)decisions.size(); i++ ) v[decisions[i]]++; int m = *max_element(v.begin(),v.end()); int mn = count(v.begin(),v.end(),m); int t = mn; while ( t>1 ) t = N%t; return t==0||m==1 ? 0 : 1./mn; }};