\(N\) 種類の品物があり、\(i\) 種類目の品物は重さ \(A'_i=\frac{A_i}{C_i}\)、体積 \(B'_i=\frac{B_i}{C_i}\)、価値 \(1\) である。各品物を、選んだ品物の価値の合計が \(1\) になるようにそれぞれ非負実数個 選ぶことができる。このとき、選んだ品物の \(\mathrm{max}\)(重さの合計、体積の合計) の最小値を求めよ。

公式解説で言い換えられたこの問題は二分探索で解くことが出来ます。判定問題「上記問題の答えは \(m\) 以下か」は、次の問題に等しいです。

\(N\) 種類の品物があり、\(i\) 種類目の品物は重さ \(A'_i=\frac{A_i}{C_i}-m\)、体積 \(B'_i=\frac{B_i}{C_i}-m\)、価値 \(1\) である。各品物を、選んだ品物の価値の合計が正になるようにそれぞれ非負実数個 選ぶことができる。このとき、選んだ品物の \(\mathrm{max}\)(重さの合計、体積の合計) を \(0\) 以下に出来るかを判定せよ。

この判定問題において選ばれた品物の個数の比を保ったまま合計が \(1\) になるようにしても結果が変わらないため、元の「価値の合計が \(1\)」という制約が「価値の合計が正」になっています。

判定問題の解き方を考えます。まず、\(A_i'\leq 0\) かつ \(B_i' \leq 0\) を満たす品物があれば答えは Yes です。そのような品物が存在しない場合、品物は以下の \(3\) 種類に分けられます。

1. \(A_i' \geq 0\) かつ \(B_i' \geq 0\)
2. \(A_i'\lt 0\) かつ \(B_i' \geq 0\)
3. \(B_i'\lt 0\) かつ \(A_i' \geq 0\)

ここで、\(1\) 番目の品物は役に立ちません。また、\(2,3\) 番目の品物は定数を掛けることで \(A_i'=-1\) または \(B_i'=-1\) となります。この時、重さや体積への負の寄与に対してもう一方への正の寄与は小さい方が良いため、\(2,3\) 番目それぞれについて非負となる値が最小のもののみを考えれば良いです。

\(2,3\) 番目において考慮される品物が \((A_i',B_i')=(-1,a), (b,-1) (a,b \geq 0)\) であるとすると、条件は \(-x + by \leq 0\) かつ \(ax - y \leq 0\) となる正の実数 \(x,y\) が存在することです。これを検討すると \(ab \leq 1\) であることが必要十分条件となるため、これを判定することで元の問題が解けます。