ABC034-D:食塩水(400)
問題
https://beta.atcoder.jp/contests/abc034/tasks/abc034_d
N 個の食塩水があり、i 番目の容器には濃度 p_i パーセントの食塩水が w_i グラム入っている。K 個の食塩水を選んだ時の最大の濃度を求めよ。
制約
- 1 <= N,K <= 1000
- 1 <= w_i <= 109
- 1 <= p_i <= 100
考え方
二分探索の典型問題。「K 個選んで濃度 m パーセント以上の食塩水を作ることができるかどうか」という条件のもと m を最大化することで解を貪欲に求めることができる。
N の部分列を n_1, n_2, ..., n_k とする。題意の満たす食塩水の濃度は
である。
これが m 以上になるかどうかを判定する。すなわち
を判定すれば良い。左辺を最大にしたいので、n 個の中から w_n[i] * (p_n[i] - k) を大きい方から K 個足し合わせればいい。m 以上の値を取ることができなければ、 m の値を m 未満の m' として条件を満たすかどうか判定すれば良い。計算量はlistのソート時が最大で O(N logN) となる。
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(), k = in.nextInt(); double[] w = new double[n], p = new double[n]; for (int i = 0; i < n; i++) { w[i] = in.nextDouble(); p[i] = in.nextDouble(); } double l = 0, r = 100, m = -1; for (int i = 0; i < 1000; i++) { m = (l+r)/2; List<Double> list = new ArrayList<>(); for (int j = 0; j < n; j++) { list.add(w[j] * (p[j] - m)); } Collections.sort(list, Comparator.reverseOrder()); double sum = 0; for (int j = 0; j < k; j++) { sum += list.get(j); } if (sum >= 0) { l = m; } else { r = m; } } out.println(m); }
ポイント
- ある状態から選択できる値の最大化、最小化、という問いは二分探索を考えてみる