Yukicoder012 限定された素数

問題概要

使用しなければならない数字の集合が与えれる。 連続する区間$[K,L]$に含まれる全ての素数について、使用していい数字を全て使用しかつ、それ以外の数字が使われていないとき、
区間長の最大値を求めよ。

$K,L\leqq5*10^6$

yukicoder012

解法

しゃくとりすればよく、 右側一つ伸ばして、左側を条件を満たすまで縮めれば良い。 縮める動作は毎回検査しているけど、右側を伸ばしたときに余計な数字が入ってしまったときは余計な文字が入らないように左の区間は右まで持ってくるのが正しそう。

計算量:$O(L)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    #define primeN 5000006 
    bool prime[primeN + 1];// 外部だとハッシュ表みたいになる
    void make_prime() {
        FOR(i, 0, primeN + 1) {
            prime[i] = 1;
        }prime[0] = prime[1] = 0;
    
        for (int i = 2; i <= primeN; i++) {
            if (prime[i]) {
                for (int j = i * 2; j <= primeN; j += i)
                    prime[j] = 0;
            }
        }
    }
    #undef primeN 
    
    LL N;
    
    LL ans = 0LL;
    
    void change(VI& cnt, int n, int add) {
        while (n) {
            cnt[n % 10] += add;
            n /= 10;
        }
    }
    
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI a(N);
        VI mustuse(10, 0);
        FOR(i, 0, N) {
            cin >> a[i];
            mustuse[a[i]] = 1;
        }
        make_prime();
        int i = 1; int j = 1;
        VI usecnt(10, 0);
        ans = -1;
        while (j <= 5000000) {
            if (prime[j]) {// 右をのばす
                change(usecnt, j, 1);
            }
    
            bool much = 0;
            do {
                FOR(k, 0, 10) {// 条件を満たすまで縮める
                    if (!mustuse[k] && usecnt[k]) {
                        much = 1;
                    }
                }
                if (much) {
                    while (!prime[i] && i < j)i++;
                    change(usecnt, i, -1);
                    i++;
                }
            } while (much && i < j);
    
            // 少なくとも余分な数字がはいのでここで完全なら
            bool ok = 1;
            FOR(k, 0, 10) {
                if (mustuse[k] && !usecnt[k]) ok = 0;
            }
            if (ok) {
                ans = max((int)ans, j - i);
            }
    
            j++;
        }
    
        cout << ans << "\n";
    
        return 0;
    }