問題
$N$ 体のモンスターがいる。$i$ 番目のモンスターは座標 $X_i$ にいて、体力は $H_i$ である。座標 $a$ で爆弾を使うと、$a-D \leq x \leq a+D$ の範囲のモンスターの体力を $A$ 減らすことができる。すべてのモンスターの体力を $0$ 以下にするために必要な爆弾の使用回数の最小値を求める。
解法
モンスターたちをあらかじめ座標でソートしておき、座標の小さいモンスターから順に倒していくことにします。
爆弾の効果を最大限利用するため、座標 $X_1$ のモンスターを倒すには、爆弾を $X_1+D$ で使用します。すると、座標 $X_1+2D$ までのモンスターが標的になります。座標 $X_1$ のモンスターの体力が $0$ 以下になったら、この位置で爆弾を使用するのをやめます。以下、同じように爆弾を使用していけば最小回数で全モンスターを倒せます。
これを素朴に実装すればいいのですが、ネックになるのは $X_1 \leq x \leq X_1 + 2D$ の範囲の全モンスターの体力を更新する操作です。愚直に更新していると時間計算量が $O(N^2)$ になりTLEします。この部分の工夫の仕方は何通りかあります。
キューで管理する
キューにどの位置で何回爆弾を使用したかを入れていき、$i$ 番目のモンスターを処理する前にキューの先頭を確認して、爆弾の効果範囲から外れていたら削除するというやり方。
詳しくはすぬけさんの解答や解説を見てください。
いもす法で管理する
いもす法とは、imosさんが考案した累積和のアルゴリズムの改良版です。ご本人による解説も参考にしてください。
各モンスターへのダメージを記録するテーブルを用意します（空間計算量は $O(N)$）。それぞれのモンスターの処理の概要は次のようになります。
- 前のモンスターのダメージを引き継ぐ。
- いま見ているモンスターの体力を $0$ 以下にするまで爆弾を使う。
- 使った爆弾が影響しない最初のモンスターのダメージから、いま使った爆弾のダメージを引いておく。
たとえば、$1$ 番目のモンスターに対して爆弾を $C_1$ 回使用したとすると、テーブルに $C_1A$ と記録します。これと同時に、この爆弾が影響しない最初のモンスター（$k$ 番目とおく）のテーブルに $-C_1A$ と記録しておきます。すると、1. の操作を行うので、この爆弾が与える $k$ 番目のモンスターへのダメージは相殺されて $0$ になります。
それぞれのモンスターに対して $k$ 番目のモンスターを探す操作に $O(\log N)$ かかるので、全体で $O(N\log N)$ で解けました。
実装例: https://atcoder.jp/contests/abc153/submissions/9771219
感想
終わってすぐ風呂に入っている間に気づいたので、あと20分早ければACしてたかもしれない。