Codeforces #156 Div1 C (256 C) Furlo and Rublo and Game

問題

n個のコインの山があり、それぞれa[i]枚のコインが積まれている。
この山を使って二人が次のようなゲームをする。

• 交互に手番をもつ。手番に操作のできなくなったプレイヤーが負け。
• 手番のプレイヤーは山をひとつ選ぶ。この山のコインの数をxとする。
• 手番のプレイヤーは選んだ山のコインの数をx^(1/4)≦y≦x^(1/2)を満たす整数yに変える。
• x=yとなるようなyを選ぶことはできない。

お互いが最善を尽くしたとき、勝利するプレイヤーはどちらか、求めよ。

制約条件

n≦77777
a[i]≦777777777777

方針

grundy数を求める。
のだけど、愚直にメモ化再帰するとTLE.

実験してみると、i枚の山のgrundy数をgrundy(i)としたとき、
grund(i)が変化するのは、iが平方数のすぐ近くでのみなことがわかる。
なので、iを平方数のすぐ近くまで寄せてしまうと、結構速い時間でgrundy(i)が求まる。

それで、複数のa[i]についてgrundy数を求めなければいけないので、
山を小さい順にソートして、尺取するようにする。

以上の工夫で700msくらいで通る。

ソースコード

map<int, int> dp;
int rec(int n){
	int m = sqrt(n);
	n = min(n, m * m + 2);
	if(dp.count(n)) return dp[n];
	
	int b = sqrt(n), a = (int)ceil(sqrt(sqrt(n * 1.0)) - EPS);
	
	set<int> s;
	for(int i = a; i <= b; i++){
		if(i < n) s.insert(rec(i));
	}
	for(int i = 0; ; i++){
		if(!s.count(i)) return dp[n] = i;
	}
}

int cnt[100];
ll in[100000];

int main(){
	
	int n;
	cin >> n;
	rep(i, n) cin >> in[i];
	sort(in, in + n);
	
	int ans = 0;
	int l = 0, r = 0;
	
	rep(i, n){
		int a = (int)ceil(sqrt(sqrt(in[i] * 1.0)) - EPS);
		int b = sqrt(in[i]);
		if(b >= in[i]) b--;
		a = min(a, b + 1);
		
		while(r <= b) cnt[rec(r++)]++;
		while(l < a) cnt[rec(l++)]--;
		
		for(int j = 0; ; j++) if(!cnt[j]){
			ans ^= j;
			break;
		}
	}
	
	cout << (ans ? "Furlo" : "Rublo") << endl;
	return 0;
}