AtCoder

ABC271 D問題(Flip and Adjust)を解く

AtCoder_ABC271_D

AtCoder が提供しているABC(AtCoder Beginner Contest)271 のD問題をC++とPythonで解いてみました。ABC271は、2022年10月1日21:00に実施されました。

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

D問題 Flip and Adjust(Difficulty : 886)

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

ABC271 D問題 Flip and Adjust

DPを使う典型問題です。結果を復元する必要があります。AtCoder Problems による Difficulty は、886 でした。

解答案

カードに表と裏があり、数字が2種類ありますが部分和問題です。

dp[i][j] は、カードの最初の i 枚の候補から、いくつか選んで j にすることができる場合 true、できない場合 false となる Bool 型の配列とします。

dp[i][j] までの値が決まっている場合は、以下の関係が成立します。添え字は0からカウントしています。

  • dp[i + 1][j] は、dp[i][j] が true の場合、true となる。
    (カードを選ばない場合)
  • dp[i + 1][j] は、dp[i][j – ai] が true の場合、true となる。
    (カードの表を選ぶ場合)
  • dp[i + 1][j] は、dp[i][j – bi] が true の場合、true となる。
    (カードの裏を選ぶ場合)

また、漸化式の初期値は、以下となります。

  • dp[0][0] は true、それ以外の dp[0][j] は false とする。

この問題では、総和がSとなる解を復元する必要があります。

  • 解がある場合、dp[n][s] は、true になっています。
    • dp[n – 1][s – an-1] か dp[n – 1][s – bn_1] のどちらが true になっているはずです。
    • これを繰り返すことによって、解を復元できます。

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

配列 dp を上で考察した漸化式となるように実装します(14ー25行目)。dp[n][s] から、解を復元します(30ー40行目)。

以下が、C++プログラムとなります。

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

int main()
{
	int n, s;
	cin >> n >> s;
	vector<int> a(n);
	vector<int> b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
	}

	vector dp(n + 1, vector<bool>(s + 1, false));
	dp[0][0] = true;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= s; ++j) {
			if ((j - a[i] >= 0)&&(dp[i][j - a[i]])) {
				dp[i + 1][j] = true;
			}
			if ((j - b[i] >= 0)&&(dp[i][j - b[i]])) {
				dp[i + 1][j] = true;
			}
		}
	}

	if (dp[n][s]) {
		cout << "Yes" << endl;

		string t = "";
		for (int i = n - 1; i >= 0; --i) {
			if ((s - a[i] >= 0)&&(dp[i][s - a[i]])) {
				t = 'H' + t;
				s -= a[i];
			} else {
				t = 'T' + t;
				s -= b[i];
			}
		}
		cout << t << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

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

Python プログラム例(ABC271D)

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

"""AtCoder Beginner Contest 271 D"""
n, s = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

dp = [[False for i2 in range(s + 1)] for i1 in range(n + 1)]
dp[0][0] = True
for i in range(n):
    for j in range(s + 1):
        if j - a[i] >= 0 and dp[i][j - a[i]]:
            dp[i + 1][j] = True
        if j - b[i] >= 0 and dp[i][j - b[i]]:
            dp[i + 1][j] = True

if dp[n][s]:
    print("Yes")

    t = ""
    for i in range(n-1, -1, -1):
        if s - a[i] >= 0 and dp[i][s - a[i]]:
            t = "H" + t
            s -= a[i]
        else:
            t = "T" + t
            s -= b[i]
    print(t)
else:
    print("No")

Python 版も「AC」と判定されました。

最後に

ABC271に参加した1年前には、DPはまったく解けませんでした。この問題も当時、「すぐにあきらめた」とメモされていました。

いまでもDPは、得意とは言えません。しかし、この問題は解くことができました。進歩を感じることができました。

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

COMMENT

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

CAPTCHA