AtCoder が提供しているABC（AtCoder Beginner Contest）369 D問題をC++とPythonで解いてみました。ABC369は、2024年8月31日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Bonus EXP（Difficulty : 621）
問題の詳細は、リンク先をご覧ください。
DP（動的計画法）を使います。AtCoder Problems による Difficulty は 621 でした。
解答案
$DP_{i,j}$ を $i$ 匹のモンスターを処理した後に得られる経験値の最大値とします。$j=0$ の場合、偶数回倒したことを、$j=1$ の場合、奇数回倒したことを表します。
$i$ 匹目のモンスターを見逃す場合は、簡単です。
- $DP_{i,0} = DP_{i-1,0}$
- $DP_{i,1} = DP_{i-1,1}$
$i$ 匹目のモンスターを倒す場合は、倒した回数が偶数か奇数かによって以下の式が適用できます。
- $DP_{i,0} = DP_{i-1,1} + 2 \times a_i$
- $DP_{i,1} = DP_{i-1,0} + a_i$
求める解答は、$DP_{n,0}$ と $DP_{n,1}$ の大きい方となります。
C++ プログラム例（ABC369D）
上記の漸化式をプログラムとして実装します。以下が、C++プログラムです。初期値と漸化式の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
int main()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<ll>> dp(n + 1, vector<ll>(2, -INF));
dp[1][0] = 0LL;
dp[1][1] = a[0];
for (int i = 1; i < n; ++i) {
dp[i + 1][0] = dp[i][0];
dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + 2 * a[i]);
dp[i + 1][1] = dp[i][1];
dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + a[i]);
}
cout << max(dp[n][0], dp[n][1]) << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC369D）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 369 D"""
INF = 1 << 60
n = int(input())
a = list(map(int, input().split()))
dp = [[-INF for _ in range(2)] for _ in range(n + 1)]
dp[1][0] = 0
dp[1][1] = a[0]
for i in range(1, n):
dp[i + 1][0] = dp[i][0]
dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + 2 * a[i])
dp[i + 1][1] = dp[i][1]
dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + a[i])
print(max(dp[n][0], dp[n][1]))こちらも「AC」と判定されました。
最後に
この問題は、DPを使う典型問題だと認識できました。ブログを始めた2年前は、DPを使う問題はまったく解けませんでした。進歩を感じてうれしく感じます。
引き続き ABC の問題を紹介していきます。
