CODE FESTIVAL 2014 決勝 H - 部屋割り

• 問題
• AC

$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]$に等しい。