ABC270 D問題（Stones）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）270 のD問題をC++で解いてみました。ABC270は、2022年9月24日21:00に実施されました。

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

D問題 Stones（Difficulty : 1300）

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

ABC270 D問題 Stones

貪欲法では解けません。DPで解きます。AtCoder Problems による Difficulty は、1300 でした。

解答案

公式解説の冒頭で反例が挙げられていますが、貪欲法（各手番で一番多く取る）では解けません。

$DP[i]$ を石が $i$ 個残っている状態から始めたときに先手が取れる最大の個数とします。$A_j$ の $j$ は、0からカウントします。$DP[i]$ の漸化式は以下となります。

$DP[i] = A_j + (i-A_j)-DP[i – A_j]$ の最大値 $(0 \leqq j < k)$

右辺の意味は、先手が $A_j$ 個の石を取ったときに、$i – A_j$ 個残っている状態から後手が取ることができる最大数を引いた石の個数となります。結果的に漸化式は以下となります。

$DP[i] = i-DP[i – A_j]$ の最大値 $(0 \leqq j < k)$

C++ プログラム例（ABC270D）

考察した漸化式を、そのまま実装しました。以下が、C＋＋プログラムとなります。

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

int main()
{
	int n, k;
	cin >> n >> k;

	vector<int> a(k);
	for (int i = 0; i < k; ++i) {
		cin >> a[i];
	}

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

	cout << dp[n] << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC270D）

Python 版も基本的な考え方は同じです。以下となります。

"""AtCoder Beginner Contest 270 D"""
n, k = map(int, input().split())
a = list(map(int, input().split()))

dp = [0] * (n + 1)
for i in range(n + 1):
    for j in range(k):
        if i - a[j] >= 0:
            dp[i] = max(dp[i], i - dp[i - a[j]])

print(dp[n])

こちらも「AC」と判定されました。

最後に

コンテスト中、貪欲法で解こうとしてこの問題を解くことができませんでした。1年以上経ちましたが、DP に慣れるために公式解説を参考にしながら解いてみました。勉強になりました。

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