B - Make N Editorial by PCTprobability
\(Y=\min(Y,AX),Z=\min(Z,BX)\) として解いてもよいです。 一般性を失わず \( \frac{Y}{A} \le \frac{Z}{B}\) とします。(そうでない場合は \(Y\) と \(Z\), \(A\) と \(B\) を swap すればよいです。)
\(P\) を \(A\) 増やす操作をする回数は、高々 \(\left \lfloor \frac{N}{A} \right \rfloor\) 回です。もし \(\left \lfloor \frac{N}{A} \right \rfloor\) 回よりも多く操作をした場合、\(P > N\) となってしまい目標を達成できないためです。
\(P\) を \(B\) 増やす操作をする回数は、高々 \(A-1\) 回としてよいです。もし \(A\) 回以上した場合、「\(P\) を \(B\) 増やす操作を \(A\) 回」を 「\(P\) を \(A\) 増やす操作を \(B\) 回」に交換することでコストの総和が大きくなることはないからです。
よって、\( \left \lfloor \frac{N}{A} \right \rfloor < A - 1\) の場合は \(P\) を \(A\) 増やす操作をする回数を全探索し、そうでない場合は \(P\) を \(B\) 増やす操作をする回数を全探索すればよいです。計算量は \(\mathrm{O}(T\sqrt N)\) です。
posted:
last update: