hotpepsiの練習帳

SRM 575

18:53

Div1 Easy (250) TheNumberGameDivOne

問題

• 数nをめぐって2人で交互にゲームをする
• 数nから、1とn以外の約数を引くことができる
• 引けなくなったら負け
• 最適手において先手必勝かどうかを求める

方針

• とりあえず愚直な探索を書く
• 1～100くらいダンプしてみる
• なんか不規則な偶奇判定っぽい
• 8,32,128,...が例外
• 理由はわからないけどそのまま書いて提出
• Passed System Test
• (終了後)
• 1または素数でターンが回ってきたら負け
• 偶数でターンが回ってきて、相手を奇数にできるなら勝ち
• 奇数でターンが回ってきたら、相手を奇数にすることはできず、負け
• 2の累乗の場合のみ、偶数でターンが回ってきても相手を奇数にできない
• 2^(2*n)の場合、相手を2または2^(2*n+1)にすることができ、勝ち
• 2^(2*n+1)の場合は負け
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_575/TheNumberGameDivOne.cpp

結果

o-- 443rd/927 143.01pt rating 1325 -> 1388 (+63)

プラス点だけどいまいち。