SRM500 div1 250

英語の読解力が低い・・・

問題

N人でマフィアというゲームを行う。
各ターン、N人全員が「弱いと思われる候補者」に投票し、投票数が最大の人が1人ならばその人が負ける。
投票数が最大の人が複数人いる場合、その人たちを「弱いと思われる候補者」の対象として投票しなおす。
今、M個(<=N個)の「投票先の情報」が配列で与えられる。誰の投票先かはわからない。
投票先が「弱いと思われる候補者」に居ない場合、または、(N-M)人の投票先がわからない人の場合、一番投票数が少ない人にいれる。ただし複数人いる場合はその人たちの中から一様ランダムに選んで投票する。
最初のターンは全員が「弱いと思われる候補者」の状態からスタートし、各人の中で負ける確率が一番高い人のその確率を返す。もし、無限ターン行っても負けの人が決まらない場合は確率0.0を返す。

考え方

N人の候補者から投票して、a人になったとする。a=1なら負けの人が決まるので1.0で終了。
a人は同票数で、a人以外に投票されてた票が次のターンではa人に均等に投票される。
均等に投票されるので、a人に投票すると、N%a人が1票多い状態になる。
b=N%a人が次の候補者なので、同様にN%b人が1票多い状態になって次の候補者になる。
これを繰り返してN%x=0になる場合、無限ターン行うことになる。N%x=1ならば候補者が決まる。
候補者が決まる場合、その候補者はa人のうちどれかだが、どの人も等しく選ばれる可能性があるので、結局、確率1.0/aが答えになる。

反省

「弱いと思われる候補者の配列」の解釈を間違っていた。(投票順番が関係すると思ってた)