Mako's blog

Blog Article

動的計画法の練習

動的計画法（DP）の練習をした
問題は「Educational DP Contest / DP まとめコンテスト」のA～F問題
(https://atcoder.jp/contests/dp)

A~E問題

おそらくE問題までが初級編
二次元配列で行うのは少し難しかった。
「アルゴリズム実技検定公式テキスト」を読んで、自分でも図に起こした。
何とか理解した風にはなったが、いざ問題を解こうとすると手が止まる。
一度マクロを組んで理解を深めたい。

参考までにC問題で書いたコードは次の通り。むずい

N = int(input())


A = [0] * N
B = [0] * N
C = [0] * N
for i in range(N):
    A[i], B[i], C[i] = list(map(int, input().split()))


happy = []
for i in range(N):
    happy.append([0, 0, 0])


happy[0][0] = A[0]
happy[0][1] = B[0]
happy[0][2] = C[0]


for i in range(1, N):
    happy[i][0] = max(happy[i - 1][1], happy[i - 1][2]) + A[i]
    happy[i][1] = max(happy[i - 1][0], happy[i - 1][2]) + B[i]
    happy[i][2] = max(happy[i - 1][0], happy[i - 1][1]) + C[i]


print(max(happy[i]))


F問題

一瞬全探索が頭をよぎったがO(2n)なのはすぐにわかったのであきらめた。
s[i] == t[j]
かどうかで分岐処理させて配列の左上から順に数字を埋めていく方針で解いた。

文字列を生成する処理が浮かばず解説を見た。賢いなあと感心。
考え方はおよそあっていたので及第点ということにしておく。

s = input()
t = input()


len_s = len(s)
len_t = len(t)


dp = []
for i in range(len_s):
    dp.append([0] * len_t)


for i in range(len_s):
    if s[i] == t[0]:
        dp[i][0] = 1
    elif i == 0:
        dp[i][0] = 0
    else:
        dp[i][0] = max(dp[i - 1][0], 0)


for j in range(len_t):
    if s[0] == t[j]:
        dp[0][j] = 1
    elif j == 0:
        dp[0][j] = 0
    else:
        dp[0][j] = max(dp[0][j - 1], 0)


for i in range(1, len_s):
    for j in range(1, len_t):
        if s[i] == t[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])


length = dp[len_s - 1][len_t - 1]
i = len_s - 1
j = len_t - 1
ans = [""] * length


while length > 0:
    if s[i] == t[j]:
        ans[length - 1] = s[i]
        length -= 1
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        if i > 0:
            i -= 1
        else:
            j -= 1
    else:
        j -= 1


print("".join(ans))


まとめ

DPコンテストを気長にやっていこうかなと思った。
DFSの問題もちょこちょこやっていきたい。

以上

categories