Atcoder解いてみた AtCoder Beginner Contest C - Sake or Water

AtCoder Beginner Contest C - Sake or Water

問題はこちら

回答

以下がポイントだった

1. N - K個のカップに水が入っているため、日本酒を飲むためには、N - K個より多くのカップを空にする必要
2. 最低限何個の日本酒のカップが必要か求めた上で、最低でも合計何個のカップが必要か求める
3. たくさんの液体に水が入っていると、最低限飲むべきカップ数が増えるため、それも考慮する必要(選んだカップのうち、最大で N-K 個は水である可能性がある そのため、確実に飲める日本酒量は「選んだカップの中で小さい側の一部」になる)
4. 高橋君が各カップに何ml入っているのか知っている

1,2は把握でき、配列をソートすればO(N logN)程度の計算量に収まりそうとまでは考えることができた
しかし、他の2つのポイントには気づけずWA、、、
特に、4に関しては、「入力で与えられている情報 = 問題参加者も高橋君も知っている情報」と今後は解釈することとする
以下、ヒントを元に作成したコード

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>


int N;
int K;
long long X;

std::vector<long long> A;

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> K >> X;

	for (int i = 0; i < N; i++) {
		long long a;
		std::cin >> a;
		A.push_back(a);
	}

	std::sort(A.begin(), A.end(), std::greater<long long>());

	// N - K個のカップに水が入っているため、日本酒を飲むためには、N - K個より多くのカップを空にする必要
	// 最低限何個の日本酒のカップが必要か求めた上で、最低でも合計何個のカップが必要か求める
	// たくさんの液体に水が入っていると、最低限飲むべきカップ数が増えるため、それも考慮する必要

	// 前提 : 高橋君が各カップに何ml入っているのか知っている
	int count = 0;
	long long total = 0;

	// 日本酒は1~Kカップ飲める
	for (int i = 0; i < K; i++) {

        // 選んだカップのうち最大 N-K 個は水の可能性がある
        // そのため、確実に日本酒として飲めるのは、選んだカップ数が N-K 個を超えた分だけ
		// ただし、液体がたくさん入っているカップに水が入っているケースも考慮し、Aは降順ソート
		total += A[N - K + i];
		if (total >= X) {
			int count = i + 1; // 再最低限飲む必要がある日本酒のカップ数
			std::cout << N - K + count << std::endl;
			return 0;
		}
	}
	std::cout << -1 << std::endl;
	

	return 0;
}