問題

$N$ 体の所持モンスターから4匹以上、 $M$ 体のお助けモンスターから0匹以上選んでモンスターを合成する。合成されたモンスターの強さは、(使用したモンスターの魔力の和)/(使用したモンスターの質量の和)で定義される。合成できるモンスターの最大の強さを求める。

atcoder.jp

考察

選んだモンスター $i$ の質量を $A_i$ 、魔力を $B_i$ とすると、モンスターの強さは $\frac{\sum B_i}{\sum A_i}$ になる。解 $X$ は、不等式 $\frac{\sum B_i}{\sum A_i} \geq x$ を満たす最大の $x$ と一致するので、二分探索で求められそうである。