モンスターは \(X_i\) の昇順にソートしておく. また, \(H_i\) は \(A\) で割って小数点切り上げておく.

モンスターの体力をいくつ減らせるかについては, 基本的には imos 法を使う. ただ, 愚直に使うと間に合わないので, 動的に爆弾を配置するようにする.

\(i\) 番目のモンスターの体力をいくつ減らせるかを配列 \(f(i)\) で用意する.

まず, 最初の爆弾は \(X_1 + D\) に \(H_1\) 個置くのが最適である. このとき, この爆弾の効果がある右端のモンスター \(i\) を二分探索で求める. そして \(f(1)\) に \(H_1\) を加算し, \(f(i+1)\) から \(H_1\) を減算する. そして imos 法の要領で \(f(2)\) を求める. \(f(2) \geq H_2\) ならそのまま \(f(3)\) の操作に移動し, そうでなければ新たに爆弾を \(X_2 + D\) に配置する. これを繰り返して置く爆弾の数を求める.