hotpepsiの練習帳

SRM 619

着想 | 01:30

Div1 Easy (250) SplitStoneGame

問題

• 複数の山それぞれに何個かの石がある
• 二人で交互にプレイする
• 一つの山を選ぶ
• 残りの山から2つの山を選び、それぞれに1個以上の石を分配する
• この操作ができなくなったほうが負け
• 最適戦略下でどちらが勝つかを判定する

方針

• 残りの山の数が2以下なら負け
• 2つ以上の石がある山がなければ負け
• そうでないときは、ターン毎に山が一つずつ減っていく
• 残りの山が3つになるほうが勝つので、奇数なら勝ち、偶数なら負け
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_619/SplitStoneGame.cpp

結果

o-- 151.83pt 451st/681 rating 1528 -> 1504 (-24)

判定ゲー意外と時間かかった。

http://togetter.com/li/663337