解法
ゲーム木っぽい動的計画法.実はKが十分に大きければ素数が作れない事態になることはなく,2か3を作って爆速で終了に持ち込むことができる.
コード
import java.util.Arrays;
public class PrimeCompositeGame {
public int theOutcome(int N, int K) {
boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i < N + 1; i++) {
if (isPrime[i]) {
for (int j = i * 2; j <= N; j += i) {
isPrime[j] = false;
}
}
}
if (K > 120) {
int cur = N;
int step = 0;
while (true) {
int next = cur - K;
while (next < 0 || !isPrime[next]) {
next++;
}
step++;
if (next == 2 || next == 3) {
break;
}
cur = next;
next = cur - 1;
while (isPrime[next]) {
next--;
}
cur = next;
step++;
}
return step;
}
int[][] dp = new int[N + 1][2];
for (int cards = 2; cards <= N; cards++) {
for (int turn = 0; turn < 2; turn++) {
int maxLose = 0;
int minWin = Integer.MAX_VALUE;
for (int remove = 1; remove <= Math.min(K, cards - 2); remove++) {
int next = cards - remove;
if (!isPrime[next] && turn == 0) {
continue;
}
if (isPrime[next] && turn == 1) {
continue;
}
int opponent = turn == 1 ? 0 : 1;
if (dp[next][opponent] <= 0) {
minWin = Math.min(minWin, -dp[next][opponent] + 1);
} else {
maxLose = Math.max(maxLose, dp[next][opponent] + 1);
}
}
if (minWin == Integer.MAX_VALUE) {
dp[cards][turn] = -maxLose;
} else {
dp[cards][turn] = minWin;
}
}
}
return dp[N][0];
}
}