Google Code Jam 2014 Round 1A B問題
Problem Statement
ノード数 $N$ の木が与えられる.
完全二分木とは,あるルートのノード(どのノードでも良い)があって,子供のノードをちょうど $0$ 個か $2$ 個持つような木.
ノードを幾つか削除して $1$ つの完全二分木にしたい.(削除したノードにつながっている枝も削除される)
最小でいくつのノードを削除すれば良いかを求める問題.
残すノードを最大化すると考える.
どのノードをルートにするかは全部試す.
その時,葉から順番に,そのノード以下(そのノードをルートとするツリー)で最大でどのぐらいのノードを残すことができるかを逐次計算していけば良い.
どのノードを残すかは,$1$ つ以下しか子ノードがない場合は残すことはできず,2つ以上子ノードがある場合は,多くのノードを残すことができる方から $2$ つの子ノードを残せば良い.
時間計算量は $O(N^2)$.
ルートを変更するたびに計算し直すのではなく,枝 $(u,v)$ に対して,親を $u$($v$)とした時,$v$($u$)以下で最大いくつのノードを残すことができるかをずっと保存しておけば,合計で $O(N)$ で計算できる.
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1000000000
int N;
int edge[1200][1200], es[1200];
int dp[1200];
int solve(int now, int bef){
int i, j, k;
vector<int> num;
rep(k,es[now]){
i = edge[now][k];
if(i==bef) continue;
num.push_back( solve(i, now) );
}
dp[now] = 1;
if(num.size() >= 2){
sort(num.rbegin(), num.rend());
dp[now] += num[0] + num[1];
}
return dp[now];
}
int main(){
int i, j, k;
int res, tmp;
int T, cnt = 0;
scanf("%d",&T);
while(T--){
fprintf(stderr,"rest %d\n",T);
printf("Case #%d: ", ++cnt);
scanf("%d",&N);
rep(i,N) es[i] = 0;
rep(i,N-1){
scanf("%d%d",&j,&k);
j--; k--;
edge[j][es[j]++] = k;
edge[k][es[k]++] = j;
}
res = INF;
rep(i,N){
rep(j,N) dp[i] = -1;
tmp = solve(i, -1);
res = min(res, N-tmp);
}
printf("%d\n", res);
}
return 0;
}
Current time: 2024年03月28日20時20分04秒
Last modified: 2014年04月26日14時26分18秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2014 GCJ_2014_Round_1A
トップページに戻る
Logged in as: unknown user (not login)