$i$人目が入る部屋の人数は決まっていて、シミュレーションで求まる。$i$人目が$f[i]$人の部屋に入ったとする。また、
- $\operatorname{dp}[i][x] := i$人が部屋に入った時点で$x$人部屋であるような部屋の、最終的な人数の期待値
- $\operatorname{num}[i][x] := i$人が部屋に入った時点で$x$人部屋であるような部屋の数
とすると、後ろからDPできる:
$$ \operatorname{dp}[i][f[i+1]] = \frac{\operatorname{dp}[i+1][f[i+1]+1] + \operatorname{dp}[i+1][f[i+1]]\operatorname{num}[i+1][f[i+1]]}{\operatorname{num}[i+1][f[i+1]] + 1} $$$\operatorname{num}[i][f[i+1]] = \operatorname{num}[i+1][f[i+1]] + 1$
$\operatorname{num}[i][f[i+1]+1] = \operatorname{num}[i+1][f[i+1]+1] - 1$
更新箇所が定数個しかないので、in-placeにDPすれば${O}(N)$になる。$i$人目に関する期待値は$\operatorname{dp}[i][f[i]+1]$に等しい。
