競プロ初中級者100問

ALDS1 10C 最長共通部分列

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc120/tasks/abc120_d

この問題は動的計画法で解くことができます。

方針

全探索では間に合いませんので、動的計画法により解きます。各クエリに対して計算量はO(MN)となるので、全体の計算量はO(qMN)です。これが想定解法と思われますがPython3の場合はTLEとなってしまいました。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Q = int(input())

def lcs(X, Y):
    dp = [[0] * (len(X)+1) for _ in range(len(Y)+1)]
    for i in range(1,len(Y)+1):
        for j in range(1,len(X)+1):
            if X[j-1]==Y[i-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp[-1][-1]

ans = []
for q in range(Q):
    X = input()
    Y = input()
    ans.append(lcs(X,Y))
for a in ans:
    print(a)

記事情報

  • 投稿日：2020年5月20日
  • 最終更新日：2020年5月20日