[AtCoder] ABC 153 F – Silver Fox vs Monster

問題

方針

モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。

最適な攻撃方法

最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注目しているモンスターの座標に与えます。したがって、\( 1 \) 回目の爆弾の範囲は、\(  [X_1, X_1 + 2D] \) となります。この地点に落とす爆弾の回数 \( t_1 \) は、

\[ t_1 = \left \lfloor \dfrac{H_1 + A – 1}{A} \right \rfloor\]

となります。このとき、この範囲のモンスターには \( t_1D \) のダメージが与えられます。同様にして、モンスター \( 2 \) の体力が残っている場合も上記のように爆弾を使います。

爆弾の範囲に含まれるモンスター

上記の方法で爆弾を落とした時に含まれるモンスターを考えます。例えば、爆弾をモンスター \( i \) が範囲の最も左側にいるとします。このとき、\( X_j \leq X_i + 2D \) を満たす最大の \( j \) までのモンスターが爆弾の範囲に含まれます。これは、二分探索によって求めることができます。

ダメージの管理

ダメージの管理は遅延評価セグメント木を使って対応します。評価遅延セグメント木が詳しいです。遅延セグメント木は、

の問題が解ければこの問題も解くことができます。

コード