AtCoder

ABC364 E問題(Maximum Glutton)を解く

AtCoder_ABC364_E

AtCoder が提供しているABC(AtCoder Beginner Contest)364 E問題をC++とPythonで解いてみました。ABC364は、2024年7月27日21:00に実施されました。

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

E問題 Maximum Glutton(Difficulty : 1496)

問題の詳細は、リンク先をご覧ください。

ABC364 E問題 Maximum Glutton

DPのキーと値を入れ替えて計算量を下げます。AtCoder Problems による Difficulty は 1496 でした。

解答案

最初に上手く動かないプログラムを紹介します。

$DP_{i,j,k}$ は $i$ 個までの料理を対象として、甘さの合計 $j$ 、しょっぱさの合計 $k$ となるように選ぶ料理の最大数とします。出力する解答は、$DP_{N, j, k}$ の最大値に1を加えた値になります。プログラムは以下となります。

#include <bits/stdc++.h>
using namespace std;

#define INF 1000000001

int main()
{
	int n, x, y;
	cin >> n >> x >> y;

	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(x + 1, vector<int>(y + 1, -INF)));
	dp[0][0][0] = 0;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		for (int j = 0; j <= x; ++j) {
			for (int k = 0; k <= y; ++k) {
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
				if ((j + a <= x)&&(k + b <= y)) {
					dp[i + 1][j + a][k + b] = max(dp[i + 1][j + a][k + b], dp[i][j][k] + 1);
				}
			}
		}
	}

	int result = 0;
	for (int j = 0; j <= x; ++j) {
		for (int k = 0; k <= y; ++k) {
			result = max(result, dp[n][j][k]);
		}
	}
	result = min(result + 1, n);

	cout << result << endl;

	return 0;
}

構造としては、ナップザック問題と同じです。ただし、計算量は、$O(NXY) = 8 \times 10^9$ となるため、時間が間に合いません(メモリ使用量も制約を超える場合があるようです)。

$DP$ の値は、料理の最大数です。この値を甘さの合計の最小値に入れ替えます。合わせて、キーである甘さの合計は、選択した料理数に入れ替えます。つまり $DP_{i,j,k}$ を $i$ 個までの料理を対象として、$j$ 個の料理を選択した、しょっぱさの合計 $k$ となる甘さの合計の最小値とします。

この工夫により、計算量が $O(N^2Y) = 1.6 \times 10^7$ となり実行時間内に収まります。

C++ プログラム例(ABC364E)

解説したようにキー(甘さの合計値)と値(選んだ料理の最大数)を入れ替えます。dp の初期値は無限大INFとします。漸化式の表現は、プログラム20行目となります。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

#define INF 1000000001

int main()
{
	int n, x, y;
	cin >> n >> x >> y;

	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(y + 1, INF)));
	dp[0][0][0] = 0;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		for (int j = 0; j <= i; ++j) {
			for (int k = 0; k <= y; ++k) {
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
				if (k + b <= y) {
					dp[i + 1][j + 1][k + b] = min(dp[i + 1][j + 1][k + b], dp[i][j][k] + a);
				}
			}
		}
	}

	int result = 0;
	for (int j = 0; j <= n; ++j) {
		for (int k = 0; k <= y; ++k) {
			if (dp[n][j][k] <= x) {
				result = max(result, j);
			}
		}
	}
	result = min(result + 1, n);

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC364E)

Python版も基本的な考え方は同じです。

以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。

"""AtCoder Beginner Contest 364 E"""
INF = 1000000001
n, x, y = map(int, input().split())

dp = [[[INF] * (y + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(i + 1):
        for k in range(y + 1):
            dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
            if k + b <= y:
                dp[i + 1][j + 1][k + b] = \
                  min(dp[i + 1][j + 1][k + b], dp[i][j][k] + a)

result = 0
for j in range(n + 1):
    for k in range(y + 1):
        if dp[n][j][k] <= x:
            result = max(result, j)
result = min(result + 1, n)

print(result)

最後に

この問題では、DPのキーと値を入れ替えるという技法を学ぶことができました。

引き続き ABC の問題を紹介していきます。

COMMENT

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

CAPTCHA