平均値を最大化するような実数の対を選ぶ問題

問題設定

n個の正の実数の対 $A_i,B_i$ ( $1 \le i\le n$ )と，n以下の自然数kが与えられる．
この中からk個の対 $A_\nu_j,B_\nu_j$ ( $1 \le j \le k$ )を選び，
$T=\frac{A_\nu_1+\cdots+A_\nu_k}{B_\nu_1+\cdots+B_\nu_k$ …(*)
を最大化したい．
どのように対を選べば良いだろうか．

解法

(*)式を変形して次のようにする．
$\sum_{j=1}^{k}{A_\nu_j-TB_\nu_j}=0$
ここで，総和における各要素 $A_\nu_j-TB_\nu_j$ に着目し，Tを変数とみなして $C_i(T)=A_i-TB_i$ とおく．すると(*)は
$\sum_{j=1}^{k}{C_\nu_j(T)}=0$ …(**)
と変形される．

Tにはある値が選ばれているとする．(**)が成り立つような $C_i(T)$ を選ぶ方法を考える．
Tを固定した場合において(**)の左辺を最大化するには， $C_i(T)$ を大きい順にソートして大きいものから順にk個取ればよい．これを $M(T)$ とおく．
$M(T)>0$ であるとき，(**)を成り立たせるには

1. $C_i(T)$ の中から適当なものをk個選びなおす
2. Tの値を増加させて $C_i(T)$ を減少させる

の2通りがあるが，この問題ではTの値を最大化するのが目的なので2.の手段をとる．
また， $M(T)<0$ であるときは対をどう取っても(**)の左辺は負になるので，Tの値を減少させるほかない．

上記の方法でTの値で2分探索を行えば，最大値が得られる．

計算量

2分探索において初期値は下限を0,上限を $\max(A_i/B_i)$ に取ればよいので2分探索は $\log{\max(A_i/B_i)}$ 回行われる．
ソートのオーダーは $n\log{n}$ なので，全体の計算量は $\Theta(n\log{n}\times\log{\max(A_i/B_i)})$ となる．