ARC038 C 茶碗と豆
問題文概要
二人で交互にターンが回ってくるゲームをする.
$0, \dots, n-1$ の $n$ マスが横並びに並んでおり, 各マス $i$ には駒が $A_i$ 個置いてある.
毎ターン, 駒を一つ選択し, 動かす. 但し, $i$ 番目のマスから動かせる先は, $i-C_i, i-C_i+1, \dots, i-1$ のいずれか.
動かせなくなったプレイヤーの負け. 先手と後手どちらが勝ちか.
制約
$1 \le n \le 10^5$, $1 \le C_i \le i$, $0 \le A_i \le 10^9$, $1 \le \sum A_i$.
解法
駒は独立なので, 独立なゲームを $\sum A_i$ 個同時進行していると思おう.
駒が一つの時, grundy 数を求めればよい. 同時進行しているので, 全ての xor を取れば答え.
但し, grundy 数を求めるのに, $O(n^2 \log n)$ とかかかると死ぬので, ここを高速化する必要がある.
t[x] = grundy数が x な中で最も右の index
と置き, これを更新していく事を考える.
$i-1$ まで処理した時, $i$ の grundy 数 $y$ は,
$$\min_{x < y} t[x] \ge i - C_i$$
を満たす最小の $y$. これを二分探索すればよい.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
template<typename T>
struct SegTree{//{{{
const T zero;
vector<T> tree;
int offset, N;
T propagate(const T &l, const T &r){ return min(l, r); }
SegTree(int n, const T zero = T()) : zero(zero){
N = 1;
while(N < n) N <<= 1;
tree.assign(N*2, zero);
offset = N-1;
}
T at(int i){ return tree[i + offset]; }
void set(int i, const T &x){
i += offset;
tree[i] = x;
while(i){
i = (i-1) >> 1;
tree[i] = propagate(tree[i*2+1], tree[i*2+2]);
}
}
T sum(const int &l, const int &r){ return sum(l, r, 0, 0, N); }
T sum(const int &l, const int &r, const int &k, const int &ll, const int &rr){
if(r <= ll || rr <= l) return zero;
if(l <= ll && rr <= r) return tree[k];
const int mm = (ll + rr) >> 1;
if(r <= mm) return sum(l, r, k*2+1, ll, mm); ////
if(l >= mm) return sum(l, r, k*2+2, mm, rr); ////
return propagate(sum(l, r, k*2+1, ll, mm), sum(l, r, k*2+2, mm, rr));
}
};//}}}
bool solve(){
int n; cin >> n;
vector<int> c(n+1), a(n+1);
rep(i, n) cin >> c[i+1] >> a[i+1];
SegTree<int> seg(n+10, -1);
vector<int> grundy(n+1);
int res = 0;
rep(i, n+1){
grundy[i] = 0;
for(int d = 1<<20; d; d >>= 1)
if(grundy[i]+d < n+10 and seg.sum(0, grundy[i] + d) >= i - c[i])
grundy[i] += d;
seg.set(grundy[i], i);
if(a[i]%2) res ^= grundy[i];
}
cout << (res == 0 ? "Second" : "First") << endl;
return true;
}