結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー ゴリポン先生
提出日時 2023-09-13 09:22:35
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 1,585 bytes
コンパイル時間 5,104 ms
コンパイル使用メモリ 172,268 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-30 19:08:48
合計ジャッジ時間 6,459 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;

import std;
// https://qiita.com/drken/items/ecd1a472d3a0e7db8dce より
bool[] isPrime, isPrimeSmall;
// K以上N以下の素数とそのハッシュを計算して入れる
int[] primes, hashes;
// [a, b)の整数に対して篩をかける。isPrime[i - a] == true ⇔ iが素数
void segmentSieve(int a, int b)
{
	for (int i = 0; i * i < b; i++) isPrimeSmall[i] = true;
	isPrime[0 .. b - a] = true;

	for (int i = 2; i * i < b; i++) {
		if (!isPrimeSmall[i]) continue;
		// [2, √b)の篩
		for (int j = 2 * i; j * j < b; j += i) isPrimeSmall[j] = false;
		// [a, b)の篩
		for (int j = max(2, (a + i - 1) / i) * i; j < b; j += i) isPrime[j - a] = false;
	}
}
// 整数の各桁を1桁になるまで足す
int calcHash(int x)
{
	while (x >= 10) {
		x = x.to!string.map!"a-'0'".sum;
	}
	return x;
}
void main()
{
	// 入力
	int K = readln.chomp.to!int;
	int N = readln.chomp.to!int;
	isPrime = new bool[](N + 2);
	isPrimeSmall = new bool[](450);	// √200_000 = 447.213…
	// 答えの計算と出力
	segmentSieve(K, N + 1);
	foreach (i; K .. N + 1) {
		if (!isPrime[i - K] || i == 1) continue;
		// iとiのハッシュを配列に追加
		primes ~= i;
		hashes ~= calcHash(i);
	}
	// しゃくとり法
	int r = 0, maxLen = 1, ans, len = cast(int)hashes.length;
	int[int] hashList;
	foreach (l; 0 .. len) {
		while (r < len && (hashes[r] !in hashList || hashList[hashes[r]] <= 0))
			hashList[hashes[r++]]++;
		if (maxLen <= r - l + 1) {
			ans = l;
			maxLen = r - l + 1;
		}
		if (r == l)
			r++;
		else
			hashList[hashes[l]]--;
	}
	writeln(primes[ans]);
}
0