SRM 472 div1 easy: PotatoGame
解法
結論を言うと, 5 で割った余りが 0 か 2 だと先手の負けで, それ以外は先手が勝ちます。勝ち負け表書いたら気づきました。
理由は, Nim と同じような証明でいけます。
まず 0, 2 で必敗であることは明らかです。あとは n を 5 で割った余りが 0 か 2 の状態からは, 5 で割った余りが 1, 3, 4 のいずれかにしかならず, 5 で割った余りが 1, 3, 4 のいずれかの状態からは, 必ず 5 で割った余りが 0 か 2 になるような遷移が存在することを言えば良いです。
ですが, 4^p は, 5 を法とすると (-1)^p と一致し, これは 1 か -1 のいずれかの値しか取らないことから, 上のことが言えます。
class PotatoGame { public: string theWinner(int n) { if (n%5==0 || n%5==2) return "Hanako"; else return "Taro"; } };