Google Code Jam 2014 Round 1A B問題 - Full Binary Tree

Source

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)$ で計算できる.

C++によるスパゲッティなソースコード

#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: 2017年09月21日05時14分41秒
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)

ログイン: