SRM435 Div2 1000

問題

野鳥が全部でbNいる．一日のはじめにcPDだけ捕まえて調査し夜には放す．調査では鳥の足にマークをつける(すでについてたらそのまま放す)．dN日繰り返したあとで，マークが付いている鳥の数がbMである確率を求める．

考え方

dpかdfs．
dp[日][マークの付いた鳥の数]でやった．ある日(day)，捕まえた鳥のうちマークが付いた鳥の数がmだった場合，組み合わせCombを使って，
prob = Comb(マークの付いた鳥から(cPD-j)鳥だけ選ぶ)*Comb(マークがついてない鳥からj鳥だけ選ぶ)/Comb(bN鳥からcPD鳥だけ選ぶ);
dp[day+1][m+j] += dp[day][m] * prob;
と書ける．
(鳥は識別できないので，マークの有無でしか確認できない=>2^20通りではなく20通りで十分．各時点から組み合わせの分だけ分岐するのでそれを確率probとすると次の日の確率はその状態での確率*probになる)
以下，破滅的なコード．

int Comb(int n, int k){
  if(n==0 || k==0) return 1;
  int f[n+1][n+1]; for(int i=0; i<n+1; i++) f[0][i] = f[i][0] = 1;
  for(int i=1; i<n+1; i++) for(int j=1; j<n+1; j++){
    f[i][j] = f[i-1][j]+f[i][j-1];
    if(i+j==n && j==k) return f[i][j];
  }
  return 1;
}

double dp[6][21];

double solve(int bN, int cPD, int dN, int bM){
  rep(i,6) rep(j,21) dp[i][j] = 0.0; 
  dp[0][0] = 1.0;
  rep(d,dN) rep(i,bN+1){
    rep(j,bN-i+1){
      if(0<=cPD-j && cPD-j<=i && 0<=j && j<=bN-i){
	double prob = Comb(i,cPD-j) * Comb(bN-i, j) / (double)Comb(bN, cPD);
	dp[d+1][i+j] += dp[d][i] * prob;
      }
    }
  }
  return dp[dN][bM];
}

class BirdsCounting {
  public:
  double computeProbability(int birdsNumber, int caughtPerDay, int daysNumber, int birdsMarked) {
    return solve(birdsNumber, caughtPerDay, daysNumber, birdsMarked);
  }
};

反省

問題をきちんと読む．マークが付いていたらマークを外すと誤読:-(