AtCoder が提供しているABC（AtCoder Beginner Contest）322 のE問題をC++で解いてみました。ABC322は、2023年9月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Product Development（Difficulty : 1193）
問題はリンク先をご覧ください。
ABC322 E問題 Product Development
次元は多いですが、ナップサック問題と考えることができます。AtCoder Problems による Difficulty は 1193 でした。
解答案
C++ プログラム例（ABC322E）
もし、$K = 1$ であれば、ある価値以上となる荷物の重さの最小値を求めるナップサック問題と同一視できます。
漸化式は以下となります。
- dp[i][j]：i 個目までのアイテムを選択したときに価値（パラメータ）が j となるコストの最小値とします。
- dp[i+1][j] = min(dp[i+1][j], dp[i][j])
i 個目のアイテムを選択しなかったことに該当します。 - dp[i+1][j+a[i]] = min(dp[i+1][j+a[i]], dp[i][j]+c[i])
i 個目のアイテムを選択したことに該当します。 - 初期値は、dp[0][0] = 0、それ以外は無限大（十分に大きな数）とします。
この漸化式を $K$ の最大値である5次元にまで拡張します。また価値（パラメータ）は、$P$ 以上を $P$ と扱います。このため、6重ループとなり読みにくくなりました。
以下が、最終的なC＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int main()
{
int n, k, p;
cin >> n >> k >> p;
vector<ll> c(n);
vector<vector<int>> a(n, vector<int>(5, p));
for (int i = 0; i < n; ++i) {
cin >> c[i];
for (int j = 0; j < k; ++j) {
cin >> a[i][j];
}
}
ll dp[n + 1][p + 1][p + 1][p + 1][p + 1][p + 1];
for (int i = 0; i <= n; ++i) {
for (int j0 = 0; j0 <= p; ++j0) {
for (int j1 = 0; j1 <= p; ++j1) {
for (int j2 = 0; j2 <= p; ++j2) {
for (int j3 = 0; j3 <= p; ++j3) {
for (int j4 = 0; j4 <= p; ++j4) {
dp[i][j0][j1][j2][j3][j4] = INF;
}
}
}
}
}
}
dp[0][0][0][0][0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j0 = 0; j0 <= p; ++j0) {
for (int j1 = 0; j1 <= p; ++j1) {
for (int j2 = 0; j2 <= p; ++j2) {
for (int j3 = 0; j3 <= p; ++j3) {
for (int j4 = 0; j4 <= p; ++j4) {
if (dp[i][j0][j1][j2][j3][j4] == INF) {
continue;
}
dp[i + 1][j0][j1][j2][j3][j4] = min(dp[i + 1][j0][j1][j2][j3][j4], dp[i][j0][j1][j2][j3][j4]);
dp[i + 1][min(j0 + a[i][0], p)][min(j1 + a[i][1], p)][min(j2 + a[i][2], p)][min(j3 + a[i][3], p)][min(j4 + a[i][4], p)] =
min(dp[i + 1][min(j0 + a[i][0], p)][min(j1 + a[i][1], p)][min(j2 + a[i][2], p)][min(j3 + a[i][3], p)][min(j4 + a[i][4], p)],
dp[i][j0][j1][j2][j3][j4] + c[i]);
}
}
}
}
}
}
ll result = INF;
for (int i = 1; i <= n; ++i) {
result = min(result, dp[i][p][p][p][p][p]);
}
if (result == INF) {
cout << -1 << endl;
} else {
cout << result << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
C++版プログラムは、自分の理解しやすい形で書いたため、分かりやすい形となっていません。この記事では、Python版プログラムを紹介することを見送ります。
最後に
このブログでは、ABC269から解説記事を紹介していました。この問題の解説で、難易度緑（Difficulty 800 ～ 1199）のすべての問題を解説することができました。
ABC269からしばらく、難易度緑の問題を解くことができなかったので、進歩を感じます。
引き続き ABC の問題を紹介していきます。
