問題はこちら
No.249 N言っちゃダメゲーム (2) - yukicoder
問題文中に「このゲームは、NとKが決まったら、先手・後手、どちらが勝つかわかることが知られています」とあるがこれは厳密には誤りで、正しくは"互いに最善手を尽くすなら"という条件が必要。
今回のゲームでは「互いにわざと負けようとする」という可能性があるかもしれないので、少し考える必要がある
・1000ゲーム目
わざと負ける意味は無いので、先攻後攻の選択権を持つプレイヤーが勝つ
・999ゲーム目
999ゲーム目の敗者は1000ゲーム目で必ず勝てるので、このゲームで勝とうが負けようが1勝1敗となり、このゲームの勝敗は最終的な勝数に影響しない
・998ゲーム目
999ゲーム目の勝敗を気にする必要が無いのでこのゲームでわざと負ける意味は無い
なので先攻後攻の選択権を持つプレイヤーが勝つ
……
以下同様に後ろからたどっていくことで、偶数ゲーム目は勝ちにいってよく、その直前の奇数ゲーム目の勝敗によらずあわせて1勝1敗になるので、結局N[i],K[i]によらず500が答え
a;main(){a=!puts("500");}
