BOJ 19526 Cups and Beans

문제 링크입니다.

게임판 분리

한 턴에 하나의 콩만 선택해 옮길 수 있으므로, 각각의 콩이 서로 독립적으로 작동합니다. 스프라그-그런디 정리에 의해, 전체 게임의 그런디 수는 각 콩에 대한 그런디 수의 XOR로 구할 수 있습니다. 이제 각 컵마다 그 컵에만 콩 하나가 들어있을 때의 그런디 수를 구하는 것으로 문제를 해결할 수 있습니다.

구간 MEX 구하기

$i = 1 \cdots N-1$ 에 대해, $i$번 컵의 그런디 수는 구간 $[i-C_i , i-1]$의 그런디 수의 MEX입니다. 그런디 수가 MEX로 계산되기 때문에, 모든 컵의 그런디 수는 $N$을 초과하지 않습니다.

그런디 수를 컵의 번호 순서대로 구하면 구간의 뒤쪽에 해당하는 컵들의 그런디 수는 고려할 필요가 없습니다. 따라서 각 그런디 수마다 해당 그런디 수가 마지막으로 등장한 위치를 관리하면, 처음으로 그 값이 $i-C_i$ 미만인 그런디 수를 찾는 것으로 구간의 MEX 값을 구할 수 있습니다.

구간의 그런디 수 중 가장 등장한 지 오래된 것의 마지막 등장 위치를 저장하는 세그먼트 트리를 이용하면, 해당 트리 위에서의 이분 탐색으로 원하는 인덱스를 $\mathcal {O}(\lg N)$에 구할 수 있습니다.

따라서 총 시간 복잡도는 $\mathcal{O}(N\lg N)$입니다.

코드

편의 상 트리에서 그런디 수와 컵 번호에 각각 1을 더한 값을 사용합니다.

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int tree[404040];

void upd(int now, int l, int r, int i, int v){
	if(i < l || r < i) return;
	if(l == r){
		tree[now] = v; return;
	}
	upd(now<<1, l, mid, i, v); upd(now<<1|1, mid+1, r, i, v);
	tree[now] = min(tree[now<<1], tree[now<<1|1]);
}

int qry(int now, int l, int r, int t){
	if(l == r) return l;
	if(tree[now<<1] < t) return qry(now<<1, l, mid, t);
	return qry(now<<1|1, mid+1, r, t);
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	upd(1, 1, n, 1, 1);
	int ans = 0;
	for(int i = 2; i <= n; i++){
		int c, a; cin >> c >> a;
		int g = qry(1, 1, n, i-c);
		upd(1, 1, n, g, i);
		if(a&1) ans ^= g-1;
	}
	cout << (ans?"First":"Second");
}