Game Theory (HackerRank) : Digits Square Board

問題

Programming Problems and Competitions :: HackerRank
初め、N*Nマスの盤がある。各マスには1から9の数が書かれている。
2人のプレイヤーは、各ターンで以下の操作を行う。
・合成数が少なくとも1つ含まれる、1*1より大きい盤(このゲームにおいては盤が分割される)を1つ選ぶ。
・その盤を垂直か水平に沿って切って、2つの盤に分割する。
先に操作出来なくなったほうが負である時、どちらが勝つか。

解法

Grundy数のゲームの分割の性質(Game Theory (HackerRank) : Tower Breakers, Again! - 4bitにっき)を使う。
累積和を使って座標(0, 0)を左上とする長方形領域について素数の数を求めておくと、任意の長方形領域に含まれる素数の数がO(1)で求まる。
(参考: 惑星探査 Planetary Exploration | Aizu Online Judge)

累積和の前計算は各テストケースについてしかかからないので、DP(メモ化再帰)の計算量を考えると全体では。

実装

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

#define int long long

const int MAX_N = 30;

int T, N, A[MAX_N][MAX_N];
int memo[MAX_N][MAX_N][MAX_N + 1][MAX_N + 1];
int primeSum[MAX_N + 1][MAX_N + 1];

bool IsPrime(int n)
{
	return (n == 2 || n == 3 || n == 5 || n == 7);
}

int Grundy(int ax, int ay, int bx, int by)
{
	if (memo[ax][ay][bx][by] != -1) return memo[ax][ay][bx][by];
	if (primeSum[bx][by] - primeSum[ax][by] - primeSum[bx][ay] + primeSum[ax][ay] == (bx - ax)*(by - ay))
		return memo[ax][ay][bx][by] = 0;
	bool exists[MAX_N*2] = {};
	for (int i = ax + 1; i < bx; i++)
	{
		int ret = Grundy(ax, ay, i, by)^Grundy(i, ay, bx, by);
		if (ret < 2*N) exists[ret] = true;
	}
	for (int i = ay + 1; i < by; i++)
	{
		int ret = Grundy(ax, ay, bx, i)^Grundy(ax, i, bx, by);
		if (ret < 2*N) exists[ret] = true;
	}
	int res = 0;
	while (exists[res]) res++;
	return memo[ax][ay][bx][by] = res;
}

signed main()
{
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		fill((int*)memo, (int*)memo + MAX_N*MAX_N*(MAX_N + 1)*(MAX_N + 1), -1);
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> A[j][i];
			}
		}

		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				primeSum[i][j] = primeSum[i - 1][j] + primeSum[i][j - 1] - primeSum[i - 1][j - 1];
				primeSum[i][j] += IsPrime(A[i - 1][j - 1]);
			}
		}

		puts(Grundy(0, 0, N, N) ? "First" : "Second");
	}
	return 0;
}