No.015 D

$t$ 秒に生成されるクッキーの期待値を考える.

$t-k$ 秒に生成された金色クッキーによる倍率の期待値は,

$$b_k = p\sum_{i=1}^N q_iy_i + (1-p)$$

である. ただし,

$$y_i = \begin{cases} x_i & (t_i \geq k) \\ 1 & (t_i \lt k) \end{cases}$$

である. よって, $t$ 秒に生成されるクッキーの期待値は,

$$e_t = \prod_{k=1}^{t-1} b_k$$

となる. $\sum e_t$ が答えである.

これを愚直に計算すると間に合わないが, $q_ix_i$ および $q_i$ の累積和, $b_k$ の累積積を計算しておけば間に合わせることができる.