Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-26

[][] Codeforces Beta Round #16 E. Fish 12:59 はてなブックマーク -  Codeforces Beta Round #16 E. Fish - 練習帳

テーマ:配る DP と貰う DP *1,条件付き確率

問題文

 Problem - 16E - Codeforces

要約

 湖の中に魚が n 匹いる。ランダムに 2 匹が出会い,一方がもう一方を食べてしまう。魚 i と魚 j が会った時に i が j を食べる確率 a[i][j] は与えられている(a[i][j] + a[j][i] = 1)。これを湖に魚1匹しかいなくなるまで繰り返す時,それぞれの魚が生き残る確率を求めよ。

 nは 1 以上 18 以下

分析

 I ⊂ {1, .., N} で生き残っている魚の種類を表し,P(J | I)で状態 I の条件下での状態 J の条件付き確率とすると,求めるのは P(i | I),これは次式で求められます。

$\displaystyle{P( i | I) = \frac{1}{ \{ (j, k)\in I^{2}  \} }\sum_{(j,k)\in I^{2}} a\[j\]\[k\] \cdot P(i | I\setminus \{k\}) + a\[k\]\[j\] \cdot P(i|I\setminus \{j\})} $

 n が小さいので O(2^n) かかるアルゴリズムが使えます。そこでそれぞれの魚の生存状態をビットで表現し,下から k 番目のビットが 1 で,k 番目の魚が生きている事を示します。dp[i][j] は魚の生存状態が j の条件で,最終的に i 番目の魚が生き残る条件付き確率を表します。これをそのまま実装したのが下のコードです。

コード例

(このコードはTLEを起こします)

#include <iostream>

using namespace std;
double dp[18][1 << 18];
int done[1<<18];
double p[18][18];
int n;

void dfs(int cond){
  if(done[cond] != -1) return;  
  if(__builtin_popcount(cond) == 1){
    for(int i = 0; i < 18; i++){
      if(cond >> i & 1)
	dp[i][cond] = 1;      
    }
    done[cond] = 1;
    return;
  }
  int num = __builtin_popcount(cond);
  for(int i = 0; i < n; i++){
    if(!((cond >> i) & 1)) continue;
    for(int j = i+1; j < n; j++){
      if( ((cond >> j) & 1) ){
	int temp = cond & ~(1 << i);
	dfs(temp);	
	for(int k = 0; k < n; k++){
	  dp[k][cond] += p[j][i] * dp[k][temp];
	}

	temp = cond & ~(1 << j);
	dfs(temp);
	for(int k = 0; k < n; k++){
	  dp[k][cond] += p[i][j] * dp[k][temp];
	}
      }      
    }
  }
  for(int i = 0;i<n;i++){
    dp[i][cond] /= num *(num - 1)/2;
  }

  done[cond] = 1;
  return ;
}
int main(){
  while(cin >> n){    
    for(int i = 0;i<n;i++){
      for(int j  = 0;j<n;j++){
	cin >> p[i][j];
      }
    }
    for(int i = 0;i<1<<n;i++){
      done[i] =-1;
    }
    dfs((1<<n)-1);
    for(int i = 0;i<n;i++){
      cout << dp[i][(1 << n)-1] << " ";
    }
    cout << endl;
  }
}

 上のコードの場合,最大ケースで約 12 秒かかります。小手先で枝狩りをしてもほとんど変わりませんでした。今のコードは O(n^3 2^n) のアルゴリズムなので,ループの数を減らします。

 オーソドックスに初めに全ての魚が生存している状態からスタートして,そこから状態 I に遷移する確率を求めます(条件付き確率では考えていません)。また,必ず自分よりも小さい数の状態に遷移するので,再帰的に呼び出さず,単純な for ループで書く事が出来ました。以上の考察のもとに修正したのが下のコードです。

#include <iostream>

using namespace std;

double dp[1 << 18];
double p[18][18];
int n;

int main(){
  while(cin >> n){    
    for(int i = 0;i<n;i++){
      for(int j  = 0;j<n;j++){
	cin >> p[i][j];
      }
    }
    dp[(1<<n)-1]= 1;    
    for(int cond = (1<<n)-1;cond>0;cond--){
      int num = __builtin_popcount(cond);
      for(int i = 0; i < n; i++){
	if(!((cond >> i) & 1)) continue;
	for(int j = i+1; j < n; j++){
	  if( ((cond >> j) & 1) ){
	    int temp = cond & ~(1 << i);
	    dp[temp] += p[j][i] * dp[cond] / (num *(num - 1)/2);

	    temp = cond &  ~(1 << j);
	    dp[temp] += p[i][j] * dp[cond] / (num *(num - 1)/2);
	  }      
	}
      }
    }
    for(int i = 0;i<n;i++){
      cout << dp[1 << i] << " ";
    }
    cout << endl;
  }
}

*1: iwiwi さんの講義資料から http://www.slideshare.net/iwiwi/ss-3578511