TopCoder SRM 526 Div1 Medium: PrimeCompositeGame

解法

ゲーム木っぽい動的計画法.実は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;
				}
			}
		}

		// Kが大きければ100%勝てる
		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;
		}

		// dp[n][t]:= tの手番でn残っている時のincome
		int[][] dp = new int[N + 1][2];
		for (int cards = 2; cards <= N; cards++) {
			for (int turn = 0; turn < 2; turn++) {
				/*
				 * turn=0なら先手番, 1なら後手番
				 */
				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) {
						// nextで相手の負けが確定している場合,自分は勝つので出来るだけ少ないターンになるように選ぶ
						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];
	}
}