EDPC J - Sushi

考え方

ABCでいうと、E問題級。

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

次のようにおく。

• $E$ は、今の状態から全て食べ終わるまでの期待値
• $p_i$ は、寿司が $i$ 個ある皿を選ぶ確率
• $E_i$ は、寿司が $i$ 個ある皿から $1$ 個取った後の期待値

すると、次の式になる。

$$
E = 1 + p_3E_3 + p_2E_2 + p_1E_1 + p_0E
$$

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

$$
(1-p_0)E = 1 + p_3E_3 + p_2E_2 + p_1E_1
$$

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

ここで、$c_i$ を寿司が $i$ 個ある皿の枚数とすると、次のようになる。

$$
(n-c_0)E = n + c_3E_3 + c_2E_2 + c_1E_1
$$

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

$$
E = \dfrac{n + c_3E_3 + c_2E_2 + c_1E_1}{c_3 + c_2 + c_1}
$$

あとは、これで動的計画法するだけではあるのだが、表が三次元なうえに表の幅が一定でないので注意。
サイズを大きめに取るという解決策もあるが、練習としてはピッタリサイズで作りたいところである。

計算量は $O(N^3)$。

入力例3での動作

入力を受け取る。

n: 2
a: {1, 2}

寿司が $1$ 個ある皿は $1$ 枚、寿司が $2$ 個ある皿は $1$ 枚、寿司が $3$ 個ある皿は $0$ 枚である。

n1: 1
n2: 1
n3: 0

dp[i3][i2][i1] を、次の状態から全て食べ終わるまでの期待操作回数とする。

• 寿司が $3$ 個ある皿が i3 枚
• 寿司が $2$ 個ある皿が i2 枚
• 寿司が $1$ 個ある皿が i1 枚

全部 $0$ 個の状態は、すでに食べ終わっているので期待値は $0$ である。

dp[0][0][0]: 0.0

状態 dp[0][0][1] を考える。
$2$ 枚のうち $1$ 枚だけが空でない皿なので、次の寿司を食べるまでの期待操作回数は $2$ である。

dp[0][0][1] = (2 + dp[0][0][0] * 1) / 1
            = 2.0

状態 dp[0][0][2] を考える。
$2$ 枚とも寿司が $1$ 個ある皿であり、寿司を $1$ 個食べると dp[0][0][1] の状態になる。

dp[0][0][2] = (2 + dp[0][0][1] * 2) / 2
            = 3.0

状態 dp[0][1][0] を考える。
寿司が $2$ 個ある皿が $1$ 枚なので、寿司を $1$ 個食べると dp[0][0][1] の状態になる。

dp[0][1][0] = (2 + dp[0][0][1] * 1) / 1
            = 4.0

最後に、状態 dp[0][1][1] を考える。
この状態では、次の $2$ 通りがある。

• 寿司が $1$ 個ある皿を選ぶと dp[0][1][0] の状態になる。
• 寿司が $2$ 個ある皿を選ぶと dp[0][0][2] の状態になる。

dp[0][1][1] = (2 + dp[0][1][0] * 1 + dp[0][0][2] * 1) / 2
            = 4.5

dp[0][1][1] の $4.5$ が答え。

注意点

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

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

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

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

別解

特になし。