Game Theory (HackerRank) : Game of Stones

問題

Programming Problems and Competitions :: HackerRank
N個の石を持つ山が1つだけある。
2人のプレイヤーは各ターンで2,3,または5個だけ石を取り除くことが出来、先に石を取れなくなった方の負け。
勝つのはどちらか。

解法

Grundy数で殴った。
想定解法は dp[i]=石がi個は勝ちか負けか というDP。

蟻本を読んで初めてGrundy数を学んだ。
(多分)以下の様な性質を満たしていればGrundy数をNimの山のように扱えるので、XORで勝敗が分かる。

Grundy数xについて
・Grundy数が0～x-1である状態に1手で行けて、xには行けない。
・少なくとも、「それ以上操作出来ない負けの状態」ならx=0。

この性質を満たしていればGrundy数が増えてももう一方のプレイヤーが1手で元に戻せるので問題にならない。
Grundy数は、定義より再帰的に求められる。(DPできる)

実装

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

#define int long long

int memo[101];

int Grundy(int n)
{
	if (memo[n] != -1) return memo[n];
	bool s[4] = {};
	int a[] = { 2, 3, 5 };
	for (int i = 0; i < 3; i++)
	{
		if (n < a[i]) continue;
		s[Grundy(n - a[i])] = true;
	}
	int res = 0;
	while (s[res]) res++;
	return memo[n] = res;
}

signed main()
{
	fill(memo, memo + 101, -1);
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		memo[0] = 0;
		int N;
		cin >> N;
		cout << (Grundy(N) ? "First" : "Second") << endl;
	}
	return 0;
}