Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM598 DIV1 HARD - TPS (この記事を編集する[管理者用])

Source

TopCoder SRM598 DIV1 HARD (950pt)
Problem Statement

問題概要

$N$ ノードの木が与えられる.
測定装置を $k$ 個のノードに置く.
各ノードに対して,測定装置からの距離の組を考え,それが各ノードについて異なるようにしたい.(測定結果からどのノードが判断できるようにしたい)
最小の $k$ を求める問題.

解法

まず,$N=1$ なら $k=0$ で良いので,例外処理しておく.
そうでなければ,$1$ 個は測定装置を置かなくてはいけないので,$1$ 個置く場所を全探索して,固定して考える.
測定装置をとりあえずおいたノードを根とした根付き木で考える.
各ノードについて,自分の子供が $2$ つ以上あるなら,それを区別するために,子供からなる部分木のうち,1個を除いて全てのものに測定装置がなければならない.
よって,測定装置を置かなければいけないノードは,子供の方から再帰的にgreedyに求めることができる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int n;
int edge[51][51], es[51];

int dp[51];
int solve(int now, int bef){
  int i, j, k;
  int down = 0, ok = 0;
  int res = 0;

  rep(k, es[now]){
    i = edge[now][k];
    if(i == bef) continue;

    res += solve(i, now);
    down++;
    ok += dp[i];
  }

  if(down - 1 - ok > 0) res += down - 1 - ok;

  if(res) dp[now] = 1;
  else    dp[now] = 0;

  return res;
}

class TPS {
public:
int minimalBeacons(vector <string> inp) {
  int i, j, k, root;
  int res = 10000, tmp;

  n = inp.size();
  rep(i,n) es[i] = 0;
  rep(i,n) rep(j,n) if(inp[i][j]=='Y'){
    edge[i][es[i]++] = j;
  }

  if(n==1) return 0;
  if(n==2) return 1;
  if(n==3) return 1;

  rep(root, n){
    rep(i,n) dp[i] = -1;
    tmp = solve(root, -1) + 1;
    printf("%d : %d\n",root,tmp);
    res = min(res, tmp);
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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