SRM462 Div1 Medium

450

ある組みのスワップが起こる確率は 2.0 * (c / (n * c)) * (c / (n * c - 1.0))
ある交換で変化する期待値の差分は score[i] - score[j]
各箱に入っているキャンディーの数は言うまでもなく C

あとは、数値を S ターンだけ更新する。

こういう、"スワップした後"と"期待値"が出てくる問題の類はひどく苦手。

class CandyBox {
public:
  vector <double> expectedScore(int C, vector <int> score_, int S)
  {
    vector<double> score(score_.begin(), score_.end());
    if (S == 0) return score;
    const int N = score.size();
    double swap_prob = 0;
    {
      double c = C;
      double n = N;
      swap_prob = 2.0 * (c / (n * c)) * (c / (n * c - 1.0));
    }
    vector<double> dp[S + 1];
    dp[0] = score;
    for (int turn = 0; turn < S; ++turn) {
      dp[turn + 1] = dp[turn];
      for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
          dp[turn + 1][i] += (dp[turn][j] - dp[turn][i]) * swap_prob / C;
        }
      }
    }
    return dp[S];
  }
};