AtCoder が提供しているABC（AtCoder Beginner Contest）281 のD問題をC++とPythonで解いてみました。ABC281は、2022年12月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Max Multiple（Difficulty : 1031）
問題はリンク先をご覧ください。
DP（動的計画法）で解きますが、一工夫必要です。AtCoder Problems による Difficulty は、1031 でした。
解答案
問題から DP を使うことが予想できる問題です。
dp[i][j] は、a1, … , ai から、j 個選んだ最大値とします。漸化式は、ai を選ぶか、選ばないかで以下となります。
- dp[i + 1][j + 1] = dp[i][j] + ai+1
- dp[i + 1][j] = dp[i][j]
ただし、これでは、D の倍数の最大値は求まりません。ここからは、公式解説を参考にしました。
動的計画法で、解けない場合は、変数をひとつ増やせば解ける場合があります。この問題も D で割った余りをパラメータに増やせば解くことができます。
dp[i][j][m] は、a1, … , ai から、j 個選んだ数の和の最大値とします。m は、D で割った余りです。この場合は、漸化式は以下となります。
- dp[i + 1][j][m]
= 左辺の数と dp[i][j][m]) の大きい数 - dp[i + 1][j + 1][(m + ai+1) % D]
= 左辺の数とdp[i][j][m] + ai+1 の大きい数
上で示した漸化式に従い計算して、dp[N][K][0] が求める解答となります。
C++ プログラム例（ABC281D）
解説では、問題文に従い a1 から記載しました。プログラムでは、a0 からコーディングしました。このため、上の解説とiの添え字がひとつずれています。ループ変数は、いままで i、j、k と書いていました。問題で入力として k を使っているため、i、j、m としました。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n, k, d;
cin >> n >> k >> d;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector dp(n + 1, vector(k + 1, vector<ll>(d, -1)));
dp[0][0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
for (int m = 0; m < d; ++m) {
if (dp[i][j][m] == -1) {
continue;
}
dp[i + 1][j][m] = max(dp[i + 1][j][m], dp[i][j][m]);
if (j != k) {
dp[i + 1][j + 1][(m + a[i])%d]
= max(dp[i + 1][j + 1][(m + a[i])%d], dp[i][j][m] + a[i]);
}
}
}
}
cout << dp[n][k][0] << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC281D）
C++ のプログラムをそのまま Python として書き直しました。Python らしい書き方なのか、いまだに自信がありません。
"""AtCoder Beginner Contest 281 C"""
n, k, d = map(int, input().split())
a = list(map(int, input().split()))
dp = [[[-1 for i3 in range(d)] for i2 in range(k + 1)] for i1 in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
for j in range(k + 1):
for m in range(d):
if dp[i][j][m] == -1:
continue
dp[i + 1][j][m] = max(dp[i + 1][j][m], dp[i][j][m])
if j != k:
dp[i + 1][j + 1][(m + a[i]) % d] = \
max(dp[i + 1][j + 1][(m + a[i]) % d], dp[i][j][m] + a[i])
print(dp[n][k][0])こちらも「AC」と判定されました。
最後に
ABC281 は、C問題の Diffculty が131で、D問題の Diffculty が 1031 でした。C問題とD問題の間に谷があるような構成となりました。
D問題は、2変数DPで考えて解くことができませんでした。DPに慣れて、このような一工夫した問題も解けるようになりたいです。
引き続き ABC の問題を紹介していきます。
