SRM 526 div1 med:PrimeCompositeGame

問題

TopCoder Statistics - Problem Statement

解法

K が小さければ, dp[n][t] = (t の人が数を変更する番の時, 残りの数が n であった場合の, 求める数) という dp で解けます。求める数というのは, もし t が勝てる場合は, 最小ターン数を, 負ける場合は 最大ターン数を -1 倍したもののことです。

この dp はゲーム木探索を dp 化したものを考えれば解くことが出来ます。
問題は K が大きい時ですが, 素数は確率 (1/log N) で出現することを考えると, 素数の間隔はそれほど大きくならなそうです。実際, 474747 までの素数を列挙すると, 素数は 114 以内に次の素数が現れます。

なので, K が十分大きい場合は, 最後の数字が 2 または 3 で終わることを考えると, 先手が必ず勝ちます(N <= 2 の場合を除くが, この場合は答えが 0 なので先手が勝ったとみなしても答えには影響がない)。

なので, 先手はとにかく数を減らす戦略で, 後手はなるべく数を減らさない方針で次の数を選ぶのが最適です。これは貪欲に出来るので, すべての場合が解けることになります。

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i*i <= n; i++) if (n%i == 0) return false;
    return true;
}

const int MAXN = 500000;
bool prime[MAXN];
int dp[MAXN][2];

class PrimeCompositeGame {
public:
    int theOutcome(int N, int K) {
        for (int i = 2; i < MAXN; i++) if (isPrime(i)) prime[i] = true;
        if (K > 120) {
            int turn = 0, step = 0;
            while (1) {
                if (turn == 0) {
                    for (int k = K; k >= 1; k--) {
                        int next = N-k;
                        if (next < 0) continue;
                        if (prime[next]) {
                            N = next;
                            break;
                        }
                    }
                } else {
                    for (int k = 1; k <= K; k++) {
                        int next = N-k;
                        if (next < 0) continue;
                        if (!prime[next]) {
                            N = next;
                            break;
                        }
                    }
                }
                turn ^= 1;
                step++;
                if (N <= 3) break;
            }
            return step;
        } else {
            for (int i = 2; i <= N; i++) {
                for (int t = 0; t < 2; t++) {
                    int winMin = MAXN;
                    int loseMax = 0;
                    for (int k = 1; k <= min(K, i-2); k++) {
                        int nt = t^1;
                        int next = i-k;
                        if (t == 0 && !prime[next]) continue;
                        if (t == 1 && prime[next]) continue;
                        if (dp[next][nt] <= 0) {
                            winMin = min(winMin, -dp[next][nt]+1);
                        } else {
                            loseMax = max(loseMax, dp[next][nt]+1);
                        }
                    }
                    if (winMin == MAXN) dp[i][t] = -loseMax;
                    else dp[i][t] = winMin;
                }
            }
        }
        return dp[N][0];
    }
};