保存されている過去のバージョンの一覧

2014年04月20日06時20分04秒

TopCoderOpen Algorithm 2014 Round 1B HARD - EagleInZoo

Source

TopCoderOpen Algorithm 2014 Round 1B HARD (900pt)
Problem Statement

問題概要

$N$ ノードの根付き木が与えられる．
最初は，どのノードにも人はいない．
これから，$K$ 人が来て $1$ 人ずつ以下の動作をする．

  1. 最初に，ルートに移動する．その後，以下の2.～4.を繰り返す
  2. 今いるノードに誰もいなければ，そのノードに居座る（終了する）
  3. 今いるノードに既に誰か居て，そのノードが子ノードを持っていない場合は，立ち去り，何処か遠くへ行く（終了する）
  4. 今いるノードに既に誰か居て，そのノードが子ノードを持っている場合は，子ノードの中から $1$ つをランダムに選び，そのノードに移動する（2.に戻る）

最後の $K$ 番目の人が，どこかのノードに居座ることができる確率を求める問題．

解法

全てのノードに対して，最後の人がそのノードに居座る可能性を別々に計算して，和を取る（ことにする）．
まず，最初に，全てのノードが埋まっていると仮定した時，それぞれのノードまで人が来る可能性があるという確率を計算しておく．
そして，あるノードに居座る可能性を計算するのは，DPを使う．
ルートからそのノードまでのパスを求めて，状態を（今何人動作をしたか，そのパスの何番目のノードまで埋まっているか）と取り確率を計算する．
ノードごとに求めて和を取らなくても，木のままDPすれば，一度に計算することもできる（こっちの方が良かった）．

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

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

double dp[111][53];

double solve(double prob[], int prob_size, int K){
  int i, j, k;

  rep(i,K+1) rep(j,prob_size+1) dp[i][j] = 0;
  dp[0][0] = 1;

  rep(i,K){
    rep(j,prob_size){
      dp[i+1][j+1] += dp[i][j] * prob[j];
      dp[i+1][j] += dp[i][j] * (1-prob[j]);
    }
    dp[i+1][prob_size] += dp[i][prob_size];
  }

  return dp[K][prob_size] - dp[K-1][prob_size];
}

int edge[55][55], es[55];
double prob[100]; int prob_size;

double dfs(int node, double p, int K){
  int i, j, k;
  double res = 0;

  prob[prob_size++] = p;
  res += solve(prob, prob_size, K);

  rep(j,es[node]){
    i = edge[node][j];
    res += dfs(i, p/es[node], K);
  }

  prob_size--;

  return res;
}

class EagleInZoo {
public:
double calc(vector <int> parent, int K) {
  int i, j, k, N;
  double res;

  N = parent.size() + 1;
  rep(i,N) es[i] = 0;
  REP(i,1,N){
    j = parent[i-1];
    edge[j][es[j]++] = i;
  }

  prob_size = 0;
  res = dfs(0, 1, K);

  return res;
}

}

Current time: 2024年04月20日03時07分31秒
Last modified: 2014年04月20日06時20分04秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_1B
トップページに戻る

Logged in as: unknown user (not login)

ログイン：