はじめに
本記事はPythonでAtcoderにチャレンジしているけど、Pythonはコード例がないため解説がわかりにくい！と感じている方を対象としています。
私自身大してレートも高くないので、不備等あるかもしれませんがご了承くださいm(_ _)m
質問や指摘などもコメント等に書いてくださったら対応していきたいと考えていますのでどしどしコメントしてください。(内容がわかりにくいぞ！みたいな文句でもオールオッケーです笑)
ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286) [D問題]
問題のURLはこちらです。ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)
使う手法
今問題では動的計画法を利用していきます。
動的計画法とはざっくりいうと、問題を小さく分割して、ひとつ前の計算結果を利用して最終的な解を見つけるというものです。
何のこっちゃ？って感じだと思うので、こちらを参考にしてみてください。(私の拙い解説よりずっとわかりやすいかと思います笑)
考え方
今問題におけるメモ用の配列として、$(N+1)×(X+1)$の行列「dp」を用意します。
dp[i][j]には、コインAiを用いた際にちょうどj円支払うことができるならjを、払えないなら0を格納しています。(ただし、A_0=0としています。)
入力例1を例にして、メモの遷移を見ていきましょう。
初期状態
今回 N = 2、X = 19であることから、3×20の二次元配列であるdpを作成します。
初期値として全て0を格納しています。
従って、初期状態におけるdpは以下のようになっています。
i = 0
先ほども述べたように、処理の関係上$A_0$を0としています。
従って、dpの1行目は「0円コインでj円を払えるかどうか」を表しています。
0円コインで払える金額は0円しかないうえ、初期状態は全て0が格納されているため、初期状態から特に変わりません。
この処理いる？って思うかもしれませんが、後の処理のために必要なのでとりあえずスルーしてください。
i = 1
いよいよ本筋の処理になります。$A_1 = 2$であることから、dpの2行目は「2円コインでj円を払えるかどうか」を表しています。
この時コインは$B_1 = 3$枚あるので、これらでj円支払えるかを調べていきます。
j円支払えるか調べるためには、$dp[i-1][j-2k] = j-2k (0\leq k\leq B_1)$が成り立てば良いです。
これはどういうことかというと、6円払えるかどうかは、$dp[0][6-2k]$、つまり
$dp[0][6]$、$dp[0][4]$、$dp[0][2]$、$dp[0][0]$を見ていきます。このうち、dp[0][0]のみ格納された値とjが一致するため、、0円コインを0枚、2円コインを3枚(k=3のため)支払うことで、6円ピッタリ支払うことができます。
逆に7円支払うことができるかどうか調べる際には、
$dp[0][7]$、$dp[0][5]$、$dp[0][3]$、$dp[0][1]$を参照します。この中には格納された値とjが一致するものはないため、支払い不可能であり、値の更新は行いません。
このように値の更新を行うことで、dpは下のようになります。
i = 2
$A_2 = 5$ですから、dpの3行目は「5円コインでj円を払えるかどうか」を表しています。
先ほど同様に、$dp[i-1][j-2k] = j-2k (0\leq k\leq B_2)$が成り立つかどうかで支払えるかどうかが分かりますのでやっていきます。
例えば$j = 12$について、参照する値は
$dp[0][12-2k]$、つまり$dp[1][12]$、$dp[1][7]$、$dp[1][2]$
となります。(kを3以上取ると、参照するjの値がマイナスになってしますため省きます。)
dp[1][2]には2が格納されており、j と一致するので12円は支払うことができます。
逆に$j = 18$などは、kについてどのような値をとっても$dp[i-1][j-2k] = j-2k $を満たすことはないので、18円は丁度支払うことができません。
よって、i = 2の処理が終わった時、以下のようなdpになります。
最後に、dpにおいて一番右下の値がxと一致していれば出力は「Yes」、0であれば「No」を出力すれば完璧です。
実装例
#標準入力
n,x = map(int,input().split())
#コインの枚数、コインの種類を格納する辞書とリストを作成
moneys = dict()
coin_list = [0]
#各コインの情報を受け取る
for _ in range(n) :
a,b = map(int,input().split())
moneys[a] = b
coin_list.append(a)
#dpの構築
dp = [[0 for _ in range(x+1)] for _ in range(n+1)]
#dpの更新。0円コインの更新は起こり得ないので、ループは1から始める。
for i in range(1,n+1):
now = coin_list[i]
for j in range(x+1) :
#jがA_iコインで割り切れて、かつ支払える最大料金を超えてなければ値を入力
if (j%now == 0) and(j <= now*moneys[now]):
dp[i][j] = j
#前状態を参照して支払い可能かどうかを調べる。支払い可能なら値を更新
for k in range(moneys[now]+1):
if (j-now*k >= -1)and(dp[i-1][j-now*k] != 0):
dp[i][j] = j
judge = dp[n][x]
if judge == x :
print("Yes")
else :
print("No")
最後に
動的計画法は非常に汎用性が高い反面、その自由度の高さゆえに体系的な理解が難しく、実際に活用できるようになるまでは慣れが必要です。
なので、きちんと動的計画法をマスターしたい初学者の方は公式解説及び本記事の内容を踏まえて自分でもコーディングしてみることをお勧めします。(上から目線で言いましたが、自分もまだまだ完璧に使いこなせていません笑)
また、今回構築したプログラムではdpに格納する値をjか0かで判断しましたが、解説のようにbool値の方が分かりやすかったかもしれません。
需要があれば書き換えたものも記載しますので、もしそっちも見たい場合にはコメントお願いします。