TopCoder SRM 493 Div 1 Easy StonesGame

問題概要

N個の石が一列に並んでいて、M個目だけが白で他は黒。
二人のプレイヤーが、手番に白石が入っている連続するK個の石を逆順にするゲームをする。
最初にL番目に白石を置いたプレイヤーが勝ちである。

お互いが最善の戦略を取ったときどちらが勝つか求めよ。
N≦100万とする。

解法

3手以上ゲームが長引くなら勝者はない。
なぜなら、相手と同じ区間を選べば、相手の番にまた同じ盤面が来て無限ループさせることができるため。

1手目でLに白石を移動させらるなら先手の勝ち。
そうでないとき、反転の仕方を全て試して、どれも先手が負けるなら後手勝ち、そうでないなら引き分けである。

1手でLに白石を移動させられるかはO(1)で判定できる。
まず、LとMの距離がK未満であること、かつM-L+1とKの偶奇が一致することが必要条件。
それから、L,Mを対称になるよう長さKの区間に入れたときに、両端が1以上N以下に収まれば必要十分である。

●●○●●▲●●
　└────┘←大きさK
○を▲に移動させたいとき、こういう区間が取れれば良い。

上の説明で言っているのは、Kの中で○と▲が対称にできるか（偶奇が一致しないとダメ）、
また、対称にしたときにKが両端の石からはみ出ないかということ。

ソースコード

bool can(int N, int M, int K, int L){
	if(M>L){
		M=N-M+1;
		L=N-L+1;
	}
	if(L-M>=K||(L-M+1)%2!=K%2)return 0;
	if(K%2){
		return 1<=(M+L)/2-K/2&&(M+L)/2+K/2<=N;
	}
	return 1<=(M+L+1)/2-K/2&&(M+L)/2+K/2<=N;
}
class StonesGame {
	public:
	string winner(int N, int M, int K, int L) 
	{
		if(can(N,M,K,L))return "Romeo";
		bool notlose=0;
		for(int i=1;i<=N;i++){
			if(i+K-1<M)continue;
			if(i>M||i+K-1>N)break;
			int m=2*i+K-M-1;
			if(!can(N,m,K,L))notlose=1;
		}
		return notlose?"Draw":"Strangelet";
	}
};