AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の56問目である「 Lucky Bag（★5）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【056 – Lucky Bag（★5）】
考察
デパートの福袋購入計画 – 動的計画法を用いた解法
問題文
デパートの高橋屋では、N日にわたって初売りが行われます。i日目には、A_i円の福袋AとB_i円の福袋Bが売られます。低橋くんはN日間、毎日高橋屋に通って福袋Aまたは福袋Bのいずれかを購入します。N日間で購入したN個の福袋の総額がちょうどS円になるように購入したいです。そのような購入の計画が存在しない場合は、それを報告してください。
考察
・考えた内容の概要
この問題は動的計画法(DP)を用いて解くことができます。具体的には、N日間でS円分の買い物ができるかをまず検証し、次にどのような順番で買えば良いかを探索します。
・考えたことの内容
- そもそもN日間でS円分の買い物できるかを検証
- 1日目には、A1円の福袋とB1円の福袋が与えられるため、
dp[i][A1] = Trueおよびdp[i][B1] = Trueとなります。 - 2日目には、A2円の福袋とB2円の福袋が与えられるため、
dp[i][A1+A2] = True,dp[i][A1+B2] = True,dp[i][B1+A2] = True,dp[i][B1+B2] = Trueとなります。 - このようにして、i日目の状態はi-1日目の状態のみ参照することで買えるかどうか分かるので、N日間の購入計画を検証します。
- 1日目には、A1円の福袋とB1円の福袋が与えられるため、
- できるのなら、どのような順番で買えば良いかを探索
- DP復元を用いて、S日目から0日目まで遡りながら購入計画を立てます。
・実装した内容
Pythonのコードを用いて、上記の考察を実装しました。具体的には、dp 配列を用いてN日間の購入計画を検証し、その後DP復元を行って購入の順番を決定します。
手順
- そもそもN日間でS円分の買い物できるかを検証
dp配列を用いて、各日における購入計画を検証します。- 1日目からN日目までの購入計画を順番に検証し、最終的に
dp[N][S]がTrueであれば、N日間でS円分の買い物ができることが確定します。
- できるのなら、どのような順番で買えば良いかを探索
- DP復元を用いて、S日目から0日目まで遡りながら購入計画を立てます。この際、
dp配列を参照しながら、どの福袋を購入するかを決定します。
- DP復元を用いて、S日目から0日目まで遡りながら購入計画を立てます。この際、
このようにして、N日間でS円分の買い物ができる購入計画を立てることができます。
コード
N,S = map(int, input().split())
dp = [[False]*(S+1) for i in range(N)]
A_box = []
B_box = []
for i in range(N):
A,B = map(int, input().split())
A_box.append(A)
B_box.append(B)
# DPの実装
for i in range(N):
A,B = A_box[i],B_box[i]
if i == 0:
dp[i][A] = True
dp[i][B] = True
else:
for j in range(A,S+1):
if dp[i-1][j-A] == True:
dp[i][j] = True
for j in range(B,S+1):
if dp[i-1][j-B] == True:
dp[i][j] = True
# DP復元の実装
if dp[-1][-1] == False:
print("Impossible")
exit()
ans = []
now = S
for i in range(N-1,-1,-1):
if now - A_box[i] >= 0 and dp[i-1][now - A_box[i]]:
ans.append("A")
now -= A_box[i]
else:
ans.append("B")
now -= B_box[i]
print(*ans[::-1],sep="")まとめ
前の問題【052 – Dice Product（★3）】
次の問題【058 – Original Calculator（★4）】
コメント