yukicoder : No.153 石の山

無駄なコードを書いてタイムロスしてしまった。
http://yukicoder.me/problems/383

問題

初期状態でN個の石がある山が１個ある。
２人で交互に石を分割するゲームを行う。

２人は各ターンで１個山を選び、石の数を均等に２つまたは３つに分ける。
１個になった山はそれ以上分割できない。
分割できる山がなくなった場合負けとなる。

互いに最適手を取った場合、勝者はどちらか。

解法

石の数に対するGrundy数を数えよう。
Grundy数は過去にyukicoderで登場済みだね。
yukicoder : No.103 素因数ゲーム リターンズ - kmjp's blog

int N;
int grundy[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	grundy[1]=0;
	for(i=2;i<=100;i++) {
		set<int> s;
		s.insert(grundy[i/2]^grundy[(i+1)/2]);
		if(i>=3) s.insert(grundy[i/3]^grundy[(i+1)/3]^grundy[(i+2)/3]);
		while(s.count(grundy[i])) grundy[i]++;
	}
	
	if(grundy[N]!=0) cout<<"A"<<endl;
	else cout<<"B"<<endl;
}

まとめ

何を考えたか、最初愚直探索解を書いてしまった。
「Grundy数の問題は出たことあるので、こんなにオーソドックスなGrundy数の問題が出るわけない」という先入観にしてやられた。