初めに

atcoder.jp 解けなかったので

敗因

典型1 最大/最小から K 番目の要素は答えで二分探索する←知ってた

典型2 ふたつの組み合わせの数え上げは, 片方を固定してみる←知ってた

典型3(?) 砂糖/食塩水の問題はある濃度に達するまでの砂糖の量とかをみるといい←知らなかった

「 x % 以上の溶液が K 個以上あるような最大の x を求める」問題に言い換える.

これは「 x % 以上の溶液はいくらあるか?」という問題を用いて二分探索できる.

全ての溶液に対して, 「 x %にするための砂糖の量との差」を求めておいてソートしておくことで, 片方を固定したときに二分探索を用いて, その溶液と混ぜた時に x % 以上になる溶液の個数が分かる.

よって, $O(log \, \frac{1}{\varepsilon} \, N \, log \, N)$ で答えを求めることができた.( $\varepsilon$ は許容される最大誤差)

くやしい...