DPまとめコンテスト/J - Sushi - 競技プログラミング用 知識集積所【7/19更新】

---

問題

DP-J

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法
• 期待値（未作成）

考え方

期待値（未作成）の計算に慣れていれば、発想自体はそこまで難しくない。

期待値 = 1 + 3個の皿を選ぶ確率 * 3個の皿から1つ取った後の期待値
           + 2個の皿を選ぶ確率 * 2個の皿から1つ取った後の期待値
           + 1個の皿を選ぶ確率 * 1個の皿から1つ取った後の期待値
           + 0個の皿を選ぶ確率 * 0個の皿から1つ取った後の期待値

という式で、最後の「0枚の皿から1つ取った後の期待値」は求めたい期待値と同じものである。
自分を含めた再帰計算はできないので、これを以下のように変形する。

(1 - 0個の皿を選ぶ確率) * 期待値
    = 1 + 3個の皿を選ぶ確率 * 3個の皿から1つ取った後の期待値
        + 2個の皿を選ぶ確率 * 2個の皿から1つ取った後の期待値
        + 1個の皿を選ぶ確率 * 1個の皿から1つ取った後の期待値

できるだけ小数計算をしたくないので、両辺に全皿枚数を掛けて

(n - 0個の皿の枚数) * 期待値
    = n + 3枚の皿の個数 * 3個の皿から1つ取った後の期待値
        + 2枚の皿の個数 * 2個の皿から1つ取った後の期待値
        + 1枚の皿の個数 * 1個の皿から1つ取った後の期待値

最初の括弧の中は1個以上の皿の枚数である。
したがって、全部0個の場合を例外処理で取り除いておけば、割り算が可能で、期待値が求まる。

解答例

解答例

注意点

寿司が1つ減った時の参照先に注意

寿司が3個乗っている皿が選ばれたときに、参照する先は「3個の皿が1つ減ったデータ」ではない。
3個の皿から寿司を1つ食べるということは、2個の皿が新しくできるということ。
つまり、参照先は「3個の皿が1つ減り、2個の皿が1つ増えたデータ」である。

寿司が3個乗っている皿が選ばれたときも同様。

その影響で、2個の皿や1個の皿の枚数が初期値より増える可能性があり、DPテーブルの広さにも注意が必要。

別解