結果

問題 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]);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0