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$ 個ある皿はない。
以下では、状態を皿の枚数の組で表す。
順番は、寿司が $3$ 個、$2$ 個、$1$ 個ある皿とする。
例えば $(0,1,1)$ を考える。
寿司が $2$ 個ある皿が $1$ 枚ある。
寿司が $1$ 個ある皿も $1$ 枚ある。
全部食べ終わった状態 $(0,0,0)$ の期待操作回数は $0$ である。
状態 $(0,0,1)$ を考える。
寿司がある皿は $1$ 枚、空の皿も $1$ 枚である。
考え方で求めた式に代入すると、期待値は $(2+1\times0)/1=2$ となる。
状態 $(0,0,2)$ を考える。
$2$ 枚とも寿司が $1$ 個ある皿である。
どちらを選んでも、次は $(0,0,1)$ になる。
したがって、期待値は $(2+2\times2)/2=3$ となる。
状態 $(0,1,0)$ を考える。
寿司が $2$ 個ある皿が $1$ 枚ある。
それを選ぶと、次は $(0,0,1)$ になる。
空の皿を選ぶ場合は状態が変わらない。
考え方で求めた式に代入すると、期待値は $(2+1\times2)/1=4$ となる。
最後に、初期状態 $(0,1,1)$ を考える。
寿司が $1$ 個ある皿を選ぶと、次は $(0,1,0)$ になる。
残りの期待値は $4$ である。
寿司が $2$ 個ある皿を選ぶと、次は $(0,0,2)$ になる。
残りの期待値は $3$ である。
この状態では空の皿がない。
したがって、期待値は $\frac{2+1\times4+1\times3}{2}=4.5$ となる。
よって、答えは $4.5$。
注意点
寿司が $1$ つ減った時の参照先に注意。
寿司が $3$ 個乗っている皿が選ばれたときに、参照する先は「$3$ 個の皿が $1$ つ減ったデータ」ではない。
$3$ 個の皿から寿司を $1$ つ食べるということは、$2$ 個の皿が新しくできるということ。
つまり、参照先は「$3$ 個の皿が $1$ つ減り、$2$ 個の皿が $1$ つ増えたデータ」である。
寿司が $2$ 個乗っている皿が選ばれたときも同様。
その影響で、$2$ 個の皿や $1$ 個の皿の枚数が初期値より増える可能性がある。
DP テーブルの広さにも注意が必要。
別解
特になし。