読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

Game Theory (HackerRank) : Tower Breakers, Again!

Grundy数 DP 約数列挙

問題

Programming Problems and Competitions :: HackerRank
N個の山がある。
それぞれの山の高さは h_{i}である。
2人のプレイヤーは、それぞれのターンで以下の操作を行う。
・高さがXである山を選び、高さがZであるY個の山に分割する。ただし Y*Z = X, Y > 1。
先に操作出来なくなったほうが負である時、どちらが勝つか。

解法

実はGrundy数には、以下の様な性質がある。(蟻本参照)
いくつかのゲームについてそれぞれのGrundy数が求まっている時、それらのゲームから1つだけ選んで1手ずつ操作する新たなゲームのGrundy数は、各ゲームのGrundy数のXORで表せる。
XOR結果の最上位ビットが立っているゲームのGrundy数をいい感じにいじればXORをより小さい任意の状態に出来るし、どれかのゲームのGrundy数が変わればXOR結果は必ず変わるし、全部のゲームが終了していればXOR結果は0になるので、XOR結果はGrundy数の性質を満たしていることが分かる。

上の性質を使って、ある山を分割した後の状態のGrundy数を求められる。
分割後の山の高さは同じだから、計算も楽。
前回のTower Breakes(
Game Theory (HackerRank) : Tower Breakers, Revisited! - 4bitにっき
)と同じように約数列挙を使って、各 h_{i}Grundy数が O(m \sqrt{m} \, \log{} m) (m = max(h_{j}の約数の個数))で求まる。
全体でも同じく O(T N m \sqrt{m} \, \log{} m)

実装

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

#define int long long

int T, N, H[100];
int memo[1000001];

int Grundy(int n);

int MergeGrundy(int y, int z)
{
	if (y&1) return Grundy(z);
	return 0;
}

int Grundy(int n)
{
	if (memo[n] != -1) return memo[n];
	set<int> s;
	for (int i = 1; i*i <= n && i < n; i++)
	{
		if (n % i) continue;
		if (i > 1) s.insert(MergeGrundy(i, n/i));
		s.insert(MergeGrundy(n/i, i));
	}
	int res = 0;
	while (s.count(res)) res++;
	return memo[n] = res;
}

signed main()
{
	fill(memo, memo + 1000001, -1);
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> N;
		int x = 0;
		for (int i = 0; i < N; i++)
		{
			cin >> H[i];
			x ^= Grundy(H[i]);
		}
		puts(x ? "1" : "2");
	}
	return 0;
}