まずは，爆弾を使う座標について考える． ダメージの入る範囲を \([x-d, x+d]\) でなく， \([x', x'+2d]\) と考える． 中途半端な位置で爆弾を使うメリットは無いため， 爆弾を使うときに左端に敵が居ると仮定してよい． 言い換えれば，左端に敵が居ない使い方をした場合は， 左端に敵がいる場所に置き換えた最適解が存在する．
爆弾を使う座標 \(x\) を与えたとき， ダメージの入る座標の範囲は \([x, x+2d]\) であるから， ここに居る敵を高速に求めたい． これは，敵を座標によりソートしておけばよい． 左端の敵から，爆弾を使うか全探索していく．
次にダメージ処理する． 爆弾を使ったとき，愚直に \([x,x+2d]\) の範囲にダメージを加算すると， 範囲が大きいときに全体で \(O(N^2)\) となる． そこで，ダメージの累積を求めておいて，実際にダメージを反映させるのを保留しておく．
これは imos 法で実装できる． \(i \in [0,N), j \in [1,N+1)\) に対して， 区間 \([i,j)\) に対してダメージ \(dmg\) を与えるとき， \(ev[i] += dmg, ev[j] -= dmg\) とすればよい． \(ev_{i}\) が，モンスター \(i\) に与えるダメージの累計となる．
今調べているモンスターを \(i \in N\) とする． 先にダメージを処理して，まだ体力が残っていたら モンスター \(i\) を倒すのに必要最低限の回数だけ爆弾を使えばよい． つまりソートさえしておけば，使う回数が貪欲に求まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
