はまやんはまやんはまやん

hamayanhamayan's blog

EEEEndless gamEEEE [Summer Festival Contest 7]

競技プログラミング

競プロのコード例について補足 競技プログラミング練習問題集 Twitter 競技セキュリティまとめのまとめ

コンテスト: https://hoj.hamako-ths.ed.jp/onlinejudge/contest/106/problems/7
アーカイブ: https://hoj.hamako-ths.ed.jp/onlinejudge/problems/838

前提知識

解法

https://hoj.hamako-ths.ed.jp/onlinejudge/state/25976

とりあえず問題をパッと見てgrundy数っぽいなという印象がある。
grundy数を愚直に計算すれば部分点は貰えそう。
神通力を使ってもう一つ山が作れるという条件があるが、これは1つずつgrundy数を追加してみて、0になるかを全て判定すればいい。
各数についての最小素因数はエラトステネスの篩の要領で用意していけばいい。
　
grundy数計算(部分点)
遷移先全てについてgrundy数を見て、その中に無い最小の非負整数を次のgrundy数とすればいい。
これでギリギリ間に合う

int G[210101], P[210101];
void make_grundy() {
    make_primes(210101);

    rep(p, 0, 210101) P[p] = -1;
    P[1] = 1;
    rep(p, 2, 210101) if (primes[p]) for (int i = p; i < 210101; i += p) if (P[i] < 0) P[i] = p;

    G[0] = 0;
    rep(i, 1, 210101) {
        int p = P[i];
        assert(0 <= p);
        p = min(p, K);

        set<int> s;
        rep(j, 1, p + 1) if (0 <= i - j) s.insert(G[i - j]);
        int g = 0;
        while (s.count(g)) g++;
        G[i] = g;
    }
}

　
grundy数計算(満点)
部分点と方針は全く一緒で「遷移先全てのgrundy数の中で、その中に無い最小の非負整数を取得するクエリ」を高速にする。
部分点ではO(KlogK)ぐらいかかるが、これをO(logK log10^6)くらいに落とす。
公式解説にやり方が書いてある。
区間最小値のセグメントツリーを用意し、i番目には数iが最後に何番目に現れたかを入れておく。
これを使うと、[0,i]の最小値をminとすると、[0,i]の数が[0,min]に存在することが分かり、逆に(min,inf)の区間に[0,i]の数が全部揃ってないことが分かる。
これを使って二分探索することで高速に取得できる。
　
ちなみにei1333さんの解法ではセグメントツリー上での[0,i]を使った二分探索はO(log^2N)ではなくO(logN)で行えるやつがあり、それを使って更に高速化してある（多分）。

vector<bool> primes;
void make_primes(int n) {
    primes.resize(n + 1, true);
    primes[0] = primes[1] = false;
    rep(i, 2, sqrt(n)) if (primes[i]) for (int j = 0; i * (j + 2) < n; j++) primes[i * (j + 2)] = false;
}
#define def INT_MAX/2
template<class V, int NV> struct SegTree { //[l,r]
    V comp(V l, V r) { return min(l,r); };
    vector<V> val; SegTree() { val = vector<V>(NV * 2, -1); }
    V get(int l, int r) { if (l>r)return def;l+=NV;r+=NV+1;V ret=def; while(l<r){
        if(l&1)ret=comp(ret,val[l++]);if(r&1)ret=comp(ret,val[--r]);l/=2;r/= 2;}return ret;}
    void update(int i, V v) { i+=NV;val[i]=v;while(i>1)i>>=1,val[i]=comp(val[i*2],val[i*2+1]); }
    void add(int i, V v) { update(i, val[i + NV] + v); }};
//---------------------------------------------------------------------------------------------------


int N, K, A[101010];
#define CAU "CAUGHT"
#define ESC "ESCAPE"
//---------------------------------------------------------------------------------------------------
int G[1010101], P[1010101];
SegTree<int, 1 << 20> st;
void make_grundy() {
    make_primes(1010101);

    rep(p, 0, 1010101) P[p] = -1;
    P[1] = 1;
    rep(p, 2, 1010101) if (primes[p]) for (int i = p; i < 1010101; i += p) if (P[i] < 0) P[i] = p;

    G[0] = 0;
    st.update(0, 0);
    rep(i, 1, 1010101) {
        int p = P[i];
        assert(0 <= p);
        p = min(p, K);

        int L = max(0, i - p);

        int ng = -1, ok = 1010101;
        while (ng + 1 != ok) {
            int x = (ng + ok) / 2;
            if (L <= st.get(0, x)) ng = x;
            else ok = x;
        }

        G[i] = ok;
        st.update(ok, i);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    make_grundy();

    int g = 0;
    rep(i, 0, N) g ^= G[A[i]];
    if (g == 0) {
        cout << CAU << endl;
        return;
    }

    rep(i, 0, N) if ((g ^ G[A[i]]) == 0) {
        cout << CAU << endl;
        return;
    }

    cout << ESC << endl;
}