ABC153 の解説です。
今回はかなり典型的なセットだったので、速く全完できると吉です。
A問題
割り算の切り上げ処理がしたいです。
あまりで場合分けしても良いですが、$A/B$ の切り上げは、 $(A+B-1)/B$ で計算できることを知っておくと便利です。
B問題
$A_i$ の総和と $H$ を比較するだけです。for文で回しましょう。
C問題
必殺技は、体力の高いモンスターに対して使ったほうがよいです。
体力の高い順に $K$ 個のモンスターに対して必殺技を使い、残りを攻撃で倒すようにします。
D問題
すべてのモンスターをまとめて攻撃すれば、体力の値は一定になるので、個数だけ考えればよくなります。
モンスターはだいたい $\log H$ 回攻撃すればなくなるので、これを愚直にシミュレーションすれば通ります。
オーバーフローには気を付けましょう。
E問題
典型的な動的計画法の問題です。
このタイプは、「個数制限なしナップザック問題」として有名です。蟻本にも載っています。
ただ、蟻本に載っているタイプとは少し異なり、添字に持つのがトキの魔力ではなく、モンスターの体力なので注意してください。
F問題
まず、一番左のモンスターについて考えると、爆弾は、ダメージがこのモンスターに入る中で一番右に設置するのが最適です。これは、他のモンスターに攻撃が入ることを考えれば明らかです。
そこで、今体力が残っている中で一番左にいるモンスターに注目し、その位置 $+D$ の座標に爆弾を設置して、そのモンスターが倒れるまで爆破します。
この処理をすべてのモンスターが倒れるまでシミュレーションすればよいです。
区間のモンスターの体力を減少させる処理をしたいので、遅延セグメントツリーを使えば簡単に実装できます。
座標の値域が大きいので、座標圧縮をして処理を遅延セグメントツリーに載せると $O(N\log N)$ になります。
当然ですが、一度ずつ爆破するのでなく、注目しているモンスターが倒れるまでまとめて爆破するようにしましょう。
どうでもいいですが、僕は座標のソートを忘れて1WAを出しました。
おわりに
この記事は20分で書いたクオリティです、ごめんなさい…
今回のような典型問題が多いセットだとスピードが重要になるので、典型をよく知っておくことは大事です。