【AtCoder】ABC 441 C - Sake or Water

2026-01-24

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 406 / NoviSteps: 2Q / 配点: 300 点

問題概要

$N$ 個のカップがあり、 $i$ 番目のカップには $A_i \, \mathrm{[ml]}$ の液体が入っている。また、これらのうちちょうど $K$ 個のカップには日本酒が入っており、それ以外には水が入っている。ただし、どのカップに日本酒が入っているかは分かっていない。

高橋君は(1つ以上の)いくつかのカップを選んでそれらに入った液体をすべて飲むことができる。どのカップに日本酒が入っているかによらず、高橋君が確実に $X \, \mathrm{[ml]}$ 以上の日本酒を飲むためには、最低何個のカップを選ぶ必要があるか求めよ。そのような選び方が不可能である場合には $-1$ を出力すること。

制約

$1 \leq K \leq N \leq 3\times 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq X \leq 3\times 10^{14}$
入力はすべて整数

考察

このような問題は最悪なケースを考えてみると分かりやすい。

高橋君にとっての最悪なケースは、 $m$ 個のカップを選んだときに、残りの $N-m$ 個のカップに最大数の日本酒が入っている場合である。

もし $N - m \geq K$ であるならば、日本酒は全て選ばなかったカップに入ってしまう可能性があるので、少なくとも $N - m < K \iff m > N - K$ である必要がある。このとき、選んだ $m$ 個のカップの中に確実に含まれる日本酒が入ったカップの個数は $K - (N - m)$ となる。

したがって、確実に飲める日本酒の量は、「選んだ $m$ 個のカップのうち、入っている液体の量が少ない方から $K - (N - m)$ 個の合計」となる。これを最大化するためには、入っている液体の量が多い方から $m$ 個のカップを選べばよい。

よって、 $A_i$ を降順にソートし、 $m$ を大きくしながら $\displaystyle \sum_{i=N-K+1}^{m} A_i \geq X$ を満たす最小の $m$ を求めれば良い。

計算量は降順ソート部分がボトルネックとなり、 $O(N \log N)$ である。

実装例

24行目では、累積和の要領で確実に飲めるようになったカップの液体の量を足し合わせている。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rall(x) (x).rbegin(), (x).rend()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.using ll = long long;
8. 
9.// ======================================== //
10. 
11.int main()
12.{
13.    int N, K;
14.    ll X;
15.    cin >> N >> K >> X;
16.    vector<ll> A(N);
17.    rep(i, 0, N) cin >> A[i];
18. 
19.    sort(rall(A));
20. 
21.    ll ans = -1, sum = 0;
22.    rep(m, N - K + 1, N + 1)
23.    {
24.        sum += A[m - 1];
25.        if (sum >= X)
26.        {
27.            ans = m;
28.            break;
29.        }
30.    }
31. 
32.    cout << ans << endl;
33. 
34.    return 0;
35.}