ARC050 B - 花束 - ツバサの備忘録

解法

$P$ 個の花束を作成できるかどうか、を調べます。
まず、2種類の花束どちらも、1つの花束につき少なくとも1本使用することになるので、最低 $P$ 本ずつ使用することになります。
この部分を除くと、

赤い花を $x-1$ 本使用する
青い花を $y-1$ 本使用する

の2通りの操作どちらかを行うことで、1つの花束を作成することができます。
ので、結局、
$\frac{R-P}{x-1} + \frac{B-P}{y-1} \geqq P$
であれば、 $P$ 個の花束を作成することができます。
この条件を調べて、 $P$ 個の花束を作成することができるとわかったとき、 $P$ 個未満の花束は明らかに作成することができます。
ということで、単調性が存在するため、上の条件を満たす最大の $P$ を二分探索で求めれば答えとなります。

感想

個数を決め打ち、どちらか片方のコストを0にして考えやすくする、といったよくある考え方が詰まっている気がします。