ABC034 D 食塩水
あらかじめ$ p_iを濃度ではなく食塩の量に置き換えておく. すると問題は「単位重さあたりの食塩の量を最大化せよ」という問題に帰着できる. これは蟻本3-1章 例題の, 平均最大化問題と同値である. ここでも詳しく解説しておく.
条件$ C(x):= 単位重さあたりの食塩の量が$ x以上となるように選ぶことができる とすると, $ C(x)を満たすような最大の$ xを求める問題となる. $ C(x)の判定について考える. まず, ある品物の集合$ Sを選んだとする. そのときの単位重さあたりの価値は$ \frac{\sum_{i \in S}v_i}{\sum_{i \in S}w_i}となるので, $ \frac{\sum_{i \in S}v_i}{\sum_{i \in S}w_i} \geq xなる$ Sが存在するかどうか調べればよいことになる. これを変形すると, $ \sum_{i \in S}(v_i - x \cdot w_i) \geq 0となるので, $ v_i - x \cdot w_iの値でソートして貪欲に選ぶことができるようになる. よってこの問題を二分探索を用いて判定問題を解いていくことで, $ O(N \log N)で解けた.