Codeforces Round #547 (Div. 3)E. Superhero Battle

問題概要

数字 $H$ と長さ $n$ の数列 $d$ が与えられる. $i$ 回目では $H \leftarrow H + d_{((i-1)~\mathrm{mod} n) + 1}$ となるとき, 初めて $H$ が $0$ 以下になるのは何回目か？(永遠に正の場合は $-1$ を出力)

問題へのリンク

制約

$1 \le H \le 10^{12}$
$1 \le n \le 2\times 10^5$
$10^{-6} \le d_i \le 10^6$

解法

$d$ 累積和における最小値を $m$ とします. もし $H+m\le 0$ なら, 普通にシミュレーションすればいいです. そうではないときに愚直にやると TLE するので, 少しは考える必要があります.

数列全体の和を $S$ としたとき, もし $S \ge 0$ なら数列を周回するたびに $H$ が増えていくので, 永遠に正にはなりません. そうではないとき, ラスト一周だけシミュレーションすることにしたいので, $H$ の値が $-m$ 以下になるまでまとめて周回を回します. これは, $H+m$ を $S$ で切り上げた回数だけ周回すればいいです(こういうのぱっとわかる人はすごいです. 僕は切り上げるか切り捨てるか毎回実験しています).

実装

Submission #145537370 - Codeforces