No.155

$L, S_i$ ともに秒に変換しておく.

$L \geq \sum S_i$ の場合は全曲が1回以上流れるので, 答えは $N$ となる. 以下は $L \lt \sum S_i$ のときだけ考える.

最後に流れる曲を $j$ とすると, $m$ 秒後に $j$ 以外の曲を $n$ 曲流す順序を含めない組み合わせの数を $C_j(m, n)$ とすると, これを

$$C_j(m, n) \leftarrow C_j(m, n) + C_j(m - S_i, n - 1)$$

s.t.

$$i \in T_j = \{i \mid 1 \leq i \leq N, i \neq j \}$$

の式で DP で計算する.

$m$ 秒後に $n$ 曲流したすると, そのときの順序を含めた組み合わせの数は $j$ の前に $n$ 曲, $j$ の後に残りを並べる組み合わせの数なので,

$$n!(N-n-1)!$$

となり, 最後に曲 $j$ を流す場合の期待値は

$$\sum_{m = L - S_j}^{L - 1} \sum_{n = 1}^{N - 1} C_j(m, n) \frac{n!(N-n-1)!}{N!}(n+1)$$

となる. これをすべての $j$ ついて計算して合計すればいい.

…のだが, $C_j(m, n)$ の計算に $O(N^2L)$ かかるので, 全体の計算量が $O(N^3L)$ となってしまう. (それでも間に合ってしまったのだが)

そこで戻すDPを使う. $i$ 曲目まで調べたときの $m$ 秒後に $n$ 曲流す順序を含めない組み合わせの数を $D_i(m, n)$ とすると, $j$ 以外の曲を対象としたときと同様に,

$$D_i(m, n) = D_{i-1}(m, n) + D_{i-1}(m - S_i, n - 1)$$

となり,

$$D_{i-1}(m, n) = D_i(m, n) - D_{i-1}(m - S_i, n - 1)$$

となる. 曲を調べる順序は任意なので, $j$ を最後に調べるような順序でこの計算を行ったとすると, $D_{N-1}(n, m) = C_j(n, m)$ であるので,

$$C_j(m, n) = D_N(m, n) - C_j(m - S_j, n - 1)$$

となる. よって $C_j(m, n)$ は $O(NL)$ で計算できる.