SRM 304 Div1 Medium Conditional

問題

面数がmaxSideのサイコロをnDice個ふる。少なくとも1つがvの目を出す条件のもと、出た目の和がtheSum以上になる確率を求めよ。

やりかた

条件付き確率を求める問題。まずvの目が一回は出つつ、合計がtheSum以上になる同時確率をdpで求める。
dp[k][i][j]:=（i番目のサイコロまでで和がjとなる確率。すでにvの目が出ているなら k = 1、さもなくば k = 0）

条件付き確率の定義上
であるからを求めて割ってやればいい。これはですぐ求まる。

double dp[2][51][51*51];

class Conditional {  
public:
  double probability(int nDice, int maxSide, int v, int theSum) {
    double ans;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0]= 1.0;
    for(int i = 0; i < nDice; i++){
      for(int j = 0; j <= nDice * maxSide; j++){
	for(int k = 1; k <= maxSide; k++){
	  if(k == v) dp[1][i + 1][j + v] += dp[0][i][j] / maxSide;
	  else dp[0][i + 1][j + k] += dp[0][i][j] / maxSide;

	  dp[1][i + 1][j + k] += dp[1][i][j] / maxSide;
	}
      }
    }
    double a = 0.0, b = 1.0;
    for(int k = theSum; k <= nDice * maxSide; k++) a += dp[1][nDice][k];
    for(int k = 0; k < nDice; k++) b *= (maxSide - 1.0) / maxSide;
    b = 1.0 - b;
    return a / b;
  }
};

完全に間違えた解説を書いていたのであわてて訂正。