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: 2017年09月22日22時28分26秒
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)

ログイン: