hotpepsiの練習帳

SRM 701

21:41

https://competitiveprogramming.info/topcoder/srm/round/16822/div/1

Div1 Easy (300) PartisanGame

問題

• N個の石の山から、二人のプレーヤーが交互に石を取っていくゲーム
• 各プレーヤーには、取ることができる石の個数の配列が与えられる
• 1ターンにおいて、プレーヤーは、許可された個数だけ石を取ることができる
• 石を取れない場合は負け
• 勝つのが先手か後手かを求める

方針

• 法則が謎なので、とりあえず全探索して試す
• どうも周期性があるっぽい
• 残り0～1000個のときの結果を求めておく
• あるTについて、2周目(T+1～T×2)と3周目(T×2+1～T×3)の結果が同じなら、周期はTターン
• Nが大きいときは、N <- (N % T) + Tとする
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_701/PartisanGame.cpp

結果

o-- 136.90pt 119th/360 rating 1317 -> 1416 (+99)

周期性の理由はわからなかったけど結果オーライ

https://togetter.com/li/1041241