AtCoder が提供しているABC（AtCoder Beginner Contest）289 のD問題をC++とPythonで解いてみました。ABC289は、2023年2月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Step Up Robot（Difficulty : 551）
問題はリンク先をご覧ください。
DPを使う典型的な問題です。AtCoder Problems による Difficulty は 551 でした。
解答案
DP（動的計画法：Dynamic Programming）を使って解いてみます。
dp[i] は、A0, … , AN-1 の N 個の候補を何回使っても良いので、その合計を i にすることができる場合 true、できない場合 false となるような Bool 型の配列とします。※配列 A は問題文と異なり、添え字を 0 からカウントしています。
dp[i – 1] までの値が決まっている場合は、以下の関係が成立します。
- dp[i] は、dp[i – A0] が true の場合、true となる。（A0 を選ぶ場合）
- dp[i] は、dp[i – A1] が true の場合、true となる。（A1 を選ぶ場合）
- dp[i] は、dp[i – A2] が true の場合、true となる。（A2 を選ぶ場合）
- ．．．
- dp[i] は、dp[i – AN-1] が true の場合、true となる。（AN-1 を選ぶ場合）
ただし、i が配列 B の要素のどれかに等しい場合は、モチが設置されていて、それ以上先に進めませんので false になります。
また、漸化式の初期値は、以下となります。
dp[0] は true、それ以外の dp[i] は false となる。
上で示した漸化式に従い計算して、dp[X] が true なら ”Yes”、false なら ”No” を出力します。
C++ プログラム例（ABC289D）
考察した漸化式をプログラムにします。配列 B のどれかに等しいことを毎回ループで確認していると時間が足りません。配列 B は、ソートされていることを使ってもよいですし、set コンテナに登録して確認してもよいです。ここでは、ソートされていることを使いました。配列 B をどこまで確認したか b_index に保持しています。
また、上述の漸化式では、配列外参照を考慮していませんでしたが、プログラムでは添え字の範囲を確認してアクセスしています。
以下が、最終的な C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int m;
cin >> m;
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
int x;
cin >> x;
vector<bool> dp(x + 1, false);
dp[0] = true;
int b_index = 0;
for (int i = 1; i <= x; ++i) {
if ((b_index < m)&&(b[b_index] == i)) {
++b_index;
continue;
}
for (int j = 0; j < n; ++j) {
if (i - a[j] >= 0) {
dp[i] = dp[i] || dp[i - a[j]];
}
}
}
if (dp[x]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC289D）
C++ のロジック通りに Python プログラムにしました。このプログラムは、Python らしくないかもしれません。
"""AtCoder Beginner Contest 289 D"""
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
x = int(input())
dp = [False] * (x + 1)
dp[0] = True
b_index = 0
for i in range(1, x + 1):
if b_index < m and b[b_index] == i:
b_index += 1
continue
for j in range(n):
if i - a[j] >= 0:
dp[i] = dp[i] or dp[i - a[j]]
print("Yes" if dp[x] else "No")どちらも「AC」と判定されました。
最後に
このブログでは、ABC269 から AtCoder の問題を紹介しています。当初、DP がほとんど理解できていませんでした。何回か解けない問題と格闘しているうちに典型的な場合は解けるようになりました。少しでも進歩していくのは楽しいものです。
引き続き ABC の問題を紹介していきます。
