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 とする。題意の満たす食塩水の濃度は

 \dfrac{w_{n_1} * p_{n_1} + w_{n_2} * p_{n_2} + ... + w_{n_k} * p_{n_k}}{w_{n_1} + ... + w_n{n_k}} である。

これが m 以上になるかどうかを判定する。すなわち

 \dfrac{w_{n_1} * p_{n_1} + w_{n_2} * p_{n_2} + ... + w_{n_k} * p_{n_k}}{w_{n_1} + ... + w_n{n_k}} \geqq m

 \Leftrightarrow w_{n_1} * (p_{n_1} - m) + w_{n_2} * (p_{n_2} - m) + ... + w_{n_k} * (p_{n_k} - m) \geqq 0

を判定すれば良い。左辺を最大にしたいので、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);

        }

ポイント

  • ある状態から選択できる値の最大化、最小化、という問いは二分探索を考えてみる