ABC153 F - Silver Fox vs Monster - あっとのTECH LOG

問題原文

atcoder.jp

問題要旨

$N$ 体のモンスターが一列に並んでいる。左から $i$ 番目のモンスターは座標 $X_i$ にいて、体力は $H_i$ である。
以下の操作をモンスターが全滅するまで繰り返す。

座標 $x$ で爆弾を使う。すると、 $x - D$ 以上 $x + D$ 以下の範囲のモンスターに、 $A$ のダメージが入る。

全てのモンスターを倒すまでに、最低何回爆弾を使う必要があるか？

$1 \leq N \leq 2×10^{5}$
$0 \leq D \leq 10^{9}$
$1 \leq A \leq 10^{9}$
$1 \leq X_i \leq 10^{9}$
$1 \leq H_i \leq 10^{9}$

解法

各モンスターに対して何回爆弾を当てる必要があるかは、 $ceil(H_i / A)$ で求められる。

また、明らかに、体力がまだ残っているような一番左にいるモンスターをギリギリ含むようにして爆弾を爆発させるのが最適。
これを元に操作を言い換えると、 あるモンスター $i$ に対して爆弾を仕掛け、 $X_i + 2 × D$ の範囲にまで爆発が及ぶ となる。ここまではOK。
問題は、「各モンスターが何回爆発を喰らったか」をどう管理するか。
毎回爆発が及ぶ範囲のモンスターの体力を減算していくのはTLEするから、うまい方法を考える必要がある。（セグ木は今回はなしで）

ここで発想を転換して、
「各モンスターが何回爆発を喰らったか」→ 「次に見るモンスターが何回爆発を喰らったことになっているのか」に意識を変える。
すると、「これまでの爆発を累積的に積み重ねていく」という発想が出てくる。

あるいは、問題を超簡単にして、 $D$ が果てしなく大きな数字な場合を考えてもいい。
$X_i + 2 × D$ が最も遠い $X$ を包んでしまうような場合、何回爆発を喰らったのか、は累積的に増えていくことがわかる。

しかし実際の問題では、 $D$ の値によって累積の爆発回数が減少するタイミングがある。
ここでどうにかして出したいのが、 『期限切れ』 というキーワード。
つまり、「ある地点 $X_i$ で起こった爆発が届かなくなった時点で、累積の爆発回数から、 $X_i$ で起こった爆発の回数を引く」処理を行えばいい。

ここでの期限は、爆発が届かなるなる座標のこと。
このこの期限には明らかに単調性があるので、期限切れの爆発の削除はそれぞれ高々１回までしか起こらない。
よって普通にキューで管理できる。

詳しくは実装で。

実装

from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    # 期限切れの蓄積ダメージを削除
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * D, need])

print(ans)

感想

！！！！！！！！！！！！！！
すごい勉強になった。『期限切れ』 というキーワード、めちゃめちゃ便利そう。
超絶汎用性のある思考パターンな気がします。絶対に身に付けてみせる。