AtCoder が提供しているABC（AtCoder Beginner Contest）312 のF問題をC++とPythonで解いてみました。ABC312は、2023年7月29日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Cans and Openers（Difficulty : 1534）
問題はリンク先をご覧ください。
缶切りの必要有無で缶詰を分けて、それぞれを組み合わせて満足度の最大値を求めます。AtCoder Problems による Difficulty は 1534 でした。
解答案
仮に缶切りが不要な缶しかないとします。この場合は簡単です。満足度が高い順に $M$ 個の缶詰を選べば、最大の満足度を得ることができます。
逆に、缶切りが必要な缶しかないとします。缶切りがない場合は、缶切りを個数が多い順に入手します。それで得た缶切りを使って、満足度が高い順に缶詰を選んでいきます。缶切りを多い順に、缶詰を満足度が高い順に $M$ 個の処理をします。貪欲法と言えます。
注）問題文から読み取りにくいですが、この問題では缶切りを缶詰に対して一度しか使えません。
缶切りが不要な缶しかない場合と、缶切りが必要な缶しかない場合を組み合わせて、最大値を求めます。
C++ プログラム例（ABC312F）
まず、缶切りが不要な缶しかない満足度を sum_a に累積和として格納します。累積和は満足度が多い順に計算します（27ー36行目）。
次に、缶切りが必要な缶しかない満足度を sum_b に累積和として格納します。缶切りを得る場合は、累積和を更新しません（42ー47行目）。缶詰は満足度が多い順に処理します（49ー55行目）。
最後に、この二つの累積和を $M+1$ 通り組み合わせて、最大値を求めます（59ー62行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n, m;
cin >> n >> m;
vector<ll> a, b, c;
for (int i = 0; i < n; ++i) {
int t;
ll x;
cin >> t >> x;
if (t == 0) {
a.push_back(x);
} else if (t == 1) {
b.push_back(x);
} else if (t == 2) {
c.push_back(x);
}
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
sort(c.begin(), c.end());
vector<ll> sum_a(m + 1);
sum_a[0] = 0;
for (int i = 0; i < m; ++i) {
if (a.size() > 0) {
sum_a[i + 1] = sum_a[i] + a.back();
a.pop_back();
} else {
sum_a[i + 1] = sum_a[i];
}
}
vector<ll> sum_b(m + 1);
sum_b[0] = 0;
ll opener = 0;
for (int i = 0; i < m; ++i) {
if (opener == 0) {
if (c.size() > 0) {
opener = c.back();
c.pop_back();
}
sum_b[i + 1] = sum_b[i];
} else {
if (b.size() > 0) {
--opener;
sum_b[i + 1] = sum_b[i] + b.back();
b.pop_back();
} else {
sum_b[i + 1] = sum_b[i];
}
}
}
ll result = 0;
for (int i = 0; i <= m; ++i) {
result = max(result, sum_a[i] + sum_b[m - i]);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC312F）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 312 F"""
n, m = map(int, input().split())
a = []
b = []
c = []
for i in range(n):
t, x = map(int, input().split())
if t == 0:
a.append(x)
elif t == 1:
b.append(x)
elif t == 2:
c.append(x)
a.sort()
b.sort()
c.sort()
sum_a = [0] * (m + 1)
for i in range(m):
if a != []:
sum_a[i + 1] = sum_a[i] + a.pop()
else:
sum_a[i + 1] = sum_a[i]
sum_b = [0] * (m + 1)
opener = 0
for i in range(m):
if opener == 0:
if c != []:
opener = c.pop()
sum_b[i + 1] = sum_b[i]
else:
if b != []:
opener -= 1
sum_b[i + 1] = sum_b[i] + b.pop()
else:
sum_b[i + 1] = sum_b[i]
result = 0
for i in range(m + 1):
result = max(result, sum_a[i] + sum_b[m - i])
print(result)こちらも「AC」と判定されました。
最後に
問題の構造が分かれば解きやすい問題でした。
引き続き ABC の問題を紹介していきます。
