動的計画法の備忘録として、問題とその回答コードについてまとめておきます。
注意
動的計画法が何かについての詳しい解説はしません。
詳細は以下のリンクなど他のサイトをご参照ください。
AtCoder Beginner Contest 289 D
無限に続く階段があります。 一番下は 0 段目で、1 段のぼるごとに 1 段目、2 段目と続きます。
0 段目に階段登りロボットがいます。 階段登りロボットは、一回の動作で $A_1,A_2,…,A_N$段ぶん階段をのぼることができます。 つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は $i+A_1$ 段目、$i+A_2$ 段目、⋯、$i+A_N$ 段目のいずれかにいることができます。 それ以外の段数を一回の動作でのぼることはできません。 階段登りロボットは階段を下ることもできません。
階段の $B_1,B_2,…,B_N$ 段目にはモチが設置されています。 モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。
階段登りロボットは階段のちょうど X 段目にのぼりたいです。 階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。
AtCoder Beginner Contest 289 D-Step Up Robot
iがBに含まれているかどうかiより前の段i-A[0], i-A[1], ... , i-A[N]が到達可能かどうか
の2項目を確認すれば、i 段目に到達できるかどうかを計算できます。
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))
X = int(input())
#動的計画法で解く
#1は到達可能な段とする
dp = [0]*(X+1)
dp[0] = 1
for x in range(X+1):
#Bに含まれる場合は無視
if x in B:
continue
#step
for a in A:
#0以上でかつBに含まれていない場合
if x-a >= 0 and not x-a in B:
dp[x] = max(dp[x], dp[x-a])
#print(dp)
if dp[-1]==1:
print('Yes')
else:
print('No')注意点は、B をリストではなく集合set型にしている点です。
これは x in B の判定を$\mathcal{O}(1)$に高速化するための工夫で、リスト型にすると$\mathcal{O}(N)$ のため TLE となり不正解になります。
リストや集合の計算量については以下のサイトをご参照ください。
AtCoder Beginner Contest 286 D
高橋君は $N$ 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1≤i≤N について $A_i$ 円硬貨を $B_i$ 枚持っています。
高橋君が現在持っている硬貨を用いて、（お釣りが出ないように）ちょうど $X$ 円を支払うことができるか判定してください。
AtCoder Beginner Contest 286 D-Money in Hand
この問題も動的計画法で解いていきます。
dp[i] = i 円 を作れる場合は True, 作れない場合は False
X 円を作れるかどうかについて、具体的な硬貨の枚数を知る必要はありません。したがって、$a$ 円を1枚持っている場合、$x$円を作れるかどうかは $x-a$円が作れるかどうかだけ分かればokです。
- dp[x] = dp[x] | dp[x-a]
この手続きを$1,2,…,B_i$ 個の場合で計算します。
- dp[x] = dp[x] | dp[x-a*2] (aが２枚の場合)
- dp[x] = dp[x] | dp[x-a*3] (aが3枚の場合)
- …
- dp[x] = dp[x] | dp[x-a*n] (aがn枚の場合)
上記全体の手続きをすべての種類の硬貨で計算します。
N, X = map(int,input().split())
AB = []
dp = [False]*(X+1)
dp[0] = True
for _ in range(N):
a,b = map(int, input().split())
nx = [False]*(X+1)
for i in range(X+1):
#今まで見た硬貨で作れる金額の場合
if dp[i]:
for j in range(b+1):
if i+a*j <= X:
nx[i+a*j] = True
dp = nx
if dp[-1]:
print('Yes')
else:
print('No')まとめ
動的計画法の問題について、今後も解いた問題をまとめていきたいと思います。
