SRM500 Div1 Easy(250), Div2 Medium(500) MafiaGame

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