AtCoder が提供しているABC(AtCoder Beginner Contest)358 D問題をC++で解いてみました。ABC358は、2024年6月15日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Souvenirs(Difficulty : 393)
問題の詳細は、リンク先をご覧ください。
それぞれの人に条件を満たす最低金額のお土産を渡します。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 の問題を紹介していきます。