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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    S = Scanner.string()
    T = Scanner.string()
    dp = [[0 for _ in range(3100)] for _ in range(3100)]
    for i in range(len(S)):
        for j in range(len(T)):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
            if S[i] == T[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
    ans = ""
    i, j = len(S), len(T)
    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] + ans
            i -= 1
            j -= 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)

V_MAX = int(1e05)+1


def main():
    # sys.stdin = open("sample.txt")
    S = Scanner.string()
    T = Scanner.string()
    dp = [[0 for _ in range(len(T)+1)] for _ in range(len(S)+1)]
    for i in range(len(S)):
        for j in range(len(T)):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
            if S[i] == T[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
    ans = ""
    i, j = len(S), len(T)
    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] + ans
            i -= 1
            j -= 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    elif dp[x-1][y] == dp[x][y-1]:
        x = x-1

print(ans)

Submission status: Wrong Answer

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-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-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
    elif dp[x-1][y] == dp[x][y-1]:
        x = x-1

print(ans)

Submission status: Wrong Answer

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-1] < dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-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
    elif dp[x-1][y] == dp[x][y-1]:
        x = x-1

print(ans)

Submission status: Wrong Answer

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-1] < dp[x][y]:
        ans+=s[x-1]
        x = x-1
        y = y-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
    elif dp[x-1][y] == dp[x][y-1]:
        x = x-1

print(ans[::-1])

Submission status: Wrong Answer

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: Wrong Answer

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])

#答えは、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: Wrong Answer

Solution code:
INF = 10**10 - 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: Wrong Answer

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 res1 > res2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
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 res1 > res2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
n = min(len(S),len(T))
dp = [[ "" for _ in range(n + 1 )] for _ in range(n + 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: Wrong Answer

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


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

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            if len(dp[i][j]) + 1 > len(dp[i][j+1]) and len(dp[i][j]) + 1 > len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i][j] + s[i]
            elif len(dp[i][j+1]) > len(dp[i][j]) + 1 and 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]
        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[-1][-1])

Submission status: Wrong Answer

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():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i]==T[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])
    cur = dp[N][M]
#    print(cur)
    ans = ""
    i = N
    for j in range(M - 1, -1, -1):
        while (i > 0):
            i -= 1
            if dp[i][j] == cur-1:
                cur -= 1
                ans += S[i]
                break
    print(ans[::-1])
    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)]

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Wrong Answer

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

max_dp = max(len(s), len(t)) + 1
dp = [""] * max_dp

begin_i = 0
begin_j = 0
for dp_i in range(1, max_dp):
    for i in range(begin_i,min(len(s), dp_i)):
        for j in range(begin_j, min(len(t), dp_i)):
            if s[i] == t[j]:
                begin_j = j + 1
                begin_i = i + 1
                dp[dp_i] = dp[dp_i - 1] + s[i]
    dp[dp_i] = max(dp[dp_i], dp[dp_i - 1])

print(dp[max_dp - 1])

Submission status: Wrong Answer

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 -= 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: Wrong Answer

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 match(s,t,i,j) == 1:
            dp[i+1][j+1] = dp[i][j]+match(s,t,i,j)
            traceback[i+1][j+1] = 3
        elif dp[i][j+1] >= dp[i+1][j] and dp[i][j+1] >= dp[i][j]+match(s,t,i,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 -= 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: Wrong Answer

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 match(s,t,i,j) == 1:
            dp[i+1][j+1] = dp[i][j]+match(s,t,i,j)
            traceback[i+1][j+1] = 3
        elif dp[i][j+1] >= dp[i+1][j] and dp[i][j+1] >= dp[i][j]+match(s,t,i,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 -= 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: Wrong Answer

Solution code:
s = input()
t = input()
ns= len(s)
nt = len(t)
ans = []
anstmp = ""
DP = [[0 for i in range(nt+1)] for j in range(ns+1)]
for i in range(1,ns+1):
  for j in range(1,nt+1):
    DP[i][j] = max(DP[i-1][j],DP[i][j-1])
    if s[i-1] == t[j-1]:
      DP[i][j] = max(DP[i][j],DP[i-1][j-1]+1)
print(DP[-1][-1])

Submission status: Wrong Answer

Solution code:
# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i) for i in input()], dtype=int)
T = np.array([ord(i) for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    newDP = dp[-1].copy()
    np.maximum(newDP[:-1], newDP[1:] + equal[i], out=newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)

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

print(ans[::-1])

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

s = input()
t = input()

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

for i in range(sl):
    for j in range(tl):
        if s[i] == t[j]: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        dp[i][j+1] = max(dp[i][j+1], dp[i][j])

ans = ''
while sl > 0 and tl > 0:
    if dp[sl][tl-1] == dp[sl][tl]:
        tl -= 1
    elif dp[sl-1][tl] == dp[sl][tl]:
        sl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

s = input()
t = input()

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

for i in range(sl):
    for j in range(tl):
        if s[i] == t[j]: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        dp[i][j+1] = max(dp[i][j+1], dp[i][j])

ans = ''
while sl > 0 and tl > 0:
    if dp[sl-1][tl] == dp[sl][tl]:
        sl -= 1
    elif dp[sl][tl-1] == dp[sl][tl]:
        tl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)

Submission status: Wrong Answer

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

s, t = input(), input()

@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
    return max(lcs(i + 1, j), (s[i] + lcs(i + 1, k)) if k < len(t) else "", key=lambda x: len(x))

print(lcs(0, 0))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

### TESTCASE
test = ""
#test = \
"""
axyb
abyxb
ans axb
ans ayb
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN

s = input2()
t = input2()
sn = len(s)
tn = len(t)
sv = np.array(["A"] + list(s))
tv = np.array(["B"] + list(t))
dp = np.zeros((sn+1, tn+1), dtype="int")

# fill dp table
for si in range(sn):
    flag = np.array(sv[si+1] == tv, dtype="int")
    flag2 = np.array(np.add.accumulate(flag) > 0, dtype="int")
    
    tmp = dp[si] + flag
    tmp2 = dp[si] + flag2 
    
    if (tmp == np.sort(tmp)).all():
        dp[si+1] = tmp
    else:
        dp[si+1] = tmp2

# get ans sequence
ans = ""
si, ti = sn, tn
while si:
    while dp[si][ti] == dp[si][ti-1] and ti:
        ti -= 1
        
    if dp[si][ti] > dp[si-1][ti]:
        ans += t[ti-1]
        
    si -= 1

# output ans
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
t = input()
m = len(t)

dp = [['' for _ in range(m+1)] for _ in range(n+1)]

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

Submission status: Wrong Answer

Solution code:
s = [ord(c) - 97 for c in input()]
n = len(s)
t = [ord(c) - 97 for c in input()]
m = len(t)
dp = [[list() for _ in range(m+1)] for _ in range(n+1)]
print(s,t)
for i in range(n):
    for j in range(m):
    	if t[j]!=s[i]:
    		dp[i+1][j+1] = dp[i+1][j] if(len(dp[i+1][j])>len(dp[i][j+1])) else dp[i][j+1]
    	else :
    		dp[i+1][j+1]= (dp[i][j+1])
    		dp[i+1][j+1].append(t[j])

ans = ''
for i in dp[n][m]:
	ans += chr(i+97)
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import copy
s = input()
t = input()

dp = [['']*(len(t)+1) for _ in range(2)]
for i, ss in enumerate(s):
    for j, tt in enumerate(t):
        a = dp[0][j+1]
        b = dp[1][j]
        if ss == tt:
            c = "".join((dp[1][j], ss))
            if len(a) > len(b) and len(a) > len(c):
                r = a
            elif len(b) > len(a) and len(b) > len(c):
                r = b
            else:
                r = c
            dp[1][j+1] = r
        else:
            if len(a) >= len(b):
                dp[1][j+1] = a
            else:
                dp[1][j+1] = b
    dp[0] = copy(dp[1])
print(dp[-1][-1])