Game Theory (HackerRank) : Chessboard Game, Again!

問題

Programming Problems and Competitions :: HackerRank
Chessboard Game(Game Theory (HackerRank) : A Chessboard Game - 4bitにっき)の駒がk個(k <= 10^3)になったバージョン。

解法

上に貼った問題(Chessboard Game)の時もGrundy数を求めて殴ったので、同じように各駒のGrundy数を求めてXORを取る。(Grundy数のゲームの分割についての性質(Game Theory (HackerRank) : Tower Breakers, Again! - 4bitにっき)を使う)

実装

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_K = 1000, MAX_X = 15, MAX_Y = 15;;

const int dx[4] = { -2, -2, 1, -1 }, dy[4] = { 1, -1, -2, -2 };

int T, K, X[MAX_K], Y[MAX_K];
int memo[MAX_X][MAX_Y];

int Grundy(int x, int y)
{
	if (memo[x][y] != -1) return memo[x][y];
	bool exists[30] = {};
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || MAX_X <= nx || ny < 0 || MAX_Y <= ny) continue;
		exists[Grundy(nx, ny)] = true;
	}
	int res = 0;
	while (exists[res]) res++;
	return memo[x][y] = res;
}

signed main()
{
	fill((int*)memo, (int*)memo + MAX_X*MAX_Y, -1);
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> K;
		int x = 0;
		for (int i = 0; i < K; i++)
		{
			cin >> X[i] >> Y[i]; X[i]--; Y[i]--;
			x ^= Grundy(X[i], Y[i]);
		}
		puts(x ? "First" : "Second");
	}
	return 0;
}