問題概要
$N$ ステージからなるゲームがある．$i$ 番目のステージは，初回クリアには $A_i + B_i$ 分の時間がかかり，2 回目以降のクリアには $B_i$ 分かかる．$i$ ( $0 < i$ ) 番目 (0-indexed) のステージをプレイするには，$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$
解法
$i$ 番目 (0-indexed) までのステージだけを使って目標を達成する場合というのを考えてみます．このとき，所要時間への寄与は次の 2 種に分類されます：
- 各ステージを初回クリアするのにかかる時間
- 初回クリア分では足りないクリア回数を稼ぐのにかかる時間
後者の方は，この状況下でプレイ可能なステージの内で所要時間が最短なものを周回するのが最適で，その時の周回数は $X - 1 - i$ です．なので上記をそれぞれちゃんと書きつつ名前をつけると，
- $C_i = \sum_{ 0 \leq j \leq i }( A_j + B_j )$
- $D_i = \min_{ 0 \leq j \leq i } B_j \times ( X - 1 - i )$
となります．これらを使うと，$i$ 番目までのステージを使う場合の最適なプレイ時間は $C_i + D_i$ なので，答えとしてはこの最小値，$$\min_{ 0 \leq i < N }( C_i + D_i )$$ となります．
この計算に必要な値はすべて $Theta( N )$ 時間で計算できるので，全体としても $Theta( N )$ 時間となります．
コード
main = do [ n, x ] <- readIntegers [ as, bs ] <- transpose <$> replicateM ( fromIntegral n ) readIntegers let as_sum = scanl1 (+) $ zipWith (+) as bs min_bs = scanl1 min bs repeats = zipWith (*) min_bs [ x - 1, x - 2 ] results = zipWith (+) as_sum repeats print $ minimum results
