TopCoder SRM 561 Div1 Medium CirclesGame

問題

座標平面上に円がいくつかある。
i番目の円の中心は(x[i], y[i])で、半径はr[i].
円同士が共有点を持つことはない。（ある円がある円の内部にあることはある）

AliceとBobが次のようなゲームをする。

• Aliceが先手。交互に手番をもつ。
• 手番のプレイヤーは、内部に赤い点の含まれて居ない円を一つ選ぶ。
• 選んだ円の真に内部に赤い点を打つ。
• 点が打てなかったプレイヤーが負け。

お互いが最善を尽くすとき、どちらのプレイヤーが勝つかを求めよ。

制約条件

n≦50

方針

r = 0の円は消して考える。
包含関係でグラフを作ると、木になる。

円を選んで内部に赤い点をうつという操作は、
木から一つの頂点を選び、その点から、頂点までのパスを全て消す、
という操作に対応する。

ゲームの勝者はgrundy数を使って求めればいい。
部分木は、根を指定すれば一意に定まる。
パスを取り除いた後、森にわかれるが、それぞれの木のgrundy数のxorを取ればいい。

ソースコード

inline int d2(int x, int y){ return x * x + y * y; }
bool contain(int x, int y, int r, int X, int Y, int R){
	if(r <= R) return 0;
	return d2(x - X, y - Y) < (r - R) * (r - R);
}

int n;
int e[60][60], can[60][60];
int dp[100000];

int grundy(int p){
	if(dp[p] >= 0) return dp[p];
	
	set<int> s;
	//i: 取り除く頂点（部分木のどれかでなければならない）
	rep(i, n) if(can[i][p]){
		int tmp = 0;
		bool use[60] = {};
		//pからiへのパス上の頂点は全て取り除かれる
		rep(j, n) if(can[i][j]) use[j] = 1;
		//残った森を見る。それぞれの木ごとにgrundy数を求め、xorを取る。
		rep(j, n) if(!use[j] && can[j][p]){
			int r = j;
			while(1){
				int nr = -1;
				rep(k, n) if(!use[k] && e[r][k]) nr = k;
				if(nr < 0) break;
				r = nr;
			}
			rep(k, n) if(can[k][r]) use[k] = 1;
			tmp ^= grundy(r);
		}
		s.insert(tmp);
	}
	for(int i = 0; ; i++) if(!s.count(i)) return dp[p] = i;
}

class CirclesGame {
	public:
	string whoCanWin(vector <int> x, vector <int> y, vector <int> r) {
		
		rep(i, x.size()) if(r[i] == 0){
			x.erase(x.begin() + i);
			y.erase(y.begin() + i);
			r.erase(r.begin() + i);
			i--;
		}
		
		memset(dp, -1, sizeof(dp));
		memset(e, 0, sizeof(e));
		memset(can, 0, sizeof(can));
		
		n = x.size();
		//n番という全部の森の親のダミーの頂点を作ると楽。
		rep(i, n) can[i][n] = e[i][n] = 1;
		rep(i, n) rep(j, n){
			if(contain(x[i], y[i], r[i], x[j], y[j], r[j]))
				can[j][i] = e[j][i] = 1;
		}
		//a→b→cという関係があったら、a→c間の辺は取り除く。
		rep(i, n + 1) rep(j, n + 1) if(e[i][j]){
			rep(k, n + 1) if(can[i][k] && can[k][j]) e[i][j] = 0;
		}
		rep(i, n + 1) can[i][i] = 1;
		
		return grundy(n) ? "Alice" : "Bob";
	}
};