[AtCoder][DP][Educational DP Contest]F-LCS

AtCoder

Photo by Joshua Miranda on Pexels.com

2022.05.25

Educational DP Contest
問題
方針
解答
提出結果
補足
関連問題
関連リンク

Educational DP Contest

Educational DP Contest - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

問題

F - LCS

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

方針

Longest Common Subsequence (LCS)の問題。

最長共通部分列問題 - Wikipedia

蟻本に従う。長さを求める問題は多いが、再現させるのは意外に少ない。

解答

#input
s = input()
t = input()

#output
m = len(s)
n = len(t)
dp = [[0]*(m+1) for _ in range(n+1)]

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

ans = ""
while m > 0 and n > 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    elif dp[n][m] == dp[n-1][m-1] + 1:
        ans += t[n-1]
        n -= 1
        m -= 1

print(ans[::-1])

提出結果

Submission #31941466 - Educational DP Contest

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

これはPython3では通らない。\(O(10^6)\)だと自分のcode力だとPython3は歯が立たないことの方が多い。

補足

再現部分について補足。入力例\(4\)で考える。dpテーブルを作成すると、以下のようなテーブルができる。

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2],
 [0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3],
 [0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4],
 [0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4],
 [0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4],
 [0, 1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 4],
 [0, 1, 1, 1, 2, 2, 3, 4, 5, 5, 5, 5],
 [0, 1, 1, 1, 2, 2, 3, 4, 5, 5, 5, 5],
 [0, 1, 1, 2, 2, 2, 3, 4, 5, 5, 6, 6],
 [0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 7]]

一番右下の部分が\(7\)で、これがLCSの長さになっている。下の矢印のように逆に戻っていき、文字を作成し、最後に逆順に表示しているということ。左上に矢印が進む箇所だけがs, tが一致している箇所で、このときのtの文字を配列に入れていって、最後に逆向きに表示する。tがsと一致するindexは逆から\(11, 10, 8, 7, 4, 2, 0\)となる。