この問題では、下側凸包を求める必要があります。下側凸包及びそれを求めるアルゴリズムについては Monotone Chainを参考にしてください。

極限を考えるのは難しいので、以下のように問題を言い換えます。

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

言い換え後の問題の答えを \(\mathrm{ans}\) としたとき、元の問題の答えは \(\frac{1}{\mathrm{ans}}\) と一致することがわかります。

言い換え後の問題は、各品物を非負実数個選べることから、以下のように全ての品物の価値が \(1\) であるように言い換えてもよいことがわかります。

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

各品物を、二次元平面上の座標 \((A'_i,B'_i)\) にプロットします。このとき、プロットした点の下側凸包に含まれない点は選ぶ必要がないことが証明できます。

また、同様の議論から下側凸包の点を \(3\) 種類以上選ぶ必要がないこと、下側凸包で隣接していない \(2\) 点を共に選ぶ必要がないことが言えます。

これらの事実から、下側凸包に含まれる頂点及び下側凸包の線分それぞれについて、\(\mathrm{max}(x,y)\) の最小値を求めれば問題に答えることができます。

頂点については全て探索すればよいです。線分については、\(x-y\) が一次関数になっていることを用いると、\(\mathrm{max}(x,y)\) の最小値は \(\mathrm{O}(1)\) で求めることができます。詳しくは実装例を参考にしてください。

下側凸包を求めるのに \(\mathrm{O}(N\log N)\) かかり、\(\mathrm{max}(x,y)\) の最小値を求めるのは \(\mathrm{O}(N)\) で可能なので、この問題は \(\mathrm{O}(N\log N)\) で解くことができます。

実装例(c++)