■

ARC038-C 茶碗と豆 -Segment Tree上の二分探索-

才能がないね。悔しい

https://beta.atcoder.jp/contests/arc038/tasks/arc038_c

100点解法

grundy数を使い、遷移は i - C[i] ~ i - 1だけ注目すればOK

104点解法

高速化すべきは遷移にO(N)かかる部分である

ここでseg[i]を「grundy数がiである茶碗の番号の最大値」とする

そして、†Segment Tree上の二分探索†を行う

わけがわからないので、概略を言うと

seg[k * 2 + 1]とseg[k * 2 + 2]の値を見て、深く進んでいく

というイメージです(は？)

seg[i]を求めたいとします

grundy数は[0,N)の中にあるので順番に絞っていきます

もしこのようなgrundy数が[0,N / 2)の範囲にあるとすれば,どのような条件を満たすでしょうか

それは

[0,N / 2)の範囲でのseg最小値がi-C[i]より小さい

です

grundy数の求め方を考えると、範囲に無い数で最も小さい数がgrundy数になるので、この条件になります

これを繰り返し,l + 1 == r を満たしたら終了です

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

vector<int> grundy;


struct Segment{
    vector<int> node;
    int n = 1;

    Segment(int sz){
        while(n < sz) n <<= 1;

        node.resize(n * 2 - 1,-1);
    }

    void update(int i,int x){
        i += n - 1;
        node[i] = x;

        while(i > 0){
            i = (i - 1) / 2;
            node[i] = min(node[i * 2 + 1],node[i * 2 + 2]);
        }
    }

    int get(int limit,int k = 0,int l = 0,int r = -1){
        if(r == -1) r = n;
        if(l + 1 == r) return l;

        if(node[2 * k + 1] < limit){
            return get(limit,2 * k + 1,l,(l + r) / 2);
        }
        return get(limit,2 * k + 2,(l + r) / 2,r);
    }
};


int N;
vector<int> C;
vector<int> A;

int main(){
    cin >> N;
    C.resize(N);
    A.resize(N);

    rep(i,1,N - 1){
        cin >> C[i] >> A[i];
    }

    int gs = 0;
    Segment seg(N + 10);
    seg.update(0,0);
    rep(i,1,N - 1){

        int ok = seg.get(i - C[i]);

        if(A[i] & 1) gs ^= ok;


        seg.update(ok,i);
    }

    if(gs == 0){
        cout << "Second" << endl;
    }
    else{
        cout << "First" << endl;
    }

}

ほかの例題があったら練習したいねこれ