BOJ 32213 래빗 홀

문제 링크입니다.

문제 요약

$N$개의 구멍에 돌을 넣고 님 게임을 합니다. 이때 돌을 없애는 대신 두 구멍을 합칠 수 있습니다. 새로운 구멍에 들어있는 돌의 개수는 원래 구멍에 들어 있던 돌 개수의 bitwise XOR 값입니다.

행동을 할 수 없게 된 쪽이 패배합니다. 선후공 중 필승 전략이 있는 쪽을 찾으세요.

풀이

구멍을 합치는 행동을 제하면 기본적인 님 게임으로, 각 구멍의 돌 개수의 XOR 값이 0임과 후공 필승이 동치임이 알려져 있습니다. 구멍을 합치는 행동만 케어해 주면 되겠네요.

구멍을 합치면 전체 XOR 값은 결국 변하지 않으므로, 구멍을 합치는 행위를 돌을 제거하는 행위와는 완전히 독립적인 게임으로 간주할 수 있습니다. 구멍 개수의 홀짝성에 따라 0 또는 1로 구멍을 합치는 게임의 그런디 수를 계산할 수 있겠네요.

총 시간 복잡도는 ${\cal O}(N)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; while(T--){
		int n; cin >> n; ll ans = (n-1)%2;
		while(n--){
			int k; cin >> k; ans ^= k;
		}
		cout << (ans?"eerste\n" : "tweede\n");
	}
}