AtCoder が提供しているABC（AtCoder Beginner Contest）306 のD問題をC++とPythonで解いてみました。ABC306は、2023年6月17日21:00に実施されました。
この回は、コンテスト中にジャッジ遅れが大きく発生したため、unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Poisonous Full-Course（Difficulty : 596）
問題はリンク先をご覧ください。
ABC306 D問題 Poisonous Full-Course
DPを使って解くことができました。AtCoder Problems による Difficulty は 596 でした。
解答案
DP（Dynamic Programming: 動的計画法）を使って解くことができる典型的な問題です。DP は、メモ化再帰で実装する方法と漸化式で実装する方法があります。この記事では、漸化式で実装する方法を紹介します。
dp[i][j] を i 番目の料理を食べた後の美味しさの合計の最大値とします。j = 0 はお腹を壊していないとき、j = 1 はお腹を壊しているときを表します。
漸化式を考えます。
料理を食べない場合は、以下となります。料理を食べないため、お腹の状態も食べた料理の美味しさの合計も変わりません。
- dp[i + 1][0] = dp[i][0]
- dp[i + 1][1] = dp[i][1]
次に料理を食べる場合について考えます。料理が解毒剤入りと毒入りの場合で分かれます。
Xi = 0（解毒剤入り）の場合の漸化式は以下となります。これは、前のお腹の状態に関係なく食べることができるためです。お腹は壊していない状態になるため、dp[i + 1][1] の値は更新されません。
- dp[i + 1][0] = max (dp[i][0] + Yi, dp[i][1] + Yi)
Xi = 1（毒入り）の場合の漸化式は以下となります。dp[i][1] からの遷移がないのは、死んでしまうからです。お腹を壊している状態になるため、dp[i + 1][0] の値は更新されません。
- dp[i + 1][1] = dp[i][0] + Yi
料理を食べない場合、食べる場合のすべての場合の最大値が dp[i + 1][0]、dp[i + 1][1] となります。
求める解答は、dp[N][0] と dp[N][1] の大きな値となります。
初期値は以下となります。
- dp[0][0] = 0 これ以外は $- \infty$
C++ プログラム例（ABC306D）
上で考察した漸化式をプログラムにします。注意としては、dp の値は、32ビット整数の範囲を超えるため、long long としました（13、18行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1ULL << 60)
int main()
{
int n;
cin >> n;
vector<int> x(n);
vector<ll> y(n);
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
vector<vector<ll>> dp(n + 1, vector<ll>(2, -INF));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
dp[i + 1][0] = dp[i][0];
if (x[i] == 0) {
dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + y[i]);
dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + y[i]);
}
dp[i + 1][1] = dp[i][1];
if (x[i] == 1) {
dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + y[i]);
}
}
cout << max(dp[n][0], dp[n][1]) << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC306D）
Python 版も C++ 版のロジックを移植しました。
"""AtCoder Beginner Contest 306 D"""
n = int(input())
x = []
y = []
for i in range(n):
t_x, t_y = map(int, input().split())
x.append(t_x)
y.append(t_y)
INF = (1 << 60)
dp = [[-INF for i in range(2)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
dp[i + 1][0] = dp[i][0]
if x[i] == 0:
dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + y[i])
dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + y[i])
dp[i + 1][1] = dp[i][1]
if x[i] == 1:
dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + y[i])
print(max(dp[n][0], dp[n][1]))こちらも「AC」と判定されました。
最後に
このブログでは、2022年9月17日に開催されたABC269からABCを紹介しています。最初は、DPはまったく解けませんでした。
今回は、A問題からD問題までを29:45でAC判定を取ることができました（その後で、1時間以上E問題と格闘しましたが）。D問題だけであれば13分程度でACを取ることができました。進歩があると、コンテスト参加を続ける動機にもなります。
引き続き ABC の問題を紹介していきます。
