LoginSignup
1

More than 3 years have passed since last update.

ABC153 解説

Last updated at Posted at 2020-01-26

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分で書いたクオリティです、ごめんなさい…
今回のような典型問題が多いセットだとスピードが重要になるので、典型をよく知っておくことは大事です。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1