TopCoder SRM620 DIV2 HARD - RandomGraph

Source

TopCoder SRM620 DIV2 HARD (1000pt)
Problem Statement

問題概要

$N$ 個のノードからなるグラフで,各頂点間は確率 $P/1000$ で枝がつながっている.(枝があるかどうかは独立)
$4$ ノード以上からなる連結成分がある確率を求める問題.

解法

$1$ つずつノードを付け加えていって,$4$ ノード以上からなる連結成分ができない確率を考える.
その時に,$1$ ノードのみの連結成分の個数,$2$ ノードのみの連結成分の個数,$3$ ノードのみの連結成分の個数を状態として,その状態になる確率をDPで求める.
$1$ ノードを加えた時に,$4$ ノード以上からなる連結成分が作られないような状態遷移のみを考えれば良い.
状態数は $O(N^3)$ で時間計算量は $O(N^3)$ ぐらい(以下のコードは手抜きのため $O(N^4)$).
$N=k$ の時の答え $D_k$ のみを状態として記憶して,最後に付け加えたノードからなる連結成分の数で場合分けする方法もあり,$O(N)$ ぐらいで求めることもできる.
また,最終的なサイズ $1$ の連結成分の個数,サイズ $2$ の連結成分の個数,サイズ $3$ の連結成分の個数を全部試して,そのような確率をコンビネーションなどを用いて計算する方法もある.

C++によるスパゲッティなソースコード($O(N^4)$)

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

double dp[51][51][51], nx[51][51][51];

class RandomGraph {
public:
double probability(int n, int p_) {
  int i, j, k, m;
  double res;
  double p = p_ / 1000.0;

  rep(i,n+1) rep(j,n+1) rep(k,n+1) dp[i][j][k] = 0;
  dp[0][0][0] = 1;

  rep(m,n){
    rep(i,n+1) rep(j,n+1) rep(k,n+1) nx[i][j][k] = 0;
    rep(i,n) rep(j,n) rep(k,n) if(dp[i][j][k] != 0){
      nx[i+1][j][k] += dp[i][j][k] * pow(1-p, m);
      if(i) nx[i-1][j+1][k] += dp[i][j][k] * pow(1-p, m-1) * pow(p, 1) * i;
      if(j) nx[i][j-1][k+1] += dp[i][j][k] * pow(1-p, m-1) * pow(p, 1) * (2*j);
      if(j) nx[i][j-1][k+1] += dp[i][j][k] * pow(1-p, m-2) * pow(p, 2) * j;
      if(i>=2) nx[i-2][j][k+1] += dp[i][j][k] * pow(1-p, m-2) * pow(p, 2) * i * (i-1) / 2;
    }
    rep(i,n+1) rep(j,n+1) rep(k,n+1) dp[i][j][k] = nx[i][j][k];
  }

  res = 1;
  rep(i,n+1) rep(j,n+1) rep(k,n+1) res -= dp[i][j][k];

  return res;
}

}

Current time: 2017年09月25日07時56分50秒
Last modified: 2014年05月11日18時24分38秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM620 SRM_Div2_Hard
トップページに戻る

Logged in as: unknown user (not login)

ログイン: