TopCoder SRM 561 Div1 Medium CirclesGame

さて本命のDiv1 Medium。
本番は最後まで解き切れなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12170

交差しない多数の円に対し、どれか円を選んで内部の点を置くと、その点を含む円は以後利用できなくなる。
２人で交互に上記ステップを繰り返し、手がなくなったら負け。

Nimを使うんだろうとは本番わかったけど、円の内包判定から大小関係の木構造を作ってそこからどうNimに落とし込むかわからなかった。

Editorialを見ると、木構造のrootになる点のNim値のxorを取ればよい。
ある点のNim値は、その点以下の任意の点（およびその親）を削除した場合に残るNim値の最大値+1になる。

あとは、「任意の点を削除した場合」を再帰を使ってガリガリ計算すればよい。
自分の場合はこの多重ループが１発で書けず、AC取るまでだいぶ手こずりました。

class CirclesGame {
	int ins[52][52];
	int parent[52],memo[52];
	int N;
	vector <int> X,Y,R;
	public:
	int INS(int a,int b) {
		if(a==b) return 0;
		ll dist = ((ll)(X[a]-X[b]))*((ll)(X[a]-X[b]))+((ll)(Y[a]-Y[b]))*((ll)(Y[a]-Y[b]));
		if(sqrt(dist)+R[b] <= R[a]+EPS) return 1;
		return 0;
		
	}
	
	int getnim(int cur) {
		if(memo[cur]==-1) {
			int del, nims[50000];
			ZERO(nims);
			FOR(del,N) {
				if(ins[cur][del]==0 && cur != del) continue;
				int tnim=0;
				// delおよびその親dcurに含まれないrootのnimを取る
				int dcur = del;
				while(1) {
					int left;
					FOR(left,N) if(parent[left]==dcur && !ins[left][del] && left!=del) tnim ^= getnim(left);
					if(dcur==cur) break;
					dcur=parent[dcur];
				}
				nims[tnim]++;
			}
			memo[cur]=0;
			while(nims[memo[cur]]) memo[cur]++;
		}
		return memo[cur];
	}
	
	string whoCanWin(vector <int> x, vector <int> y, vector <int> r) {
		X=x;Y=y;R=r;
		N=x.size();
		int a,b,c,d;
		
		FOR(a,N) FOR(b,N) ins[a][b]=INS(a,b);
		FOR(a,N) {
			parent[a]=-1;
			memo[a]=-1;
			FOR(b,N) if(ins[b][a]) {
				int ok=1;
				FOR(c,N) if(ins[b][c] && ins[c][a]) ok=0;
				if(ok) parent[a]=b;
			}
		}
		
		int nim=0;
		FOR(a,N) if(parent[a]==-1) nim ^= getnim(a);
		
		return (nim==0)?"Bob":"Alice";
	}
};

まとめ

Nimのこういう使い方は初めて。こりゃ本番中には解けないな。
でも勉強になりました。