結果

問題 No.12 限定された素数
コンテスト
ユーザー ゴリポン先生
提出日時 2025-05-12 20:37:20
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 281 ms / 5,000 ms
コード長 1,301 bytes
コンパイル時間 4,183 ms
コンパイル使用メモリ 164,872 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-12 20:37:32
合計ジャッジ時間 10,679 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

immutable P_MAX = 5_000_005;
bool[P_MAX] isPrime;

void sieve()
{
	isPrime[] = true;
	isPrime[0] = isPrime[1] = false;

	foreach (i; 2 .. P_MAX) {
		if (!isPrime[i]) continue;
		for (int j = 2 * i; j < P_MAX; j += i)
			isPrime[j] = false;
	}
}

void main()
{
	// 入力
	auto N = readln.chomp.to!int;
	auto A = readln.split.to!(int[]);
	sieve();
	// 答えの計算
	auto mustUse = new bool[](10);	// 使わないといけない数字
	foreach (a; A)
		mustUse[a] = true;
	auto cnt = new int[](10);
	// 数 n に使われている数字を増減する
	void change(int n, int add)
	{
		while (n) {
			cnt[n % 10] += add;
			n /= 10;
		}
	}
	int i = 1, j = 1, ans = -1;
	while (j <= 5_000_000) {
		if (isPrime[j])	// 右を伸ばす
			change(j, 1);

		bool much = false;
		do {
			foreach (k; 0 .. 10)	// 条件を満たす間縮める
				if (!mustUse[k] && cnt[k]) much = true;
			if (much) {
				while (!isPrime[i] && i < j) i++;
				change(i, -1);
				i++;
			}
		} while (much && i < j);
		// 少なくとも余分な数字がない場合
		bool ok = true;
		foreach (k; 0 .. 10)
			if (mustUse[k] && !cnt[k]) ok = false;
		if (ok) {
			ans = max(ans, j - i);
		}
		j++;
	}
	// 答えの出力
	writeln(ans);
}
0