AtCoder の DPまとめコンテストを python で解いてみる(F問題まで)

この記事は書きかけです.

動的計画法(DP)について, AtCoder でコンテストが開かれました.

atcoder.jp
Python で解けたものから, 自分なりに解説をつけていきたいと思います.

A - Frog 1

考えること

足場 $n$ , $n =1,\cdots, N$ にたどり着くまでの最小コストを考えます.
これを $a_n$ と表すことにすると,
\begin{equation}
\begin{cases}
a_1 &= 0,\\
a_2 &= |h_1-h_2|,\\
a_n &= \min\{a_{n-1} + |h_n-h_{n-1}|, a_{n-2}+ |h_n-h_{n-2}| \},&\quad \textrm{if } n=3,4,\cdots, N
\end{cases}
\end{equation}
という風に一般的に表されます.
つまり, $a_n$ を $n=3, 4,\cdots, N$ のときもとめるには以前の計算結果を使いまわすことで結果を得られます.
$a_N$ を求めたいのに $a_n$ , $n=1,2,\cdots, N-1$ をわざわざ求めるのは直観的には遠回りに感じますが,
$a_{n-2}, a_{n-1}$ のそれぞれの値を保存できていれば $a_{n}$ を瞬時に求めることが出来るので, うまくいきます.

N = int(input())
h = list(map(int, input().split()))
 
DP = [0, abs(h[0]-h[1])]
for i in range(N-2):
    DP += [min(DP[-2] + abs(h[i]-h[i+2]), DP[-1] + abs(h[i+1]-h[i+2]))]
 
print(DP[-1])

B - Frog 2

atcoder.jp

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])

C - Vacation

atcoder.jp

N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
 
A = [0]
B = [0]
C = [0]
for i in range(N):
    a = abc[i][0] + max(B[-1], C[-1])
    b = abc[i][1] + max(A[-1], C[-1])
    c = abc[i][2] + max(A[-1], B[-1])
    A += [a]
    B += [b]
    C += [c]
print(max(A[-1], B[-1], C[-1]))

D - Knapsack 1

atcoder.jp

import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.zeros(W+1, dtype=int)
# i 円以下で買える商品の最大価値
for i in range(N):
    DP[w[i]:] = np.maximum(DP[:-w[i]]+ v[i], DP[w[i]:])
print(DP[-1])

E - Knapsack 2

atcoder.jp

import numpy as np
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
    a, b = map(int, input().split())
    w += [a]
    v += [b]
 
DP = np.ones(N*1000+1, dtype=int) *(W+1)
DP[0] = 0
#総価値 i 円を得るために最低限必要な重量
for i in range(N):
    DP[v[i]:] = np.minimum(DP[:-v[i]]+ w[i], DP[v[i]:])
ans = 0
for k in range(N*1000+1):
    if DP[k] <= W:
        ans = k
        
print(ans)

F - LCS

atcoder.jp

S = input()
T = input()
 
#初期化
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
 
#DP
for i in range(len(S)):
    for j in range(len(T)):
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + (S[i] == T[j]))
 
st = []
 
x = len(S)
y = len(T)
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]: x -= 1
    elif dp[x][y] == dp[x][y-1]: y -= 1
    else: 
        x -= 1
        y -= 1
        st += S[x]
print("".join(reversed(st)))