Pの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 626 Div1 Easy : FixedDiceGameDiv1

問題概要


1~bの値が書いてあるb面サイコロをa個持っているAさんと、1~dの値が書いてあるd面サイコロをc個持っているBさんがいる。

二人がそれぞれ持っているサイコロを全て振って出た目の合計を比べるとき、AさんがBさんより大きい値になる期待値を求める問題。

解法・感想など


確率の問題。条件付き期待値を求める。

まずn面サイコロをm個振ったときに出た目の和についてその確率を求めておく。

dp[i個サイコロを振ったとき][出た目の和] := その確率
で確率テーブルを埋めていく。

それを元にして期待値を求める。

ソースコード

class FixedDiceGameDiv1 {
public:

  double dp[51][2501];

  vector<double> func(int num, int side) {
    rep(i, num + 1) rep(j, 2501) dp[i][j] = 0;
    dp[0][0] = 1;

    rep(i, num) rep(j, 2501) REP(k, 1, side + 1) {
      if(j + k < 2501) dp[i + 1][j + k] += dp[i][j] / side;
    }
    
    vector<double> res(2501);
    rep(i, 2501) res[i] = dp[num][i];
    
    return res;
  }

  double getExpectation(int a, int b, int c, int d) {
    vector<double> pa = func(a, b);
    vector<double> pb = func(c, d);

    double p = 0;
    double q = 0;
    rep(i, a * b + 1) rep(j, c * d + 1) if(i > j) {
      p += i * pa[i] * pb[j];
      q += pa[i] * pb[j];
    }

    return q == 0 ? -1 : p / q;
  }
};