yukicoder : No.2285 Make A Unit Square

この事実は有名なのかな…。
https://yukicoder.me/problems/no/2285

問題

(0,0)-(A,B)を対角線とする軸に平行な矩形がある。
ここに対し、2人でターン制のゲームを行う。

自分の手番では、矩形内を貫通する格子点を通るような縦線または横線を引く。
その際、線で区切られた1*1の領域ができると負けである。
両者が最適手を取るときの勝者はいずれか。

解法

G(x) := 長さxの棒のgrundy数
とすると、解はG(A) xor G(B)が0かどうかで決まる。

• G(1)=0
• G(x)=mex(G(i) xor G(x-i))

となるわけだが、愚直にG(x)を求めるとO(x^2)かかる。
G(x)は実は周期性があり、55項目目以降34周期で繰り返すので、xが100程度までG(x)を求めておけば、それ以上のxに対するG(x)をO(1)で計算できる。

int T;
ll A,B;

int G[222];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=2;i<=200;i++) {
		set<int> S;
		for(x=2;x<=i-x;x++) S.insert(G[x]^G[i-x]);
		while(S.count(G[i])) G[i]++;
	}
	
	
	cin>>T;
	while(T--) {
		cin>>A>>B;
		
		if(A>55) A-=(A-55)/34*34;
		if(B>55) B-=(B-55)/34*34;
		x=G[A]^G[B];
		if(x) {
			cout<<"First"<<endl;
		}
		else {
			cout<<"Second"<<endl;
		}
		
	}
}

まとめ

これ周期性があるって知識で知っておくべきなのか、試行錯誤でわかるもんなのか…。