Yukicoder007 プライムナンバーゲーム

問題概要

$N$が与えられる。2人で次のゲームを行う。

・その番のプレイヤーは$N$に対して、「$N$以下（$N$も含む）の素数」のどれかで減算する、 その数を$N’$とすると、$N’$が$0$または$1$になってしまったら、そのプレイヤーの負けである。

・その後$N’$を新たな$N$とし、相手にその数を渡し、以上を繰り返す。

$2≦N\leqq10^4$

yukicoder007

解法

$Grundy$数を知っていれば解ける。 負け状態の定義を踏まえると、$2,3$は負け状態が確定している。 したがってこれ以上の$grundy$数を再帰的に求めていけば良い。

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    #define primeN 10000 
    vector<int>a;
    
    void make_prime() {
        bool prime[primeN + 1];
        FOR(i, 0, primeN + 1) {
            prime[i] = 1;
        }prime[0] = prime[1] = 0;
    
        for (int i = 2; i <= primeN; i++) {
            if (prime[i]) {
                a.push_back((long long)i);
                for (int j = i * 2; j <= primeN; j += i)
                    prime[j] = 0;
            }
        }
    }
    
    LL N;
    
    LL ans = 0LL;
    
    int grundy(int n, VI& state) {
        if (state[n] != -1)return state[n];
        set<int>se;
        FOR(i, 0, SZ(a)) {
            if (n - a[i] >= 2)se.insert(grundy(n - a[i], state));
            else break;
        }
        int subgame = 0;
        while (se.count(subgame))subgame++;
        return state[n] = subgame;
    }
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        make_prime();
    
        VI state(N + 1, -1);
        state[2] = state[3] = 0;
        ans = grundy(N, state);
    
        cout << (ans == 0 ? "Lose" : "Win") << "\n";
    
        return 0;
    }