ABC 153 F - Silver Fox vs Monster

問題

数直線上に配置された $n$ 体の敵の座標 $X _ i$ と体力 $H _ i$ が与えられていて、長さ $2d$ の範囲にいる敵の体力を一斉に $a$ 削る攻撃ができる。何回の攻撃ですべての敵を倒せるか求めよ。（$n\leq 2\times 10 ^5$）

atcoder.jp

解説

敵はあらかじめ座標の昇順にソートされているとして、左から順に、それまでの敵へのダメージを引き継ぎながら、目の前の敵を倒すまで攻撃していけばよい。ただし、攻撃が及ぶ範囲には制限があるので、$i$ 番目を足す際に $X _ j \leq X _ i + 2 d$ をみたす最小の $j$ については $i$ 番目に足す分をあらかじめ引いておく。
具体的な手順としては、最初 $S _ {i} = 0$ $(i = 0,\ldots , n)$ としておき、 各 $i$ において以下の操作を行う。

1. $H _ i \leftarrow H _ i - S _ i$
2. $c \leftarrow \displaystyle \left \lceil \frac{H _ i}{a} \right \rceil $
3. $X _ j \leq X _ i + 2 d$ をみたす最小の $j$ について、$S _ j \leftarrow S _ j - a \times c$
4. $S _ {i + 1} \leftarrow S _ i + a \times c$

最終的な $c$ の合計が答えになる。

実装

$X _ j > X _ i + 2 d$ をみたす最小の $j$ は $i$ に対して単調増加なので、前の $i$ での $j$ 以降だけ調べればよい。
また、無限遠点に体力 $0$ の敵を置いておくことで、インデックスのエラーを防いでいる。

n, d, a = map(int, input().split())
XH = [tuple(map(int, input().split())) for i in range(n)]
XH.sort()
X = [x for x, h in XH]
H = [h for x, h in XH]
X.append(10**10)
H.append(0)
j = 0
S = [0]*(n+1)
ans = 0
for i in range(n):
    H[i] = max(0, H[i]-S[i])
    c = -(-H[i]//a)
    while X[j] <= X[i] + 2*d:
        j += 1
    S[i+1] += S[i] + a*c
    S[j] -= a*c
    ans += c
print(ans)

atcoder.jp