Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

ABC063-D Widespread 解説

問題

D - Widespread

解説

問題を見るとまず全探索解が生えますがこれはTLEします.
ここで問題をぐっと睨むと, T回の爆発ですべての魔物を消し去れるならば,  T\le T'回の爆発でも可能なことがわかります, よって二分探索をすることで最小値を見つけることができます.

つぎに二分探索をする関数(T回の爆発で可能かどうかのbool関数)を実装する必要があります.
これは爆破のダメージをよくみると、まず全員にT\times Bのダメージを与えてから生き残っている魔物に(A-B)のダメージを与えていくという操作と同値なことが分かります.

これで考察は終わりです, オーバーフローに注意して実装しましょう.

コード

Submission #1890890 - AtCoder Beginner Contest 063

感想

初めての関数上のにぶたんだった.