mayoko’s diary

プロコンとかいろいろ。

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";
    }
};