kmjp's blog

競技プログラミング参加記です

Codeforces #418 Div2 D. An overnight dance in discotheque

Dで配点の割に手間取った。
http://codeforces.com/contest/814/problem/D

問題

2次元座標上でN個の円がある。各円の境界は互いに交差しない。
各円を2つのグループに分ける。両グループに関し、奇数個の円で囲まれた領域の面積の総和の最大値を求めよ。

解法

まず円の包含関係を森として表し、木DPをする。
f(c,mask) := 円cの領域が、両グループですでに囲まれているかどうかがmaskであらわされているときの円cの内部の面積の最大値

cをすでに奇数個の円で囲まれたグループに属させる場合、cの面積は減算されることになる。
それを踏まえて各円どちらのグループに属させた方が面積が最大になるかを子から(小さい円から)求めていこう。

int N;
ll X[1010],Y[1010],R[1010];
double S[1010];
double memo[1010][4];
int P[1010];
vector<int> E[1010];

double dfs(int cur,int mask) {
	if(memo[cur][mask]==0) {
		if(mask==0) {
			memo[cur][mask]=S[cur];
			FORR(e,E[cur]) memo[cur][mask] += dfs(e,1);
		}
		else if(mask==3) {
			memo[cur][mask]=-S[cur];
			FORR(e,E[cur]) memo[cur][mask] += dfs(e,1);
		}
		else {
			double a=S[cur],b=-S[cur];
			FORR(e,E[cur]) a += dfs(e,3);
			FORR(e,E[cur]) b += dfs(e,0);
			memo[cur][mask] = max(a,b);
		}
	}
	return memo[cur][mask];
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	double pi=atan(1)*4;
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>R[i];
		S[i]=pi*R[i]*R[i];
	}
	FOR(i,N) {
		P[i]=-1;
		FOR(j,N) if(R[j]>R[i] && (X[j]-X[i])*(X[j]-X[i])+(Y[j]-Y[i])*(Y[j]-Y[i])<=R[j]*R[j]) {
			if(P[i]==-1 || R[j]<R[P[i]]) P[i]=j;
		}
		if(P[i]!=-1) E[P[i]].push_back(i);
	}
	double ret=0;
	FOR(i,N) if(P[i]==-1) ret+=dfs(i,0);
	_P("%.12lf\n",ret);
}

まとめ

子側から求めようとして混乱してしまった。
親側で何個囲まれてるか考えるのだから、親から囲んだ数の偶奇を伝搬させればシンプルだったね。