AtCoder Beginner Contest 258 D問題 Trophy

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 個のステージからなるゲームがある. $i$ 番目のステージはストーリー映像が $A_i$ 分, ゲームパートが $B_i$ 分からなる.

各ステージをクリアするためには, ストーリー映像を見てゲームをクリアしなければならないが, 以前にクリアしたことのあるステージについてはストーリー映像をスキップできる.

また, $i$ 番目のステージをプレイするためには, $1,2, \dots, (i-1)$ 番目のステージ全てをクリアしていなければならない.

合計 $X$ 回ステージクリアするためには最低何分必要か? ただし, 同じステージを複数回クリアした場合はその分だけカウントされる.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i, B_i \leq 10^9$
$1 \leq X \leq 10^9$

解法

まず, $N \gt X$ だった場合, $X$ 回クリアした時点で, $(X+1), (X+2), \dots, N$ 番目のステージがプレイ可能になっていることはない. 従って, $(X+1), \dots, N$ 番目のステージは最初からなかったとしても問題ない. つまり, $N \leq X$ と仮定しても良い.

クリアしたステージの種類数に着目して全探索する. $X$ 回クリアしたとき, 1回以上クリアしたステージが $1,2, \dots, i$ 番目のステージだったとする. このような状況下において $X$ 回クリアするのに必要な最短時間を考える. 場合分けの仮定から $1,2, \dots, i$ 番目のステージは $1$ 回はクリアしなければならない. そして, 残りの $(X-i)$ 回についてはゲームパートが最も短いステージでクリアすればよい.

よって, 1回以上クリアしたステージが $1,2, \dots, i$ 番目のステージであるような場合における最短時間 $U_i$ は

$\displaystyle U_i=\sum_{k=1}^i (A_k+B_k)+(X-i) \min (B_1, B_2, \dots, B_i)$

である.

この $U_i~(i=1,2, \dots, N)$ を求めるにあたり, $i=1,2, \dots, N$ の順に求めることにすると,

$\displaystyle \sum_{k=1}^i (A_k+B_k)=\sum_{k=1}^{i-1} (A_k+B_k)+(A_i+B_i)$
$\displaystyle \min (B_1, B_2, \dots, B_i)=\min(\min(B_1, B_2, \dots, B_{i-1}), B_i)$

であるから, 各 $U_i$ を $O(1)$ 時間で計算できる.

クリアしたステージの種類数に着目して全探索する方針であったので, 求めるべき答え $T$ は,

$T=\min(U_1, \dots, U_N)$

である. 以上から, $O(N)$ 時間で処理できた.

ちなみに, $T=U_i$ を達成する $i$ において, $B_i \neq \min (B_1, \dots, B_i)$ だったとすると, $B_j=\min (B_1, \dots, B_i)~(1 \leq j \lt i)$ としたとき, $B_j \lt A_k+B_k~(j \lt k \leq i)$ だから, $U_k \lt U_i$ となってしまう. これは $T=U_i$ であることに矛盾してしまう. よって, $B_i=\min (B_1, \dots, B_i)$ であることがわかる.