Problem:


Score : 900 points

Problem Statement

Takahashi has decided to give a string to his mother.

The value of a string T is the length of the longest common subsequence of T and T', where T' is the string obtained by reversing T.
That is, the value is the longest length of the following two strings that are equal: a subsequence of T (possibly non-contiguous), and a subsequence of T' (possibly non-contiguous).

Takahashi has a string S. He wants to give her mother a string of the highest possible value, so he would like to change at most K characters in S to any other characters in order to obtain a string of the highest possible value.
Find the highest possible value achievable.

Constraints

1 \leq |S| \leq 300

0 \leq K \leq |S|

S consists of lowercase English letters.

K is an integer.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the highest possible value achievable.

Sample Input 1

abcabcabc
1

Sample Output 1

7

Changing the first character to c results in cbcabcabc.
Let this tring be T, then one longest common subsequence of T and T' is cbabcbc, whose length is 7.

Sample Input 2

atcodergrandcontest
3

Sample Output 2

15



Sample input:
abcabcabc
1


Sample output:
7

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

S = list(map(ord, readline().strip()))
N = len(S)
S = [None] + S + [None]
K = int(readline())

if N == 1:
    ans = 1
elif N == 2:
    ans = 1
    if S[1] == S[2]:
        ans = 2
    if K:
        ans = 2
else:
    dp1 = [[0]*(K+1) for _ in range(N+2)]
    dp2 = [[0]*(K+1) for _ in range(N+2)]
    for i in range(1, N+1):
        dp1[i][0] = 1
    for i in range(1, N):
        dp2[i][0] = 1
        if S[i] == S[i+1]:
            dp2[i][0] = 2    
        elif K:    
            dp2[i][1] = 2
    for s in range(3, N+1):
        dp3 = [[0]*(K+1) for _ in range(N+2)]
        for i in range(1, N-s+2):
            j = i+s-1    
            if S[i] == S[j]:
                for k in range(K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], 2+dp1[i+1][k])
            else:
                dp3[i][0] = max(dp2[i+1][0], dp2[i][0], dp2[i+1][0])
                for k in range(1, K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], dp1[i+1][k], 2+dp1[i+1][k-1])
        '''
        dp1 = [k[:] for k in dp2]
        dp2 = [k[:] for k in dp3]
        '''
        dp1 = dp2[:]
        dp2 = dp3[:]
    ans = max(dp3[1][k] for k in range(K+1))
print(ans)
'''
MLEした
dp = [[[0]*(K+1) for _ in range(N+2)] for _ in range(N+2)]
for i in range(1, N+1):
    dp[i][i][0] = 1
for i in range(1, N):
    dp[i][i+1][0] = 1
    if S[i] == S[i+1]:
        dp[i][i+1][0] = 2    
    elif K:    
        dp[i][i+1][1] = 2
for s in range(3, N+1):
    for i in range(1, N-s+2):
        j = i+s-1
        if S[i] == S[j]:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], 2+dp[i+1][j-1][k])
        else:
            dp[i][j][0] = max(dp[i+1][j][0], dp[i][j-1][0], dp[i+1][j-1][0])
            for k in range(1, K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], dp[i+1][j-1][k], 2+dp[i+1][j-1][k-1], dp[i+1][j-1][k])
print(max(dp[1][N][k] for k in range(K+1)))
'''

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

S = list(map(ord, readline().strip()))
N = len(S)
S = [None] + S + [None]
K = int(readline())

if N == 1:
    ans = 1
elif N == 2:
    ans = 1
    if S[1] == S[2]:
        ans = 2
    if K:
        ans = 2
else:
    dp1 = [[0]*(K+1) for _ in range(N+2)]
    dp2 = [[0]*(K+1) for _ in range(N+2)]
    for i in range(1, N+1):
        dp1[i][0] = 1
    for i in range(1, N):
        dp2[i][0] = 1
        if S[i] == S[i+1]:
            dp2[i][0] = 2    
        elif K:    
            dp2[i][1] = 2
    for s in range(3, N+1):
        dp3 = [[0]*(K+1) for _ in range(N+2)]
        for i in range(1, N-s+2):
            j = i+s-1    
            if S[i] == S[j]:
                for k in range(K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], 2+dp1[i+1][k])
            else:
                dp3[i][0] = max(dp2[i+1][0], dp2[i][0], dp2[i+1][0])
                for k in range(1, K+1):
                    dp3[i][k] = max(dp2[i+1][k], dp2[i][k], dp1[i+1][k], 2+dp1[i+1][k-1])
        dp1 = [k[:] for k in dp2]
        dp2 = [k[:] for k in dp3]
    ans = max(dp3[1][k] for k in range(K+1))
print(ans)
'''
MLEした
dp = [[[0]*(K+1) for _ in range(N+2)] for _ in range(N+2)]
for i in range(1, N+1):
    dp[i][i][0] = 1
for i in range(1, N):
    dp[i][i+1][0] = 1
    if S[i] == S[i+1]:
        dp[i][i+1][0] = 2    
    elif K:    
        dp[i][i+1][1] = 2
for s in range(3, N+1):
    for i in range(1, N-s+2):
        j = i+s-1
        if S[i] == S[j]:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], 2+dp[i+1][j-1][k])
        else:
            dp[i][j][0] = max(dp[i+1][j][0], dp[i][j-1][0], dp[i+1][j-1][0])
            for k in range(1, K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], dp[i+1][j-1][k], 2+dp[i+1][j-1][k-1], dp[i+1][j-1][k])
print(max(dp[1][N][k] for k in range(K+1)))
'''

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

"""
・reversed LCS = 最大長の回文
・(長さ、始点、変更コスト) -> opt value
"""

S = np.frombuffer(readline().rstrip(),'S1')
N = len(S)
K = int(readline())

dp = [None] * (N+1) # 長さ -> array
dp[0] = None # 自身ないので使わない
dp[1] = np.zeros((N,K+10),np.int32); dp[1][:,0] = 1
if N >= 2:
    dp[2] = np.zeros((N-1,K+10),np.int32)
    dp[2][:,0] = 1+(S[:-1]==S[1:])
    dp[2][:,1] = 2

for n in range(3,N+1):
    arr = np.zeros((N-n+1,K+10),np.int32)
    # 両端をマッチしない場合
    np.maximum(arr,dp[n-1][:-1],out=arr)
    np.maximum(arr,dp[n-1][1:],out=arr)
    # 両端をコストなしでマッチさせる場合
    match = (S[:-n+1]==S[n-1:])
    np.maximum(arr,match[:,None]*(dp[n-2][1:-1]+2),out=arr)
    # 両端をコストありでマッチさせる場合
    np.maximum(arr[:,1:],dp[n-2][1:-1,:-1]+2,out=arr[:,1:])
    
    dp[n] = arr

answer = dp[-1][0][:K+1].max()
print(answer)

Submission status: Accepted

Solution code:
def solve(s, k):
    n = len(s)
    if k >= n // 2:
        return n
    dpp = [[1] * (k + 1), [0] * (k + 1)]
    for r in range(1, n):
        dpc = [[0] * (k + 1) for _ in range(r + 2)]
        dpc[r] = [1] * (k + 1)
        for l in range(r - 1, -1, -1):
            dpl, dpl1 = dpc[l], dpp[l + 1]
            if s[l] == s[r]:
                dpc[l] = [c + 2 for c in dpl1]
            else:
                dppl, dpcl1 = dpp[l], dpc[l + 1]
                dpl[0] = max(dppl[0], dpcl1[0])
                for p in range(1, k + 1):
                    dpl[p] = max(dppl[p], dpcl1[p], dpl1[p - 1] + 2)
        dpp = dpc

    return dpp[0][k]


print(solve(input(), int(input())))

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    n = len(s)
    k = int(input())
    # dp[使った回数][左端からの距離][左端]
    dp = [[[1]*(n-i) for i in range(n)] for _ in range(k+1)]

    dp2 = dp[0][1]
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp2[i] = 2
    if k > 0:
        for cnt in range(1, k+1):
            dp2 = dp[cnt][1]
            for i in range(n-1):
                dp2[i] = 2

    for cnt in range(k):
        dp2 = dp[cnt]
        for d in range(2, n):
            dp3 = dp2[d]
            for left in range(n-d):
                right = left+d
                plus = (s[left] == s[right])*2
                dp3[left] = max(
                    dp3[left], dp2[d-1][left],
                    dp2[d-1][left+1], dp2[d-2][left+1]+plus)
                dp[cnt+1][d][left] = max(
                    dp[cnt+1][d][left], dp3[left], dp2[d-2][left+1]+2)
    dp2 = dp[k]
    for d in range(2, n):
        dp3 = dp[d]
        for left in range(n-d):
            right = left+d
            plus = (s[left] == s[right])*2
            dp3[left] = max(
                dp3[left], dp2[d-1][left], dp2[d-1][left+1], dp2[d-2][left+1]+plus)
    print(dp[-1][-1][0])


main()

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]
if n == 2 and k == 0:
  if s == t:
    print(2)
  else:
    print(1)
    exit()
ans = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  if flg:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+2,ans)
  elif K > 0:
    ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K-1]*2+2,ans)
  else:
    ans= max(dp[sfl][sll][K]*2+1,ans)
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]

ans = min(2*K+1,n)
flg2 = 0
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  if ans < max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+1+flg):
    flg2 = flg
  ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+1+flg,ans)
if flg2 == 1:
  print(2/0)
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]
ansls = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  ans= max(dp[sfl][sll][min(K,sll)]*2+1,dp[sfl][sll-1][min(K,sll)]*2+1+flg,ans)
print(max(ansls))

Submission status: Runtime Error

Solution code:
s = list(map(ord, list(input())))
ls = len(s)
lk = int(input())
if lk*2 >= ls: print(ls); exit(0)
lk = 2*lk - ls%2
dp = [[[0]*(lk+1) for _ in range(ls+1)] for i in range(ls+1)]
for k in range(lk+1):
  for i in range(ls):
    for j in range(ls):
      if s[i] == s[-j-1]:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i][j][k] + 1)
      else:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i+1][j][k], dp[i][j+1][k], (k > 0)*(dp[i][j][k-1] + 1))
print(max(dp[ls][ls]))

Submission status: Runtime Error

Solution code:
#coding:utf-8
def check(s, t):
    count = 0
    v = 0
    for i in range(len(s)):
        if s[i] in t[i]:
            count += 1
        else:
            if count > v:
                v = count
            count = 0
    return v
    
s = list(input())
k = int(input())
t = []
tg = []
pat = [0]*len(s)
for i in s[::-1]:
    t.append(i)
    tg.append(i)

for i in range(k):
    v = check(s, t)
    c = 0
    for j in range(len(s)):
        t[j] = s[j]
        if v < check(s, t):
            ind = j
        t[j] = tg[j]
    tg[ind] = s[ind]

print(check(s, tg))

Submission status: Runtime Error

Solution code:
# coding=utf-8

def lcs(s1,s2):
    table = []
    for _ in range(110):
        table.append([0 for _ in range(110)])

    for y in range(1,len(s1)+1):
        for x in range(1,len(s2)+1):
            match = 0
            if s1[y-1]==s2[x-1]:
                match = 1

            v1 = table[y-1][x-1]+match
            v2 = table[y-1][x]
            v3 = table[y][x-1]
            table[y][x] = max(v1,v2,v3)
    return table[len(s1)][len(s2)]

def log(s,s2):
    return
    print("---")
    print("s :"+"".join(s))
    print("s2:"+"".join(s2))

s = list(input())
k = int(input())
s2 = s[::-1]
log(s,s2)

ab = set(s)

for i in range(k):
    idx = -1
    char = ""
    r = -1
    for j in range(len(s)):
        for x in ab:
            t = s[:]
            t[j] = x
            t2 = t[::-1]
            if lcs(t,t2)>r:
                r = lcs(t,t2)
                idx = j
                char = x

    s[idx] = char
    s2 = s[::-1]
    log(s,s2)


print(lcs(s,s2))

Submission status: Runtime Error

Solution code:
# coding=utf-8

def lcs(s1,s2):
    table = []
    for _ in range(100):
        table.append([0 for _ in range(100)])

    for y in range(1,len(s1)+1):
        for x in range(1,len(s2)+1):
            match = 0
            if s1[y-1]==s2[x-1]:
                match = 1

            v1 = table[y-1][x-1]+match
            v2 = table[y-1][x]
            v3 = table[y][x-1]
            table[y][x] = max(v1,v2,v3)
    return table[len(s1)][len(s2)]

def log(s,s2):
    return
    print("---")
    print("s :"+"".join(s))
    print("s2:"+"".join(s2))

s = list(input())
k = int(input())
s2 = s[::-1]
log(s,s2)

ab = set(s)

for i in range(k):
    idx = -1
    char = ""
    r = -1
    for j in range(len(s)):
        for x in ab:
            t = s[:]
            t[j] = x
            t2 = t[::-1]
            if lcs(t,t2)>r:
                r = lcs(t,t2)
                idx = j
                char = x

    s[idx] = char
    s2 = s[::-1]
    log(s,s2)


print(lcs(s,s2))

Submission status: Runtime Error

Solution code:
input = raw_input
range = xrange
n, m, h, v = map(int,input().split())
remain = [n] * m
ind = 0
for i in range(h):
    for odd in range(1, m, 2):
        if remain[odd] % 2 == 1: break
    else:
        for odd in range(1, m, 2):
            if remain[odd]: break
        else: print("NO"); exit()
    if m == 1: print("NO"); exit()
    remain[odd]-= 1; remain[odd-1]-= 1

if sum(x//2 for x in remain) < v: print("NO"); exit()
print("YES")
grid = [["."]*m for i in range(n)]
for j in range(0, m, 2):
    placed = n - remain[j]
    for i in range(placed):
        grid[i][j] = "<"
        grid[i][j+1] = ">"
    for i in range(placed, n, 2):
        if i == n-1: break
        grid[i][j] = "^"
        grid[i+1][j] = "v"
        v-= 1
        if v == 0:
            for row in grid: print(''.join(row))
            exit()
        if j == m-1: continue
        grid[i][j+1] = "^"
        grid[i+1][j+1] = "v"
        v-= 1
        if v == 0:
            for row in grid: print(''.join(row))
            exit()