TopCoder SRM 701 Div2 Hard ThueMorseGame

まーたゲームやってるよ。
https://community.topcoder.com/stat?c=problem_statement&pm=14429

問題

2人でN個の石を交互に取り合うゲームを行う。
各自の手番では、残った石から1～M個の石を取ることができる。
ただし、取り沿いた後の石の数は、2進数表記で1が偶数個となる値でなければならない。
自分の手番で石を取り除けない場合、その人が負ける。

互いに最適手を取るとき、勝者はどちらか。

解法

最後の2進数表記の話が無ければ、よくある石取りゲームである。
相手の直前の手に対して和を(1+M)とするように取ることで、Nが(1+M)の倍数なら後手必勝、それ以外先手必勝となる。

http://www004.upp.so-net.ne.jp/s_honma/relax/stone.htm
http://www.ise.chuo-u.ac.jp/ISE/outline/Gmajor/matsui/contents03.html

これを少しアレンジして、(1+M)石を取ると残った石の数が条件を満たさない場合、和が(2+M)となるように取ればよい。
そうして石の和を取っていったとき、Nを経由するなら後手必勝。

なお、Mが2以下の場合のみ例外。
「2進数表記で1が奇数個となる値」は2整数で連続するケースがある。
その際はいずれの手番でもこの2整数を超えることができない。
このケースは愚直に総当たりすればよい。
すぐにそのような2整数にぶつかるので、総当たりの組み合わせはわずか。

class ThueMorseGame {
	public:
	
	int win(int n,int m) {
		for(int i=1;i<=m;i++) if(__builtin_popcount(n-i)%2==0 && win(n-i,m)==0) return 1;
		return 0;
	}
	
	string get(int n, int m) {
		int cur=0;
		if(m<=2) return (win(n,m))?"Alice":"Bob";
		
		while(cur+m+1<=n) {
			cur+=m+1;
			while(__builtin_popcount(cur)%2==1) cur++;
		}
		return (cur==n)?"Bob":"Alice";
	}
}

まとめ

こいつらいつもゲームやってんな。