Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1962-72349b18
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #69 DIV1 C問題/DIV2 E問題 - Beavermuncher-0xFF (この記事を編集する[管理者用])

Source

Codeforces Beta Round #69 DIV1 C問題 (1500pt)
Codeforces Beta Round #69 DIV2 E問題 (2500pt)
Problem description
Beta Round #69 DIV1の自分の参加記録

問題概要

ノード数N (10^5以下) の木が与えられる.
それぞれのノードにいるビーバーの数が与えられる.(各ノード1以上10^5以下)
出発ノードも与えられる.
あるノードからあるノードに移動すると,移動先のノードにいるビーバーを1匹取り除く.
移動先にビーバーがいないと移動できない.
最終的には出発ノードに戻ってこなければいけない.
取り除けるビーバーの総数の最大値を求める問題.

解法

下から組み立てていく.
各ノードに対して,そのノードに上 (根に近いほう) から来たとして,その部分木でどれだけのビーバーを取り除けるかを求める.
また,その際に,greedyに下の部分と行ったり来たりしておき,そのノードのビーバーの残り数も求めておく.
(その上のノードと行ったり来たりするのにどれだけできるかを,上のノードの計算で使う)

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

typedef struct struct_vector_int{ int size,mem; int *d; }intVector;
intVector intVectorNull(){ intVector v; v.size=v.mem=0; return v; }

void intVectorMemoryExpand(intVector *v){
  int i, *t, m;
  m=v->mem*2; if(m<5) m=5;
  t=(int*)malloc(m*sizeof(int));
  rep(i,v->size) t[i]=v->d[i];
  if(v->mem) free(v->d);
  v->d=t; v->mem=m;
}

void intVectorPushBack(intVector *v,int add){
  if(v->mem==v->size) intVectorMemoryExpand(v);
  v->d[(v->size)++] = add;
}

void llSort(ll d[],int s){int i,j;ll k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;i=-1;j=s;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}llSort(d,i);llSort(d+j+1,s-j-1);}

intVector edge[111111];
int in[111111];
ll dp[111111], amari[111111], st[111111];


void solve(int now,int bef){
  int i,j,k,sz;
  ll res, amari_sum, tmp, gogo;

  rep(i,edge[now].size) if(edge[now].d[i]!=bef) solve(edge[now].d[i], now);

  if(in[now] < 1){ dp[now] = -1; return; }

  dp[now] = 1;
  amari[now] = 0; amari_sum = 0;

  gogo = in[now]-1;
  sz = 0;
  rep(i,edge[now].size){
    j = edge[now].d[i];
    if(j==bef) continue;
    if(dp[j]>=0){
      st[sz++] = dp[j];
      amari_sum += amari[j];
    }
  }
  llSort(st,sz);

  for(i=sz-1;i>=0;i--) if(gogo>0) {
    gogo--;
    dp[now] += st[i]+1;
  }

  if(gogo){
    tmp = gogo;
    if(tmp > amari_sum) tmp = amari_sum;
    gogo -= tmp;
    dp[now] += tmp*2;
  }

  amari[now] = gogo;

/*  printf("%d %d : %lld %lld\n",now,bef,dp[now],amari[now]);*/
}


int main(){
  int i,j,k,l,m,n,st;
  ll res;

  rep(i,111111) edge[i] = intVectorNull();

  while(scanf("%d",&n)==1){
    rep(i,n) scanf("%d",in+i);
    rep(i,n) edge[i].size = 0;
    rep(k,n-1){
      scanf("%d%d",&i,&j); i--; j--;
      intVectorPushBack(edge+i,j);
      intVectorPushBack(edge+j,i);
    }
    scanf("%d",&st); st--;

    in[st]++;
    solve(st,-1);
    dp[st]--;
    if(dp[st]<0) dp[st] = 0;
    printf("%I64d\n",dp[st]);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1962-72349b18
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。