ABC 034 D - 食塩水 - BEN2のブログ

ABC 034 D - 食塩水に関連する、平均最大化についてのメモを残します。

参考

「プログラミングコンテストチャレンジブック」(蟻本)
プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
- 作者:秋葉拓哉,岩田陽一,北川宜稔
- 発売日: 2012/01/28
- メディア: Kindle版

濃度の大きいものから順に選ぶと WA

問題 : ABC 034 D - 食塩水

水色 diff の問題なので、濃度の大きいものから貪欲に選んでいくとダメなのだろうというメタ読みができる (ずるい)。
実際、次のケースでは、濃度の大きい順だと $100 \%$ と $50 \%$ の食塩水を選ぶことになるが、最大濃度となる選び方はこれではない。

ここで、

食塩水を $K$ 個選んで、濃度を $x \, [ \% ]$ 以上にできるかどうか

を考える。
ある食塩水の集合を $S$ とする。濃度 $x \, [ \% ]$ 以上の食塩水を作ることが可能ならば、

$\begin{aligned} \frac{ \displaystyle \sum_{i \, \in \, S} w_{i} p_{i} }{ \displaystyle \sum_{i \, \in \, S} w_{i} } \geq x \end{aligned}$

すなわち

$\begin{aligned} \sum_{i \, \in \, S} ( w_{i} p_{i} - x w_{i} ) &\geq 0 \end{aligned}$

を満たす $S$ が存在する。
$w_{i} p_{i} - x w_{i}$ の大きい $K$ 個を選び、その和が 0 以上であれば、 $x \, [ \% ]$ 以上を達成できる。
二分探索によって、達成可能な最大の $x$ を求めればよい。

#include <bits/stdc++.h>
using namespace std;

int N, K;
vector<long long> W(1000);
vector<int> P(1000);

// 濃度 x パーセント以上の食塩水を作れるか判定
bool func(double x) {
  // w_i * p_i - x * w_i が大きい K 個を選ぶ
  vector<double> tmp(N);
  for (int i = 0; i < N; i++) {
    tmp.at(i) = W.at(i) * P.at(i) - x * W.at(i);
  }
  sort(tmp.begin(), tmp.end(), greater<double>());
  double sum = 0;
  for (int i = 0; i < K; i++) sum += tmp.at(i);
  return sum >= 0;
}

int main() {
  cin >> N >> K;
  for (int i = 0; i < N; i++) cin >> W.at(i) >> P.at(i);
  // 二分探索により、達成可能な最大の x を求める
  double left = 0, right = 100.0000001;
  for (int i = 0; i < 100; i++) {
    double mid = (left + right) / 2;
    if (func(mid)) left = mid;
    else right = mid;
  }
  cout << fixed << setprecision(10);
  cout << left << endl;
}