AtCoder が提供しているABC（AtCoder Beginner Contest）271 のD問題をC++とPythonで解いてみました。ABC271は、2022年10月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Flip and Adjust（Difficulty : 886）
問題はリンク先をご覧ください。
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 – 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 の問題を紹介していきます。
