人間だけど競プロやる

解けなかった問題を理解できたら記事を投稿します。日本語の解説が見つからなかったもの中心。

codeforces Educational Codeforces Round 162 (Rated for Div. 2) B. Monsters Attack!

公式解説は、インデックス1まで移動してきた敵を一気に倒す。
使わずに余った弾丸は次のターンに持ち越すことにしても結果は変わらない。
というもの。
気づかずに少しめんどくさい解法をつかったのでメモしておく。


敵を攻撃し始めないと間に合わない締め切りを求める。
締切は  X[i] - \lceil \frac{A[i]}{K} \rceil
これをpriority queueにいれて。締切が早い順に処理していく。
各ターンで、残弾がある限り、もっとも締切が近いものを、1ターン締切を伸ばすように処理してpriority queueに入れなおす。
締め切りを伸ばすのに必要なダメージは  A[i]\bmod  K (ただし0のときはK) で求める。
締め切りが現ターンより小さければNOを出力。
(締め切りが近いものからKダメージをフルに使うとWAなので注意)