AtCoder が提供しているABC（AtCoder Beginner Contest）286 のD問題をC++とPythonで解いてみました。ABC286は、2023年1月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Money in Hand（Difficulty : 607）
問題はリンク先をご覧ください。
DPを使う典型的な問題です。AtCoder Problems による Difficulty は 607 でした。
解答案
問題から DP を使うことが予想できる問題です。硬貨の枚数 Bi がすべて1の時は、部分和問題と呼ばれる問題になります。まず、この場合を考えてみます。
dp[i][j] は、a0, … , ai-1 の i 個の候補から、いくつか選んで j にすることができる場合 true、できない場合 false となるような Bool 型の配列とします。
dp[i][j] までの値が決まっている場合は、以下の関係が成立します。a の添え字を0からカウントしているため、ai は、i + 1 番目の候補となります。
- dp[i + 1][j] は、dp[i][j] が true の場合、true となる。
（ai を選ばない場合） - dp[i + 1][j] は、dp[i][j – ai] が true の場合、true となる。
（ai を選ぶ場合）
また、漸化式の初期値は、以下となります。
- dp[0][0] は true、それ以外の dp[i][j] は false となる。
これにより部分和問題を解くことができます。実際に解く問題では、硬貨が Bi 枚あります。このため、漸化式は以下となります。
- dp[i + 1][j] は、dp[i][j] が true の場合、true となる。
（ai を選ばない場合） - dp[i + 1][j] は、dp[i][j – ai] が true の場合、true となる。
（ai を 1 枚選ぶ場合） - dp[i + 1][j] は、dp[i][j – 2 × ai] が true の場合、true となる。
（ai を 2 枚選ぶ場合） - ．．．
- dp[i + 1][j] は、dp[i][j – Bi × ai] が true の場合、true となる。
（ai を Bi 枚選ぶ場合）
上で示した漸化式に従い計算して、dp[N][X] が true なら ”Yes”、false なら ”No” を出力します。
C++ プログラム例（ABC286D）
Vector コンテナ dp の値を方針に従い計算します。一番内側のループ変数 k を 0 から、Bi まで回します。k が 0 の場合は、ai を選ばないことに該当します。
添え字が範囲外にならないように確認してから、漸化式に従い、dp[i+1][j] の値を更新しています（20-22行目）。以下が、C++ のプログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, x;
cin >> n >> x;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
}
vector<vector<bool>> dp(n + 1, vector<bool>(x + 1, false));
dp[0][0] = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= x; ++j) {
for (int k = 0; k <= b[i]; ++k) {
if ((j - a[i] * k >= 0)&&(dp[i][j - a[i] * k])) {
dp[i + 1][j] = true;
}
}
}
}
if (dp[n][x]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC286D）
上記の C++ プログラムをそのまま移植しました。
"""AtCoder Beginner Contest 286 D"""
n, x = map(int, input().split())
a = []
b = []
for i in range(n):
temp_a, temp_b = map(int, input().split())
a.append(temp_a)
b.append(temp_b)
dp = [[False for i2 in range(x + 1)] for i1 in range(n + 1)]
dp[0][0] = True
for i in range(n):
for j in range(x + 1):
for k in range(b[i] + 1):
if j - a[i] * k >= 0 and dp[i][j - a[i] * k]:
dp[i + 1][j] = True
print("Yes" if dp[n][x] else "No")このプログラムは、Python（3.8.2）では、TLE（Time Limit Exceeded）判定でした。一方、PyPy3（7.3.0）では、AC 判定となりました。
最後に
ABC286 C問題の Difficulty が 565でした。一方、今回のD問題の Difficulty は 607 でした。
C問題は、簡単ではないですが、問題の構造が分かれば全検索のプログラムを書くことは可能だと思います。D問題は、DP（動的計画法）の知識がないと手がでません。一般のプログラマにとって、この意味でD問題は難しいと感じる人が多いと思います。実際の Difficulty の差は少ないと感じました。これは、AtCoder の参加者のレベルが高いからだと考えています。
引き続き ABC の問題を紹介していきます。
