Google Code Jam 2014 Round 1A : B. Full Binary Tree

ちょっと手こずったけど何とか解けてよかった。
https://code.google.com/codejam/contest/2984486/dashboard#s=p1

問題

木構造のグラフが与えられる。
幾つかの頂点を削除して二分木を作りたい。
最少何個の頂点を削除すれば二分木ができるか。

解法

Small解法

頂点数N<=15と小さいので、bitmaskで残す頂点を決め、各頂点をrootとして二分木かどうかチェックすればよい。
実際本番はこうした。

Large解法

各頂点をrootとしてそれぞれ二分木を構築できるようDFSする。
各頂点につながる子の数が：

• 0個なら何もしない
• 1個なら、子およびその子孫を削除する
• 2個なら、両方の子も二分木になるようDFSした上で、今見ている頂点はそれ以上いじらない
• 3個以上なら、それぞれの子も二分木になるようDFSした上で、二分木にするコストが低い頂点を２個残し、残りを削除する。

最後の２個選ぶ処理は、各頂点で「二分木にするコスト - 全部切り落とすコスト」が小さいものを２個残せばよい。

ここでソート処理が生じるのでrootの総当たりがN通り、DFSがN通りの他ソートでN*logNのコストがかかるのでO(N^2*logN)かかる。
１テストケース１秒程度かかる場合もあるが、なんとか時間内に間に合う。
実際は同じ頂点の処理を何度も行うので、メモ化すればもっと速くなる。

int N;
vector<int> E[1001];
int D[1001],ND[1000];

int dfs(int cur,int pre) {
	int i,tot=0,nu=0,x;
	ND[cur]=1;
	
	vector<pair<int,int> > V;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		V.push_back(make_pair(dfs(tar,cur),tar));
		ND[cur]+=ND[tar];
	}
	if(V.size()==0) return 0;
	if(V.size()==1) return ND[V[0].second];
	if(V.size()==2) return V[0].first+V[1].first;
	
	tot=0;
	FOR(x,V.size()) tot+=ND[V[x].second];
	vector<int> V2;
	FOR(x,V.size()) V2.push_back(V[x].first-ND[V[x].second]);
	sort(V2.begin(),V2.end());
	return tot+V2[0]+V2[1];
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) E[i].clear();
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	int ret=N;
	FOR(i,N) {
		ZERO(ND);
		ret=min(ret,dfs(i,-1));
	}
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

メモ化しなかったので時間が間に合うか心配だったけど、無事間に合ってよかった。