TopCoder SRM 624 Div2 Hard GameOfSegments

これも典型問題かな？
http://community.topcoder.com/stat?c=problem_statement&pm=13204

問題

N個の点が２次元座標上で凸多角形を成すように配置されている。
ここで２人で交互にターンを迎えるゲームを行う。

各ターンでは、２点を選んで線分を引く。その際：

• １度使われた点は２度以上使えない。
• 他の線分と交差してはならない。

上記条件を満たす２点が選べない場合、負けとなる。

２人が最適手を取った場合、勝者はどちらか。

解法

典型的なGrundy数問題。
N個の点があるとき、２点を選ぶとその線分によりN点は、内部に線分を含まないx個と(N-2-x)個の点に分けられる。
よってN個の点からはGrundy数Grundy(x)^Grundy(N-2-x)に遷移可能である。
Grundy(N)は、そこから遷移できないGrundy数のうち最小の値となる。

Grundy(N)==0なら後手、それ以外は先手の勝ち。

class GameOfSegments {
	public:
	int winner(int N) {
		int i,j,k;
		int gr[1001], me[1001];
		ZERO(gr);
		gr[2]=gr[3]=1;
		for(i=4;i<=1000;i++) {
			ZERO(me);
			FOR(j,i) {
				k=i-2-j;
				if(j<=k) me[gr[j]^gr[k]]++;
			}
			while(me[gr[i]]) gr[i]++;
		}
		return (gr[N]==0)?2:1;
	}
}

まとめ

Div2 Hardの割に、典型すぎる問題。