AtCoder

ABC306 D問題(Poisonous Full-Course)を解く

AtCoder_ABC306_D

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を取ることができました。進歩があると、コンテスト参加を続ける動機にもなります。

ABC306 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA