AtCoder

ABC281 D問題(Max Multiple)を解く

AtCoder_ABC281_D

AtCoder が提供しているABC(AtCoder Beginner Contest)281 のD問題をC++とPythonで解いてみました。ABC281は、2022年12月10日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Max Multiple(Difficulty : 1031)

問題はリンク先をご覧ください。

ABC281 D問題 Max Multiple

DP(動的計画法)で解きますが、一工夫必要です。AtCoder Problems による Difficulty は、1031 でした。ABC D問題としては、やや難しい問題です。

解答案

問題から 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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA