■
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; } }
ほかの例題があったら練習したいねこれ