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

4bitにっき

ぽよ

Game Theory (HackerRank) : Tower Breakers, Revisited!

問題

Programming Problems and Competitions :: HackerRank
Tower Breakersとルールはほぼ同じ。
Game Theory (HackerRank) : Tower Breakers - 4bitにっき
今度はN個の山の高さがそれぞれ h_{i}となる。

 テストケース数T \leq 100
 N \leq 100
 1 \leq c_{i} \leq 10^6

解法

それぞれの山についてGrundy数を求める。
約数を列挙する時に、 \sqrt{n}までの約数aについて、対になる約数を \frac{n}{a}で得ることで、 O(\sqrt{n})に抑えるテクを使う。
すると 各 h_{i}について、setを使うことまで考慮するとGrundy数が O(m \sqrt{m} \, \log{} m) (m = max(h_{j}の約数の個数))で求まる。
全体で O(T N m \sqrt{m} \, \log{} m)

 2*3*5*7*11*13*17*19 \simeq 10^6なので、mはせいぜい500もなさそう。

実装

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

#define int long long

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

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;
		s.insert(Grundy(i));
		if (i > 1) s.insert(Grundy(n/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;
}