AtCoder

ABC358 D問題(Souvenirs)を解く

AtCoder_ABC358_D

AtCoder が提供しているABC(AtCoder Beginner Contest)358 D問題をC++で解いてみました。ABC358は、2024年6月15日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Souvenirs(Difficulty : 393)

問題の詳細は、リンク先をご覧ください。

ABC358 D問題 Souvenirs

それぞれの人に条件を満たす最低金額のお土産を渡します。AtCoder Problems による Difficulty は 393 でした。

解答案

$M$ 人のそれぞれの人に $B_i$ 以上の最低金額のお土産を渡せば最小となります。つまり貪欲法で解くことができます。この解法は直感的に理解できますが、厳密な証明は公式解説で説明されています。

C++ プログラム例(ABC358D)

コードの補足をします。

  • すべてのお土産の値段を set コンテナ a に格納します。
  • それぞれの b[i] 以上の最も小さい金額のお土産を lower_bound で求めます。
    • そのようなお土産がなければ、-1 を出力して終了します。
  • 求めたお土産を変数 result に加えて、set コンテナ a から削除します。
  • 最後に result を出力します。

以下が、C++プログラムです。

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

typedef long long int ll;

int main()
{
	int n, m;
	cin >> n >> m;
	multiset<int> a;
	for (int i = 0; i < n; ++i) {
		int t;
		cin >> t;
		a.insert(t);
	}
	vector<int> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
	}

	ll result = 0;
	for (int i = 0; i < m; ++i) {
		auto it = a.lower_bound(b[i]);
		if (it == a.end()) {
			cout << -1 << endl;
			return 0;
		}
		result += *it;
		a.erase(it);
	}

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python の ordered set について

Python には標準で順序付きの set がありません。ネットで探すといくつかの実装を見つけることができますが、記事として取り上げることを見送ります。

最後に

少し難しいですが、ABC308F問題解説記事)が類題となります。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA