yukicoder : No.2813 Cookie

実験ゲーで解いてしまった。
https://yukicoder.me/problems/no/2813

問題

N個のクッキーがあり、それぞれ大きさが与えられる。
ここで2人でターン制のゲームを行う。
各自のターンでは以下を行える。

• クッキーを1つ食べる。
• 大きさ2以上のクッキーを、正整数の大きさを持つ2個以上のクッキーに分割する

自分の手番で操作できないと負けとなる。
両者最適手を取るとき、勝者はどちらか。

解法

大きさvのクッキーのGrundy数G(v)は、実験すると以下のようになる。

• v=1,2の時G(v)=1
• v=3,4の時G(v)=2
• vが5以上かつ3で割って1余るとき、G(v)=(N-4)/3+2
• それ以外の時、G(v)=[(N-2)/3]

int T,N,A[202020];

ll G(ll v) {
	if(v<=2) return 1;
	if(v<=4) return 2;
	if(v%3==1) return (v-4)/3*4+2;
	return (v-2)/3*4;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		y=0;
		FOR(i,N) {
			cin>>x;
			y^=G(x);
		}
		if(y==0) {
			cout<<"Bob"<<endl;
		}
		else {
			cout<<"Alice"<<endl;
		}
	}
		
}

まとめ

こういう問題、毎回実験以外で解けない。