kmjp's blog

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

Codeforces #322 Div2 F. Zublicanes and Mumocrates

本番方針はあっていたけど、しょうもないバッファオーバーフローで落ちた。
http://codeforces.com/contest/581/problem/F

問題

N頂点の木を成すグラフが与えられる。
この木の葉は偶数である。

各頂点を白黒2色で塗り分けることを考える。
その際、葉となる頂点は白黒同数となるようにしたい。

上記条件を満たす塗り分け方において、白頂点と黒頂点を結ぶ辺の数の最小数を求めよ。

解法

仮に初期状態で全頂点白とする。
葉でない頂点から初めてDFSを行い、「以下のsubtreeの頂点をすべて白黒反転する/しない」場合に、subtreeにおける白黒な葉頂点の差を計算していく。
そして白黒葉頂点数の差ごとに、必要な反転回数の最小値を求めるDPをしていけば良い。

一見O(N^3)でO(N^2)で終わるタイプの木DP。

int N,D;
vector<int> E[5050];
int mi[5050];
int ma[5050];
int dp[5050][7100];

void dfs(int cur,int pre) {
	
	// last
	if(E[cur].size()==1) {
		dp[cur][3000+1]=0;
		mi[cur]=ma[cur]=1;
	}
	else {
		dp[cur][3000+0]=0;
		mi[cur]=ma[cur]=0;
		int x,y;
		FORR(tar,E[cur]) if(tar!=pre) {
			int tmp[7000];
			FOR(x,7000) tmp[x]=10000000;
			dfs(tar,cur);
			for(x=mi[cur];x<=ma[cur];x++) if(dp[cur][3000+x]<1000000) {
				for(y=mi[tar];y<=ma[tar];y++) if(dp[tar][3000+y]<1000000) {
					if(x+y<=D/2 && x+y>=-D/2) tmp[3000+x+y]=min(tmp[3000+x+y],dp[cur][3000+x]+dp[tar][3000+y]);
					if(x-y<=D/2 && x-y>=-D/2) tmp[3000+x-y]=min(tmp[3000+x-y],dp[cur][3000+x]+dp[tar][3000+y]+1);
				}
			}
			
			mi[cur]=max(-D/2, min(mi[cur]+mi[tar],mi[cur]-ma[tar]));
			ma[cur]=min(D/2,max(ma[cur]-mi[tar],ma[cur]+ma[tar]));
			for(x=mi[cur];x<=ma[cur];x++) dp[cur][3000+x]=tmp[3000+x];
		}
	}
	int x;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	memset(dp,0x7f,sizeof(dp));
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	int st=N+1;
	FOR(i,N) {
		if(E[i].size()==1) D++;
		else st=min(st,i);
	}
	if(D==2) return _P("1\n");
	dfs(st,-1);
	cout<<dp[st][3000]<<endl;
}

まとめ

Eよりだいぶ楽。