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