ABC063 D - Widespread
解法
全員を倒すまでにかかる回数が、最悪回なので、かぐらいまで計算量を落としたいです。
すると、倒すのにかかる回数を二分探索すると、うまくとlogの計算量に落ち着きそうです。
倒すのにかかる回数を二分探索するということで、
回魔法をうったときに全ての魔物を倒せるかどうか、ということをぐらいで調べることができれば、あとは二分探索するだけになります。
回魔法をうつので、全ての魔物に対してのダメージが入ります。
回分、任意の1体には、のダメージの代わりにのダメージを与えることができます。 これは、を上乗せで回与えるのと同じことです。
ということで、のダメージで倒しきれていない相手に対して、回分ののダメージを与えることで、全ての魔物を倒しきることができれば、回の魔法で相手を全滅させることができます。
逆に、1体でも体力が1以上余っていれば、回の魔法では倒しきることができません。
あとは、魔法をうって相手を全滅させることのできる回数の最小値を二分探索で求めれば、この問題が解けます。