yukicoder 0007 プライムナンバーゲーム

概要

$2$人対戦ゲームをする. $N$ が与えられる. プレイヤーには交互にターンが回ってきて, 自分のターンになった時に, $p \le N$ なる 素数 $p$ を選び, $N$ を $N - p$ で更新する. $0$ か $1$ になってしまったら負け.

先手後手のどちらが勝つか判定せよ.

制約

$2 \le N \le 10^4$.

解法

ゲーム木をメモ化再帰で探索.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> ps;
vector<int> memo;
bool dfs(int n){
    int &res = memo[n];
    if(res >= 0) return res;
    if(n == 0 or n == 1) return res = true;
    for(aur p : ps){
        if(p > n) break;
        if(!dfs(n-p)) return res = true;
    }
    return res = false;
}

bool solve(){
    int n;
    cin >> n;
    memo.assign(n+10, -1);
    ps = sieve(n);
    cout << (dfs(n) ? "Win" : "Lose") << endl;
    return true;
}