Hatena::Grouptopcoder

hotpepsiの練習帳

2017-01-03

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

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170103