Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    dp = [[0]*(len(s)+1) for _ in range((len(t)+1))]
    ans = ""
    for i in range(len(t)):
        for j in range(len(s)):
            tmp1 = dp[i+1][j]
            tmp2 = dp[i][j+1]
            tmp3 = dp[i][j]
            if t[i] == s[j]:
                tmp3 += 1
            dp[i+1][j+1] = max(tmp1,tmp2,tmp3)
    i = len(t)
    j = len(s)
    while i > 0 and j > 0:
        if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
            ans += t[i-1]
            i -= 1
            j -= 1
        elif dp[i-1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
    print(ans[::-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] < dp[x][y-1]:
        y = y-1
    elif dp[x-1][y] > dp[x][y-1]:
        x = x-1
    elif dp[x-1][y-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-1
        continue
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] == dp[x][y-1]:
        if dp[x-1][y-1] < dp[x][y]:
            ans += s[x-1]
            x = x-1
            y = y-1
            continue
        else:
            x = x-1
            continue
    elif dp[x-1][y] < dp[x][y-1]:
        y = y-1
    elif dp[x-1][y] < dp[x][y-1]:
        x = x-1

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] == dp[x][y-1]:
        if dp[x-1][y-1] < dp[x][y]:
            ans = ans+s[x-1]
            x = x-1
            y = y-1
            continue
        else:
            x = x-1
            continue
    elif dp[x-1][y] < dp[x][y-1]:
        y = y-1
    elif dp[x-1][y] < dp[x][y-1]:
        x = x-1

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [['' for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            if len(dp[i+1][j]) < len(dp[i][j]) or dp[i+1][j] == '':
                dp[i+1][j] = dp[i][j]
        if j+1 <= LENt:
            if len(dp[i][j+1]) < len(dp[i][j]) or dp[i][j+1] == '':
                dp[i][j+1] = dp[i][j]
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+s[i]

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()

table = [['' for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + si
        else:
            x = table_cur[j]
            y = table_pre[j + 1]
            table_cur[j + 1] = x if len(x) > len(y) else y
print(table[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()

table = ['' for j in range(len(t) + 1)]
table_pre = ['' for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = table_pre[j] + si
        else:
            x = table[j]
            y = table_pre[j + 1]
            table[j + 1] = x if len(x) > len(y) else y
    table, table_pre = table_pre, table
print(table_pre[-1])

Submission status: Time Limit Exceeded

Solution code:
def union_set(x, y):
    return x if len(x) > len(y) else y

s = input()
t = input()

table = ['' for j in range(len(t) + 1)]
table_pre = ['' for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = table_pre[j] + si
        else:
            table[j + 1] = union_set(table[j], table_pre[j + 1])
    table, table_pre = table_pre, table
print(table_pre[-1])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**10 - 1 #無限大
SMAX = 3000 + 10

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、一致文字列長を二次軸に取り
その値として：s2の使用済文字数の最小値を入れる
　　　　　　　0列は 0 それ以外がINFで初期化
'''
dp = [[INF] * (SMAX) for i in range(SMAX)]
for i in range(0,len(s1)+1):
    dp[i][0] = 0
#print(dp[0])

for s1pos in range(1,len(s1)+1):
    s = s1[s1pos-1:s1pos]
    #print("s=",s,"--------")
    for psLen in range(1,s1pos+1):
        s2pos = dp[s1pos-1][psLen-1] + 1
        spos = s2[s2pos-1:].find(s)
        dp[s1pos][psLen] = dp[s1pos-1][psLen]
        if spos == -1:
            pass
        else:
            if dp[s1pos][psLen] > s2pos+spos:
                dp[s1pos][psLen] = s2pos+spos
        #print("s=",s,"ps2=",s2[s2pos-1:],"spos=",spos,"s1pos=",s1pos,"s2pos=",s2pos,"dp=",dp[s1pos])
res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    while dp[s1pos][s2pos] == INF:
        s2pos -= 1
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)

Submission status: Time Limit Exceeded

Solution code:
def union_set(x, y):
    lx, x_set = x
    ly, y_set = y
    l = max(lx, ly)
    if lx == ly:
        z_set = x_set.union(y_set)
    else:
        z_set = x_set if lx > ly else y_set
    return [l, z_set]

def update_set(x, t):
    l, s = x
    return [l + len(t), {si + t for si in list(s)}]

s = input()
t = input()
if len(s) < len(t):
    s, t = t, s

table = [[0, {''}] for j in range(len(t) + 1)]
table_pre = [[0, {''}] for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = update_set(table_pre[j], si)
        else:
            table[j + 1] = union_set(table[j], table_pre[j + 1])
    table, table_pre = table_pre, table
print(list(table_pre[-1][1])[0])

Submission status: Time Limit Exceeded

Solution code:
def union_set(x, y):
    lx, x_set = x
    ly, y_set = y
    l = max(lx, ly)
    if lx == ly:
        z_set = x_set.union(y_set)
    else:
        z_set = x_set if lx > ly else y_set
    return [l, z_set]

def update_set(x, t):
    l, s = x
    return [l + len(t), {si + t for si in list(s)}]

s = input()
t = input()

table = [[0, {''}] for j in range(len(t) + 1)]
table_pre = [[0, {''}] for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = update_set(table_pre[j], si)
        else:
            table[j + 1] = union_set(table[j], table_pre[j + 1])
    table, table_pre = table_pre, table
print(list(table_pre[-1][1])[0])

Submission status: Time Limit Exceeded

Solution code:
def union_set(x, y):
    lx, x_set = x
    ly, y_set = y
    l = max(lx, ly)
    if lx == ly:
        z_set = x_set.union(y_set)
    else:
        z_set = x_set if lx > ly else y_set
    return [l, z_set]

def update_set(x, t):
    l, s = x
    return [l + len(t), {si + t for si in list(s)}]

s = input()
t = input()

table = [[[0, {''}] for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[i + 1][j + 1] = update_set(table[i][j], si)
        else:
            table[i + 1][j + 1] = union_set(table[i + 1][j], table[i][j + 1])
print(list(table[-1][-1][1])[0])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**10 - 1 #無限大
SMAX = 3000 + 1

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (len(s2)+1) for i in range(len(s2)+1)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    #print("s1pos=",s1pos,"dp=",dp[s1pos])

#print("LCS_len",dp[len(s1)][len(s2)])

res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**2 - 1 #無限大
SMAX = 3000 + 1

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、一致文字列長を二次軸に取り
その値として：s2の使用済文字数の最小値を入れる
　　　　　　　0列は 0 それ以外がINFで初期化
'''
dp = [[INF] * (len(s1)+1) for i in range(len(s1)+1)]
for i in range(0,len(s1)+1):
    dp[i][0] = 0
#print(dp[0])

for s1pos in range(1,len(s1)+1):
    s = s1[s1pos-1:s1pos]
    #print("s=",s,"--------")
    for psLen in range(1,s1pos+1):
        s2pos = dp[s1pos-1][psLen-1] + 1
        spos = s2[s2pos-1:].find(s)
        dp[s1pos][psLen] = dp[s1pos-1][psLen]
        if spos == -1:
            pass
        else:
            if dp[s1pos][psLen] > s2pos+spos:
                dp[s1pos][psLen] = s2pos+spos
        #print("s=",s,"ps2=",s2[s2pos-1:],"spos=",spos,"s1pos=",s1pos,"s2pos=",s2pos,"dp=",dp[s1pos])

#答えは、DP配列を最善値を出したところを逆方向に辿る
Ans = ""
pos1 = len(s1)
pos2 = len(s1)
for s1pos in range(pos1,0,-1):
    s = s1[s1pos-1:s1pos]
    for psLen in range(pos2,0,-1):
        if dp[s1pos][psLen] < INF:
            if dp[s1pos-1][psLen] > dp[s1pos][psLen]:
                Ans = s + Ans
                pos2 = psLen - 1
                break
            else:
                continue
    #print("s1pos=",s1pos,"s=",s,"dp=",dp[s1pos],"Ans=",Ans)

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
dp = [[ "" for _ in range(len(S) + 1 )] for _ in range(len(T) + 1)]

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = dp[i-1][j-1] + S[j-1]
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            l1 = len(res1)
            l2 = len(res2)
            if l1 > l2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()

dp = [[ "" for _ in range(len(S) + 1 )] for _ in range(len(T) + 1)]

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = dp[i-1][j-1] + S[j-1]
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            l1 = len(res1)
            l2 = len(res2)
            if l1 > l2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()

dp = [[ "" for _ in range(len(S) + 1 )] for _ in range(len(T) + 1)]

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = dp[i-1][j-1] + S[j-1]
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            if max([len(res1),len(res2)]) == len(res1):
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()

import sys
sys.setrecursionlimit(2147483647)

def dfs(i,j):
    if (i,j) in dic: return dic[(i,j)]
    if i > len(S) - 1 or j > len(T) - 1:
        return ""
    ans  = ""
    if S[i] == T[j]:
        ans = S[i] + dfs(i + 1,j + 1)
    else:
        res1 = dfs(i + 1,j)
        res2 = dfs(i, j + 1)
        if max([len(res1),len(res2)]) == len(res1):
            ans = res1
        else:
            ans = res2
    dic[(i,j)] = ans
    return ans
dic = {}
print(dfs(0,0))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()

from functools import lru_cache
import sys
sys.setrecursionlimit(2147483647)

@lru_cache(None)
def dfs(i,j):
    if i > len(S) - 1 or j > len(T) - 1:
        return ""
    if S[i] == T[j]:
        return S[i] + dfs(i + 1,j + 1)
    else:
        res1 = dfs(i + 1,j)
        res2 = dfs(i, j + 1)
        if max([len(res1),len(res2)]) == len(res1):
            return res1
        else:
            return res2
    
print(dfs(0,0))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0]*(T+1) for _ in range(S+1)]

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

ans = ""
while S and T:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1]+ans
        S -= 1
        T -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [[""]*(S+1) for _ in range(T+1)]

    for i in range(T):
        for j in range(S):
            if s[j] == t[i]:
                dp[i+1][j+1] = dp[i][j] + s[j]
            else:
                if len(dp[i+1][j]) >= len(dp[i][j+1]):
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]
    print(dp[T][S])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
S = len(s)
T = len(t)
dp = [[""]*(S+1) for _ in range(T+1)]

for i in range(T):
    for j in range(S):
        if s[j] == t[i]:
            dp[i+1][j+1] = dp[i][j] + s[j]
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
print(dp[T][S])

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
s=len(S)
t=len(T)
#dp[i][j] Sのi文字目までとTのj文字目までで最大共通文字数
dp=[[0]*(t+1) for i in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # https://mzp.hatenadiary.org/entry/20100623/lcs
    # LCS
    def maxBy(f, x, y):
        if f(x) > f(y):
            return x
        else:
            return y
    def lcs(xs, ys, table):
        if (xs, ys) in table:
            return table[(xs, ys)]
        ret = ""
        if xs == "" or ys == "":
            ret = ""
        elif xs[-1] == ys[-1]:
            ret = lcs(xs[:-1], ys[:-1], table) + xs[-1]
        else:
            ret = maxBy(len,
                        lcs(xs[:-1], ys, table),
                        lcs(xs, ys[:-1], table))
        table[(xs, ys)] = ret
        return ret

    S = SI(); N = len(S)
    T = SI(); M = len(T)
    ans = lcs(S,T,{ ("","") : "" })
    print(ans)
    return

def examG():

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
s = input()
t = input()
dp = [[0]*(1+len(t)) for _ in range(1+len(s))]
def match(s_,t_,i,j):
    if s_[i] == t_[j]:
        return 1
    else: return 0
#　配列アラインメントの感じでマッチしたら+1 そうでなかったら+0を返す
# traceback関数を作って戻る必要がある
# 漸化式 dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],dp[i][j]+match())
# traceback[i+1][j+1] = 0 だったら上、1なら左、2なら斜め
traceback =[[-1]*(1+len(t)) for _ in range(1+len(s))]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j]+1
            traceback[i+1][j+1] = 3
        elif dp[i][j+1] >= dp[i+1][j]:
            dp[i+1][j+1] = dp[i][j+1]
            traceback[i+1][j+1] = 1
        else:
            dp[i+1][j+1] = dp[i+1][j]
            traceback[i+1][j+1] = 2
        
# traceback時の初期値がx = len(s),y = len(t)
# tracebackの挙動を見ながらx,y を更新する
#　終了条件はx,y == 0,0 になったとき
# traceback[x][y] % 2 == 1 の時、s[x-1]を出力する。
x,y = len(s),len(t)
"""for i in range(1+len(s)):
    #print(dp[i])
    print(traceback[i])
"""
output = []
while True:
    if traceback[x][y] == 3:
        output.append(s[x-1])
        #print()
    x_ = x
    y_ = y
    x -= traceback[x_][y_] % 2 
    y -= traceback[x_][y_] // 2
    #print(x,y)
    if x == 1 and y == 1:
        if traceback[x][y] == 3:
            output.append(s[x-1])
        break
    if x == 0 or y == 0:
        break
for i in range(len(output)-1,-1,-1):
    print(output[i],end="")
print()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()

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

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


ans = ""
x = len(s)
y = len(t)
d = dp[-1][-1]
while True:
  if d == 0:
    break
  if dp[y - 1][x] == d:
    y -= 1
  elif dp[y][x - 1] == d:
    x -= 1
  else:
    ans += t[y - 1]
    x -= 1
    y -= 1
    d -= 1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
def LCS(S,T):
  #初期化
  dp=[["" 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)):
      if len(dp[i][j+1]) > len(dp[i+1][j]):
        dp[i+1][j+1]=dp[i][j+1]
      else:
        dp[i+1][j+1]=dp[i+1][j]
      if S[i]==T[j]:
        if len(dp[i+1][j+1]) > len(dp[i][j])+1:
          dp[i+1][j+1]=dp[i+1][j+1]
        else:
          dp[i+1][j+1]=dp[i][j]+S[i]
         
      
  return dp[len(S)][len(T)]

print(LCS(S,T))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

s=ss()
t=ss()
dp = [[[0,"0"] for i in range(len(s)+1)] for j in range(len(t)+1)] #0で初期化

for i in range(len(t)):
    for j in range(len(s)):
        if s[j] ==t[i]:
            dp[i+1][j+1] = [dp[i][j][0] + 1,dp[i][j][1] +s[j]]

        else:
            if dp[i+1][j][0] >=  dp[i][j+1][0]:
                dp[i+1][j+1] = [dp[i+1][j][0],dp[i+1][j][1]]
            else:
                dp[i+1][j+1] = [dp[i][j+1][0], dp[i][j+1][1]]

print(dp[-1][-1][1][1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

s=ss()
t=ss()
dp = [[[0,"0"] for i in range(len(s)+1)] for j in range(len(t)+1)] #0で初期化

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

Submission status: Time Limit Exceeded

Solution code:
# LongestCommonSubsequences
S = input()
T = input()
Ns = len(S)
Nt = len(T)

dp = [[0] * (Nt + 1) for _ in range(Ns + 1)]

for i in range(Ns):
    for j in range(Nt):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""
i = Ns
j = Nt
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

ans = ans[::-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# LongestCommonSubsequences
S = input()
T = input()
Ns = len(S)
Nt = len(T)

dp = [[0] * (Nt + 1) for _ in range(Ns + 1)]

for i in range(1, Ns + 1):
    s = S[i-1]
    for j in range(1, Nt + 1):
        t = T[j-1]
        if s == t:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

ans = ""
i = Ns
j = Nt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += S[i-1]
        i -= 1
        j -= 1

ans = ans[::-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ひとまず長さだけ持つ，後から表を後ろ向きに見て復元を試みる

s=input()
t=input()

ls=len(s)
lt=len(t)
    
    
#sのi文字目とtのj文字目までで取れる最長部分列の長さ
dp=[[0]*(lt+1) for _ in range(ls+1)]

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

ans=""
i=ls
j=lt
while(i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        i-=1
        j-=1
        ans+=s[i]

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
#計算量的にはきつそうだけど，dp[i][j]でやる？

s=input()
t=input()

ls=len(s)
lt=len(t)

add=ls-lt
if add>0:
    t+="T"*add
else:
    s+="S"*(-1*add)
N=len(s)
    
    
#sのi文字目とtのj文字目までで取れる最長部分列
dp=[[""]*(N+1) for _ in range(N+1)]

temp=["",""]

for i in range(N):
    for j in range(N):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
            L=len(dp[i+1][j+1])
        else:
            temp[0]=dp[i+1][j]
            temp[1]=dp[i][j+1]
            if len(temp[0])>len(temp[1]):
                dp[i+1][j+1]=temp[0]
            else:
                dp[i+1][j+1]=temp[1]

                    
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jan 23 10:17:15 2020

@author: matsui
"""

import numpy as np


s=input()
t=input()

Ls=len(s)
Lt=len(t)
dp=np.zeros([Ls+1,Lt+1])

for i in range(Ls):
    for j in range(Lt):
        if s[i]==t[j]:
            dp[i+1,j+1]=dp[i,j]+1
        if dp[i,j+1]>dp[i+1,j+1]: dp[i+1,j+1]=dp[i,j+1]
        if dp[i+1,j]>dp[i+1,j+1]: dp[i+1,j+1]=dp[i+1,j]
        
result=''
i=Ls-1
j=Lt-1
while(i>=0 and j>=0):
    if dp[i+1,j+1]==0: break
    if dp[i+1,j+1]==dp[i,j+1]: 
        i-=1
    elif dp[i+1,j+1]==dp[i+1,j]: 
        j-=1
    else:
        result=s[i]+result
        i-=1
        j-=1
                

print(result)

Submission status: Time Limit Exceeded

Solution code:
def LCS(X,Y):
    m,n=len(X),len(Y)
    MAP=[[0 for i in range(m)] for j in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if Y[i]==X[j]:
                MAP[i][j]=MAP[i-1][j-1]+1
            else:
                MAP[i][j]=max(MAP[i][j-1],MAP[i-1][j])

    i,j=n-1,m-1
    ans=""
    while MAP[i][j]!=0:
        if MAP[i][j]==MAP[i-1][j]:i -=1
        elif MAP[i][j]==MAP[i][j-1]:j -=1
        else:
            ans +=Y[i]
            i -=1
            j -=1
    return ans[::-1]


print(LCS(" "+input()," "+input()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def LCS(X,Y):
    m,n=len(X),len(Y)
    MAP=[[0 for i in range(m)] for j in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if Y[i]==X[j]:
                MAP[i][j]=MAP[i-1][j-1]+1
            else:
                MAP[i][j]=max(MAP[i][j-1],MAP[i-1][j])

    i,j=n-1,m-1
    ans=""
    while MAP[i][j]!=0:
        if MAP[i-1][j]!=MAP[i][j] and MAP[i][j-1]!=MAP[i][j]:
            ans +=Y[i]
            i -=1
            j -=1
        elif MAP[i-1][j]!=MAP[i][j] and MAP[i][j-1]==MAP[i][j]:
            j -=1
        elif MAP[i-1][j]==MAP[i][j] and MAP[i][j-1]!=MAP[i][j]:
            i -=1
        else:
            i -=1
    return ans[::-1]


print(LCS(" "+input()," "+input()))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jan 23 10:17:15 2020

@author: matsui
"""

def remove(T):
    R=[]
    L=len(T[0])
    for t in T:
        for i in range(L):
            R.append(t[:i]+t[(i+1):])
    return R

def ag(T,S):
    for t in T:
        if t in S:
            return t
            break
    return ''


s=input()
t=input()

if len(s)<len(t): t,s=s,t


Ls=len(s)
Lt=len(t)
S=[s]
T=[t]

for i in range(Ls):
    result=ag(T,S)
    #print(result)
    if result=='':
        if len(S[0])==len(T[0]): T=remove(T)
        S=remove(S)
    else:
        break

            
print(result)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**5)

s, t = input(), input()

d = {chr(a): {} for a in range(97, 97 + 26)}
for a in range(97, 97 + 26):
    last = None
    for i in range(len(t) - 1, -1, -1):
        if t[i] == chr(a):
            last = i
        d[chr(a)][i] = last

ans = set()
order = []

@lru_cache(maxsize=None)
def lcs(i, j):
    if i >= len(s):
        return 0
    k = d[s[i]][j] if j < len(t) else None
    v1, v2 = lcs(i + 1, j), (1 + lcs(i + 1, k + 1)) if k is not None else 0
    if v1 >= v2:
        return v1
    if i not in ans:
        ans.add(i)
        order.append(i)
    return v2

lcs(0, 0)
print("".join(s[i] for i in order[::-1]))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**5)

s, t = input(), input()

d = {chr(a): {} for a in range(97, 97 + 26)}
for a in range(97, 97 + 26):
    last = None
    for i in range(len(t) - 1, -1, -1):
        if t[i] == chr(a):
            last = i
        d[chr(a)][i] = last

@lru_cache(maxsize=None)
def lcs(i, j):
    if i >= len(s):
        return ""
    # k = j
    # while k < len(t) and s[i] != t[k]:
    #     k += 1
    k = d[s[i]][j] if j < len(t) else None
    return max(lcs(i + 1, j), (t[k] + lcs(i + 1, k + 1)) if k is not None else "", key=lambda x: len(x))

print(lcs(0, 0))