SRM500 Div1 Easy - MafiaGame
問題
n人いてそのうち何人かは追い出したい人を決めている
最初は全員vulnerableな状態から始まり、以下の流れを繰り返す
1) 追い出したい人を決めている人たちは対象がvulnerableならそいつらに投票
2) 他の人たちは順番にvulnerableの人の中で今最も票が少ない人に当確率で投票
3) 得票数が最大の人が1人ならその人が退場して終了、複数いたらその人たち以外はinvulnerableになって次のラウンドへ
各プレイヤーが追い出される確率のうち最大のものを求める
解法
まず追い出したい人リストdに重複する数字が1つもないとき、各ラウンドで必ず全員が1票ずつ得ることになって一生ゲームが終わらないからreturn 0
そうじゃない場合、dで同じ数字が現れる回数の最大値をmx(>=2)、mx回現れる数字の個数をcntとすると、問題の手順2でmxとcntが変わることはないからこのcnt人以外は全員invulnerableになってラウンド2へ進む
ラウンド2以降は手順1で投票するmx*cnt人を除いたn-mx*cnt人が手順2の法則に従って投票し、毎回vulnerableな人数は (n-mx*cnt)%cnt = n%cnt 人に減る
これが最終的に0になったらその後毎回得票数が全員等しくなって永遠に終わらないってことだからreturn 0
1になったらcnt人のうち誰かが追い出されることになり、そういう状況になるのは全員等確率だからreturn 1.0 / cnt
class MafiaGame { public: double probabilityToLose(int n, vector<int> d) { int v[500] = {}; each(i,d) v[i]++; int mx = *max_element(v,v+n), cnt = count(v,v+n,mx); if (mx<=1) return 0; int t = cnt; while (t>1) t = n%t; return (t==0 ? 0 : 1./cnt); } };