Pythonで解く【初中級者が解くべき過去問精選 100 問】(039 - 045 動的計画法：ナップザック DP亜種)

# 1. 目的
[初中級者が解くべき過去問精選 100 問](https://qiita.com/e869120/items/eb50fdaece12be418faa)をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「039 - 045 動的計画法：ナップザック DP亜種」です。

# 2. 総括
目標となる```dp```テーブルを実際に書けると問題は解けますが、テーブルをイメージできないとなかなか解くことが難しいです。

# 3. 本編
## 039 - 045 動的計画法：ナップザック DP亜種

### 039. [JOI 2011 予選 4 - 1 年生](https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/337b360c-a77e-6bb2-46eb-a2f31dc93a44.png)

#### 回答
```python

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）となります。

```python

    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 - パスタ](https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/d48451cf-9b88-71b3-397f-1d77a47144f1.png)


#### 回答
```python

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```テーブルは、行の添え字をパスタの種類、列の添え字を日数、テーブルの中身を場合の数として、下記のようなテーブルを作成することが目標です（入力例２の場合）

```python

   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```までのせます。


```python


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 - 暑い日々](https://atcoder.jp/contests/joi2013yo/tasks/joi2013yo_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/2b43655a-f8ac-08d6-7734-7f0af7cb464b.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/cd4c6821-bc5d-f72c-3708-1b705556b224.png)


#### 回答
```python

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の場合）

```python

   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 - シルクロード](https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/08a242d6-70e1-8754-c5f8-4d05cd687b5c.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/5d53868d-2f2a-e368-de86-0ac03760f101.png)


#### 回答
```python

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の場合）

```python

     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 - パ研軍旗](https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/25d6d423-1f4a-7a01-7462-1d393e4b71ef.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/28aac516-ae07-e2ab-5853-b9101a4a2505.png)


#### 回答
```python

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の場合）

```python

     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 - ポロック予想](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/775bf899-11ef-79b5-aa79-2e1cb3ae1219.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/52ab7396-fa99-5be7-9ef0-985c337b6066.png)


#### 回答(TLE)
```python


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 - 差分パルス符号変調](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199&lang=jp)



![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/b2628ea0-2804-d356-38d6-b53133c25716.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/93af6643-0925-ec8d-c244-898b3adcf47d.png)

#### 回答(TLE)

```python

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```となります。ローカルではすべて答えは一致しているのでこれであっているとは思います。
高速化はちょっと難しかったので気が向いたら行います。






---