1. 目的
初中級者が解くべき過去問精選 100 問をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。
本記事は「039 - 045 動的計画法：ナップザック DP亜種」です。
2. 総括
目標となるdpテーブルを実際に書けると問題は解けますが、テーブルをイメージできないとなかなか解くことが難しいです。
3. 本編
039 - 045 動的計画法：ナップザック DP亜種
039. JOI 2011 予選 4 - 1 年生
回答
N = int(input())
num = list(map(int, input().split()))
dp = [[0] * (N-1) for _ in range(21)]
for i in range(21):
if i == num[0]:
dp[i][0] = 1
for j in range(1, N-1):
for i in range(21):
if dp[i][j-1] <= 0:
continue
if i - num[j] >= 0:
dp[i - num[j]][j] += dp[i][j-1]
if i + num[j] <= 20:
dp[i + num[j]][j] += dp[i][j-1]
answer = dp[num[-1]][N-2]
print(answer)
dpテーブルは、行の添え字を計算結果の合計値、列の添え字を与えられる整数の添え字と一致させます。
dpテーブルには「j列までに計算結果がちょうどiとなるような件数」を記録します。
入力例１で作成するdpテーブルは下記のようになります。
答えはdp[8][9]（=10）となります。
0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 1 2 4 8
1 0 0 0 0 1 0 0 0 0 0
2 0 0 0 0 0 1 1 3 6 12
3 0 0 1 1 1 0 0 0 0 0
4 0 0 0 0 0 1 2 4 8 8
5 0 1 0 1 1 0 0 0 0 0
6 0 0 0 0 0 1 3 5 10 12
7 0 0 1 1 0 0 0 0 0 0
8 1 0 0 0 0 2 3 4 8 10
9 0 0 1 1 1 0 0 0 0 0
10 0 0 0 0 0 2 4 6 12 12
11 0 1 0 1 1 0 0 0 0 0
12 0 0 0 0 0 2 2 4 8 10
13 0 0 1 1 1 0 0 0 0 0
14 0 0 0 0 0 0 3 6 12 10
15 0 0 0 0 1 0 0 0 0 0
16 0 0 0 0 0 1 1 3 6 8
17 0 0 0 1 1 0 0 0 0 0
18 0 0 0 0 0 1 2 3 6 12
19 0 0 0 0 1 0 0 0 0 0
20 0 0 0 0 0 1 1 1 2 8
最初は先にこの表を書いてみて、この表を実現するようなコードを書く、という流れで行うのがよいと思います。
おそらく慣れてくると、この表を書かないでも直接コードを書けるようになるのでは、と想像していますが、僕はまだ表を書かないと解けないです。
040. JOI 2012 予選 4 - パスタ
回答
N, K = map(int, input().split()) # N日間のうちK日分はすでに決まっている
pastas = [0] * (N+1)
for _ in range(K):
A, B = map(int, input().split())
pastas[A] = B
dp = [[0] * (N+1) for _ in range(4)]
MOD = 10**4
dp[1][0] = 1
for j in range(1, N+1):
if pastas[j] == 0:
for i in range(1, 4):
for k in range(1, 4):
dp[i][j] += dp[k][j-1]
for i in range(1, 4):
if j -2 > 0 and dp[i][j-1] > 0 and dp[i][j-2] > 0:
dp[i][j-1] -= dp[i][j-2] # 3日以上連続しないように2日前のやつを差し引く
dp[i][j] -= dp[i][j-2] # 3日以上連続しないように2日前のやつを差し引く
else:
for k in range(1, 4):
dp[pastas[j]][j] += dp[k][j-1]
if j - 2 > 0 and dp[pastas[j]][j-1] > 0 and dp[pastas[j]][j-2] > 0:
dp[pastas[j]][j-1] -= dp[pastas[j]][j-2] # 3日以上連続しないように2日前のやつを差し引く
dp[pastas[j]][j] -= dp[pastas[j]][j-2] # 3日以上連続しないように2日前のやつを差し引く
answer = 0
for i in range(1, 4):
answer += dp[i][-1]
print(answer % MOD)
無理やり解いた感がありますが、上記でACです。
多くの回答例ではdpテーブルを3次元で作成していますが、3次元だとなかなかイメージがつかず2次元で解きました。
作成するdpテーブルは、行の添え字をパスタの種類、列の添え字を日数、テーブルの中身を場合の数として、下記のようなテーブルを作成することが目標です（入力例２の場合）
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 8 0 22 38 104 306 1120 0 1120 3360 0 3360 6720 16800 50400 134400 366240 1370880
2 0 1 2 8 0 22 38 104 410 0 1120 1120 0 3360 0 6720 20160 47040 134400 369600 1370880
3 0 1 2 6 16 0 44 120 404 0 0 1120 0 0 3360 6720 16800 50400 134400 366240 1370880
この表の作成過程は下記の流れになります。長いのでj=5までのせます。
j=1----------
普通に足した場合↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
連続するものを消去後↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
j=2----------
普通に足した場合↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
連続するものを消去後↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
j=3----------
普通に足した場合↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 3 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 3 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
連続するものを消去後↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
j=4----------
普通に足した場合↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 2 8 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
連続するものを消去後↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 2 6 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
j=5----------
普通に足した場合↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 8 0 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 2 8 0 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 2 6 22 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
連続するものを消去後↓
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 2 8 0 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 2 8 0 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 2 6 16 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
dp テーブルを作成できれば、最後の列の合計が答えとなります。
041. JOI 2013 予選 4 - 暑い日々
回答
D, N = map(int, input().split()) # D日、N種類の服
T = [0] + [int(input()) for _ in range(D)] # 各日の気温
clothes = [tuple(map(int, input().split())) for _ in range(N)] #(下限気温、上限気温、派手さ)
dp = [[0] * (D+1) for _ in range(N)]
for j in range(2, D+1):
for i in range(N):
if T[j] < clothes[i][0] or clothes[i][1] < T[j]:
continue
score = 0
for k in range(N):
if T[j-1] < clothes[k][0] or clothes[k][1] < T[j-1]:
continue
score = max(score,
abs(clothes[i][2] - clothes[k][2]) + dp[k][j-1])
dp[i][j] = score
answer = 0
for i in range(N):
answer = max(answer, dp[i][-1])
print(answer)
今回のdpテーブルは、行の添え字を服、列の添え字を日付、中身を派手さの絶対値として、下記の用なテーブルを作成することが目標です。（入力例1の場合）
0 1 2 3
0 0 0 0 0
1 0 0 50 0
2 0 0 20 80
3 0 0 0 0
このテーブルを作成できれば、最終列の最大値が答えとなります。
042. JOI 2015 予選 4 - シルクロード
回答
INF = float('inf')
N, M = map(int, input().split()) # N+1個の都市、M日以内に運ぶ必要
D = [0] + [int(input()) for _ in range(N)] # 都市の距離
C = [0] + [int(input()) for _ in range(M)] # 天候の悪さ。疲労はC*Dだが移動しない場合は0
MAX_break = M - N
# dp[i][j] := j日目までにiに到達するための最小疲労
dp = [[INF] * (M+1) for _ in range(N+1)]
for j in range(M+1):
dp[0][j] = 0
for i in range(1, N+1):
for j in range(1, M+1):
dp[i][j] = min(dp[i][j-1],
dp[i-1][j-1] + D[i] * C[j])
print(dp[-1][-1])
今回のdpテーブルは、行の添え字を移動、列の添え字を日付、中身を最小の距離として、下記の用なテーブルを作成することが目標です。（入力例1の場合）
0 1 2 3 4 5
0 0.0 0.0 0.0 0.0 0.0 0.0
1 inf 500.0 300.0 150.0 150.0 150.0
2 inf inf 1250.0 675.0 675.0 675.0
3 inf inf inf 1475.0 1275.0 1125.0
このテーブルが作成できるとdp[-1][-1]が答えとなります。
043. パ研杯2019 D - パ研軍旗
回答
import numpy as np
INF = float('inf')
N = int(input())
S = [[''] + list(input()) for _ in range(5)]
S_count = np.zeros((4, N+1))
for j in range(1, N+1):
for i in range(5):
if S[i][j] == 'R':
S_count[0, j] += 1
if S[i][j] == 'B':
S_count[1, j] += 1
if S[i][j] == 'W':
S_count[2, j] += 1
if S[i][j] == '#':
S_count[3, j] += 1
S_to_use = np.zeros((3, N+1))
for j in range(1, N+1):
for i in range(3):
S_to_use[i, j] = S_count[:, j].sum() - S_count[i, j]
dp = np.full((3, N+1), INF)
dp[:, 0] = 0
# dp[i, j] := j列目をiに塗るときの最小値
for j in range(1, N+1):
for i in range(3):
for k in range(3):
if i == k:
continue
dp[i, j] = min(dp[i, j],
dp[k, j-1] + S_to_use[i, j])
answer = dp[:, -1].min()
print(int(answer))
今回のdpテーブルは、行の添え字を旗の色（R:0, B:1, W:2とする）、列の添え字は列番号、中身を最小の塗るマス数として、下記の用なテーブルを作成することが目標です。（入力例4の場合）
0 1 2 3 4 5 6 7
0 0.0 4.0 6.0 12.0 13.0 15.0 18.0 23.0
1 0.0 3.0 8.0 11.0 11.0 17.0 19.0 21.0
2 0.0 4.0 7.0 8.0 15.0 15.0 20.0 21.0
このテーブルの右端の列の最小値が答えになります。
今回の問題では、dpテーブル作成する前の下処理を工夫する必要がありました。
具体的には、回答コードにあるS_to_useで、これは例えばS_to_use[0, 2]の意味として、旗の2列目をRに塗るために必要なマス数を表します。
これを作成できれば、dpテーブル作成するのはそこまで難しくないと思いました。
044. AOJ 1167 - ポロック予想
回答(TLE)
def cal(i):
return i * (i + 1) * (i + 2) // 6
def main(n):
proku = [0]
proku_odd = [0]
for i in range(1, 201):
num = cal(i)
proku.append(num)
if num % 2 != 0:
proku_odd.append(num)
dp = [0] * (n+1)
dp_odd = [0] * (n+1)
for j in range(n+1):
dp[j] = j
dp_odd[j] = j
for i in range(1, len(proku)):
for j in range(1, n+1):
if j-proku[i] < 0:
continue
if dp[j] > dp[j-proku[i]] + 1:
dp[j] = dp[j-proku[i]] + 1
for i in range(1, len(proku_odd)):
for j in range(1, n+1):
if j-proku_odd[i] < 0:
continue
if dp_odd[j] > dp_odd[j-proku_odd[i]] + 1:
dp_odd[j] = dp_odd[j-proku_odd[i]] + 1
print(dp[-1], dp_odd[-1])
if __name__ == "__main__":
while True:
n = int(input())
if n == 0:
break
main(n)
TLE を直しきれていないです、が、たぶんこれであってると思います。
問題文を理解するのがやや難しいですが、やることはそこまで難しくなく、普通のdpです。
重複許すナップサック問題（問題36）と同じ考え方で解くことができます。
045. AOJ 2199 - 差分パルス符号変調
回答(TLE)
def main(N, M, C, X):
dp = [[INF] * 256 for _ in range(N+1)]
dp[0][128] = 0
for i in range(1, N+1):
for j in range(256):
for k in range(M):
next_j = j + C[k]
next_j = max(0, min(255, next_j))
dp[i][next_j] = min(dp[i][next_j],
dp[i-1][j] + pow(next_j - X[i-1], 2))
answer = min(dp[N][:])
return answer
if __name__ == "__main__":
INF = float('inf')
answer_list = []
while True:
N, M = map(int, input().split()) # Nが入力の数、Mがコードブックの数字の数
if N == M == 0:
break
C = [int(input()) for _ in range(M)] # コードブック
X = [int(input()) for _ in range(N)] # 入力値
answer_list.append(main(N, M, C, X))
for answer in answer_list:
print(answer)
問題を読み解くのが難しいです。
またもや上記コードだとTLEとなります。ローカルではすべて答えは一致しているのでこれであっているとは思います。
高速化はちょっと難しかったので気が向いたら行います。