TopCoder/SRM500/MafiaGame

出展 †

• TopCoder SRM500(Div1 Easy/Div2 Medium) (問題文)

問題 †

N(≦500)人でゲームを行う．
N人中M(≦N)人は誰に投票するかを決めており，そのリストがdecisionsとして与えられる．
投票対象になる人のリスト"vulnerable"には初めN人全員が含まれるとして，以下のようにゲームを進める．

• まずdecisionsで投票する人を決めている人のうち，投票する人がvelnerableに含まれている人が投票を行う．
• 前ステップで投票を行わなかった人が順に，その時点で最も得票が少ない人からランダムに1人を選び投票する．
• 得票数が最も多い人のみをリストvelnerableに残す．
• velnerableに1人だけが残ったらその人の負けとし，そうでなければ最初のステップに戻る．

このとき，負ける確率が最も高い人の，負ける確率を求めなさい．
決着がつかない場合は0.0を返しなさい．

解法 †

• 問題の性質を整理すると
  • 1回目の投票で最多票になる人はdecisionsで決められた投票で最多票になる人
  • decisionsで2票以上得る人がいなければ全員が1票になり決着がつかない
  • 2回目以降は，(残り人数 mod decisionsで投票されない人の数)人が残る
  • これが途中で0になる場合は全員の得票数が同じになるので決着がつかない
  • 1回目の投票の結果残る人は全員条件が同じなので，最後に1人になる確率も同じ

• 以上から解法は，
  • decisionsで(2票以上の)最多票を得る人の数Cを求める
  • 2票以上得る人がいなければ0.0を返して終了
  • 2回目の投票以降の残り人数の推移を最後の1人になるまでシミュレーションする
  • 途中で0になった場合は決着がつかないので0.0を返して終了
  • 決着がつくことが確認できたので，求める確率である1/Cを返す

回答 †

• MafiaGame_pes.cpp -↑解法準拠(pes)