No.322

難所を適当に並べたとき, $i$ 番目の難所を通過するために必要な時間 $t_i$ は,

$$t_i = D_i \left( \sum_{j=1}^{i-1} T_j + \frac{T_i}{2} \right) + T_i$$

となる.

難所を適当に並べたとき, $i$ 番目と $i+1$ 番目の難所を入れ替えたときのステージクリアに必要な時間の差は,

$$\begin{align} t_d &= \left( \left( D_{i+1} \frac{T_{i+1}}{2} + T_{i+1} \right) + \left( D_i \left( T_{i+1} + \frac{T_i}{2} \right) + T_i \right) \right) - \left( \left( D_i \frac{T_i}{2} + T_i \right) + \left( D_{i+1} \left( T_i + \frac{T_{i+1}}{2} \right) + T_{i+1} \right) \right) \\ &= \left( \frac{D_{i+1}T_{i+1} + D_iT_i}{2} + D_iT_{i+1} + T_{i+1} + T_i \right) - \left( \frac{D_{i+1}T_{i+1} + D_iT_i}{2} + D_{i+1}T_i + T_i + T_{i+1} \right) \\ &= D_iT_{i+1} - D_{i+1}T_i \\ &= T_iT_{i+1} \left( \frac{D_{i+1}}{T_{i+1}} - \frac{D_i}{T_i} \right) \end{align}$$

となるので, $D_i/T_i$ が小さい順に並べればステージクリアに必要な時間が最大になる.