ABC 034 D-食塩水

D - 食塩水
問題を見ると, とてもDPがしたくなります. 入力のアルファベットがNとKでそれぞれ制約1000以下, 解説でO(NK)で解けます!と書いてあるところまで想像しDPを考えました. しかし, 食塩水の濃度をテーブルにもたせるとすれば, 水の重さも共に持たせなければ遷移が考えられません. そのためDPは挫折し, あっさり解説を見ました.
適当にK個容器を選んだときの濃度pは
\begin{equation} p = \frac{\sum_{i=0}^K w_ip_i}{\sum_{i=0}^K w_i} \end{equation}
と記述できます. ここで, 『ある濃度pを与えたとき, その濃度より大きい食塩水を作れるか？』という問題を考えます. つまり,
\begin{equation} p \leq \frac{\sum_{i=0}^K w_ip_i}{\sum_{i=0}^K w_i} \end{equation}
を満たすようにpをK個選べるかどうか(True or False)という問題です. この式を変形すると,
\begin{equation} \sum_{i=0}^K w_i(p_i-p) \geq 0 \end{equation}
という式になります. pは固定されているので, できるだけw_i(p_i-p)が大きいようなものを取ってくることで, この式が実現可能かどうかが決定します. この問題は各iについてw_i(p_i-p)のソートがネックとなり, O(N log N)で解くことができます.
上の問題に対し, あるpが作成可能であったとき, それより大きな濃度の食塩水が作れることが期待できます. 不可能だったときはpを下げて再び実行...と考えていくと, 二分探索が適用できることがわかります.
このpを十分な回数二分探索することで, 解を求めることができます. 繰り返し一回につき誤差が半分となるため, 100回も繰り返しておけば十分すぎると思います. 繰り返し回数Qとすると全体の計算量はO(QN log N)となります.

Submission #2968930 - AtCoder Beginner Contest 034