BOJ 32363 피라미드 게임

문제 링크입니다.

막 내리다 보면

게임의 시작부터 끝까지의 모든 과정 동안, X가 적힌 칸은 그 아래 피라미드의 칸들로 X를 전파한다고 생각할 수 있습니다. 피라미드의 꼭대기부터 내려가면서 각 칸의 전파 이후의 X 값을 아래로 전파하는 작업을 반복하면서 XOR 값을 구해주면 스프라그-그런디 정리를 쓸 수 있습니다.

빨리 전파하기

그래서 구간 XOR을 빨리 하는 게 문제가 됩니다. 사각형 범위였다면 imos법을 이용해 쉽게 할 수 있었겠지만 삼각형 구간에서 업데이트를 해야 해서 조금 더 생각이 필요합니다.

삼각형을 처리하기 위해, 왼쪽 끝과 오른쪽 끝을 따로 관리하면서 내려 주면 총 시간복잡도 $\mathcal{O}(N^2)$에 문제를 해결할 수 있습니다.

코드

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

int Lxor[2345][2345], Rxor[2345][2345];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; while(T--){
		int n, k; cin >> n >> k;
		int ans = 0, tmp = 0;
		for(int i = 1; i <= n; i++) for(int j = 1; j <= i+1; j++) Lxor[i][j] = Rxor[i][j] = 0;
		for(int i = 1; i <= n; i++){
			tmp = 0;
			for(int j = 1; j <= i; j++){
				tmp ^= Lxor[i][j]^Rxor[i][j];
				Lxor[i+1][j] ^= Lxor[i][j];
				Rxor[i+1][j+1] ^= Rxor[i][j];
				int a; cin >> a; if(a == -1) continue;
				a ^= tmp; if(i+k-1 <= n) ans ^= a;
				Lxor[i+1][j] ^= a; Rxor[i+1][j+2] ^= a;
				Lxor[i+k][j] ^= a; Rxor[i+k][j+k+1] ^= a;
			}
		}
		cout << (ans ? "First" : "Second") << '\n';
	}
}