AtCoder が提供しているABC（AtCoder Beginner Contest）308 のF問題をC++で解いてみました。ABC308は、2023年7月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Vouchers（Difficulty : 1284）
問題はリンク先をご覧ください。
商品に対してクーポンが1回しか使えないため貪欲法で解けます。AtCoder Problems による Difficulty は 1284 でした。
解答案
消費するクーポンの割引 Di を最大化する問題です。以下の2つの貪欲法が考えられます。
- 貪欲法1
割引 Di が大きい順にクーポンを使用する。使える範囲でもっとも安い商品にクーポンを使用する。 - 貪欲法2
商品の定価が安い順にクーポンを使用する。使える範囲でもっとも割引が大きいクーポンを使用する。
どちらの解法も AC を得ることができます。紙に書きだすなどしてシミュレーションすれば（証明できたことにはなりませんが）正しい気がします。
貪欲法の証明は以下を確認する場合が多いようです。
- 貪欲法の証明方針1
貪欲法で求めた最適解に対して、その解を入れ替えても状況が良くならないことを示す。 - 貪欲法の証明方針2
任意の解に対して、それを貪欲法で求めた最適解に入れ替えても状況が悪くならないことを示す。
貪欲法1の証明方針2に従った厳密な証明は、このユーザ解説で詳しく紹介されています。
C++ プログラム例（ABC308F）
上で考察した貪欲法1で解いてみます。
商品の定価は、二分探索を使うこと、削除すること、同じ定価がありえることから multiset を使います。
クーポンが使える下限 Li と割引 Di は、割引が大きい順にソートしておきます（29ー37行目）。
プログラムの本質的な部分は以下となります。
- クーポンの割引が大きい順に以下を処理する。
- クーポンが適用できる定価が一番安い商品を探す（40行目）。
商品がなければ次のクーポンを処理する。 - 商品定価の総額から割引 Di を引く（42行目）。
- 適用した商品を対象から外す（43行目）。
- クーポンが適用できる定価が一番安い商品を探す（40行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n, m;
cin >> n >> m;
ll result = 0;
multiset<int> p;
for (int i = 0; i < n; ++i) {
int temp;
cin >> temp;
p.insert(temp);
result += temp;
}
vector<int> L(m);
for (int i = 0; i < m; ++i) {
cin >> L[i];
}
vector<int> D(m);
for (int i = 0; i < m; ++i) {
cin >> D[i];
}
vector<pair<int, int>> coupon;
for (int i = 0; i < m; ++i) {
coupon.push_back(make_pair(-D[i], L[i]));
}
sort(coupon.begin(), coupon.end());
for (int i = 0; i < m; ++i) {
L[i] = coupon[i].second;
D[i] = -(coupon[i].first);
}
for (int i = 0; i < m; ++i) {
auto it = p.lower_bound(L[i]);
if (it != p.end()) {
result -= D[i];
p.erase(p.find(*it));
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python の ordered set について
Python には、標準で順序付きの set がありません。ネットで探すといくつかの実装を見つけることができますが、記事として取り上げることを見送ります。ABC281E問題、ABC306E問題の場合と同様です。
最後に
貪欲法は、実装するプログラムはそれほど難しくない傾向があります（一番状況がよいものを選んでいくだけなので）。ただし、最近の出題では、ABC270D問題のように貪欲法を適用することが正しくない場合もあります。ある程度の難易度の貪欲法を使う問題は、貪欲法を使えば解けることに確信を持つこと自体が難しいと考えています。
コンテストは時間が限られているため、厳密な証明をすることが難しい場合の方が多いと思われます。問題に触れる量が増えれば、素早く見極めることができるようになるのかもしれません。
引き続き ABC の問題を紹介していきます。
