結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー ゴリポン先生
提出日時 2025-05-13 12:57:55
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 180 ms / 5,000 ms
コード長 932 bytes
コンパイル時間 3,160 ms
コンパイル使用メモリ 203,824 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-13 12:58:00
合計ジャッジ時間 4,712 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://yang33-kassa.jp/yukicoder/yukicoder007/ より
import std;

int N;
int[] primes;
// エラトステネスの篩によってm以上n未満の素数の表を返す
T[] sieve(T)(T m, T n)
{
	T[] primes = new T[](n);
	foreach (i; 2 .. n)
		primes[i] = i;
	for (T i = 2; i*i < n; ++i)
		if (primes[i])
			for (T j = i*i; j < n; j += i)
				primes[j] = 0;
	return primes.remove!(a => a < m).array;
}
int grundy(int n, int[] state)
{
	if (state[n] != -1) return state[n];
	auto se = redBlackTree!int();
	foreach (p; primes) {
		if (n - p >= 2) se.insert(grundy(n - p, state));
		else break;
	}
	int subgame = 0;
	while (subgame in se) subgame++;
	return state[n] = subgame;
}

void main()
{
	// 入力
	N = readln.chomp.to!int;
	// 答えの計算と出力
	primes = sieve(2, N + 1);
	auto state = [-1].replicate(N + 1);
	state[2] = state[3] = 0;
	int ans = grundy(N, state);
	writeln(ans == 0 ? "Lose" : "Win");
}
0