問題リンク
問題概要
数直線上に\(N\)体のモンスターがいる。それぞれのモンスターは座標\(X_i\)にいて、体力は\(H_i\)である。
次の操作を好きなだけおこなう。
- 好きな座標\(x\)を選び、爆弾を使用する。このとき座標が\(x-D\)以上\(x+D\)以下のモンスターの体力が\(A\)減る。
全てのモンスターの体力を0以下にする為の爆弾の使用回数の最小値を求めよ。
解法
考えやすくするために、爆弾の効果範囲を\([x-D,x+D]\)ではなく\([x,x+2D]\)とする。
そうすると、\(x\)の候補としてはモンスターのいる位置だけを考えればよくて、イベントソートが使える。
効果が適用されている爆弾の個数を「手持ち爆弾個数」、使用が確定した爆弾の個数を「累計個数」と呼ぶことにする。
次のイベント2種類を考える。
- イベント１：このイベントではモンスターを倒す。
モンスターの体力が\(A \times (手持ち爆弾個数)\)以下ならば、何もしない。
そうでなければ、モンスターを倒せるだけの追加の爆弾の個数(これを\(t\)と置く)を手持ち個数と累計個数に加え、さらに座標\(x+2D\)に手持ち爆弾個数を\(t\)個減らすイベント(この後に出てくるイベント２)を挿入する。 - イベント２：手持ち爆弾個数を\(t\)個減らす。
最初に各モンスターの座標にイベント１を挿入し、座標が小さい順に処理した後の最終的な爆弾の累計個数が答え。
また、イベント１と２が重なる時の処理の順番に注意する。上の例ではイベント１を先に処理しなければならない。
提出
https://atcoder.jp/contests/abc153/submissions/9751288
(上の解法とイベント１と２が逆になっています)
感想
早く解けたと思ったのに、提出後に順位表見てびっくりした。
