Problem:


Score : 600 points

Problem Statement

We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.

After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

1 \leq N \leq 2000

1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_{3N}

Output

Print the maximum number of points you can gain.

Sample Input 1

2
1 2 1 2 2 1

Sample Output 1

2

Let us rearrange the five leftmost cards so that the integers written on the six cards will be 2\ 2\ 2\ 1\ 1\ 1 from left to right.

Then, remove the three leftmost cards, all of which have the same integer 2, gaining 1 point.

Now, the integers written on the remaining cards are 1\ 1\ 1.

Since these three cards have the same integer 1, we gain 1 more point.

In this way, we can gain 2 points - which is the maximum possible.

Sample Input 2

3
1 1 2 2 3 3 3 2 1

Sample Output 2

1

Sample Input 3

3
1 1 2 2 2 3 3 3 1

Sample Output 3

3



Sample input:
2
1 2 1 2 2 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/abc176/tasks/abc176_f

dp[i][c1][c2] = 先頭2枚がc1とc2(c1<=c2)の時の答えの最大
で解けるようだ
毎回の処理をO(N)に抑えなくてはいけない

3枚が同じときは取っちゃえばいいので、3枚みたいな変数を用意しておいて答えに足せばいい
2枚が同じな時、更新するべきはc1とc2のうち片方以上が同じな場合
→残る2枚は確定するので、O(N)の更新が必要
1枚あるのをセットにする場合、c1=c2である。残りの2枚は確定するので、O(1)で更新できる。

セットにせず、カードを交換する場合も考える
新しいカードでそろえる場合は、渡される2枚は関係ないので、maxを持っておき、それで置き換えればいい
新しい+古いカードの場合は、そのカードを含む最大で更新すればいい？
→O(N)で更新するために、あるカードを含む数値の最大をもっておく

"""

import sys
from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
for i in range(3*N):
    A[i] -= 1

nmax = 0 #現在のdp配列中の最大値
maxin = [float("-inf")] * N #あるカードが入っている場合の最大値
three = 0 #3枚が同じ場合

dp = [ [float("-inf")] * N for i in range(N) ]
c1,c2 = A[:2]
if c1 > c2:
    c1,c2 = c2,c1
dp[c1][c2] = 0
dp[c2][c1] = 0
maxin[c1] = 0
maxin[c2] = 0
#print ("dp:",dp,file=sys.stderr)

for loop in range(N-1):

    cards = A[2+3*loop:5+3*loop]
    cards.sort()

    #全てが同じ場合、処理をパスする
    if cards[0] == cards[1] and cards[1] == cards[2]:
        three += 1
        continue

    change = [] #更新個所を覚えて置き、最後に一気に更新する (c1,c2,値)

    #2枚が同じ場合を処理する
    if cards[0] == cards[1]:
        nc = cards[0]
        for i in range(N):
            change.append((i,cards[2],dp[i][nc] + 1))
            """
            c1 = cards[2]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))
            """
    if cards[1] == cards[2]:
        nc = cards[1]
        for i in range(N):
            change.append((i,cards[0],dp[i][nc] + 1))
            """
            c1 = cards[0]
            c2 = i
            if c1 > c2:
                c1,c2 = c2,c1
            if nc <= i:
                change.append((c1,c2,dp[nc][i]+1))
            else:
                change.append((c1,c2,dp[i][nc]+1))
            """

    #1枚が同じ場合を処理する
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[0]][cards[0]]+1))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,dp[cards[1]][cards[1]]+1))
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,dp[cards[2]][cards[2]]+1))

    #新しいカードでそろえる場合
    c1 = cards[0]
    c2 = cards[1]
    change.append((c1,c2,nmax))
    c1 = cards[1]
    c2 = cards[2]
    change.append((c1,c2,nmax))
    c1 = cards[0]
    c2 = cards[2]
    change.append((c1,c2,nmax))

    #新しいカード+1の場合
    for c1 in cards:
        for c2 in range(N):
            change.append((c1,c2,maxin[c2]))

    #dp配列の更新作業
    #nmaxとmaxinも更新する

    for c1,c2,tmp in change:
        nmax = max(nmax,tmp)
        dp[c1][c2] = max(dp[c1][c2],tmp)
        dp[c2][c1] = max(dp[c2][c1],tmp)
        maxin[c1] = max(maxin[c1],tmp)
        maxin[c2] = max(maxin[c2],tmp)

    #print ("dp:",dp,file=sys.stderr)

nmax = max(nmax , dp[A[-1]][A[-1]] + 1)
print (nmax + three)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
I=2*N
D=[[-I]*(N+1)for _ in range(N+1)]
M=0
r=[-I]*(N+1)
def c(i,j,k):
    D[i][j]=max(k,D[i][j])
    D[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
X=A[0]
Y=A[1]
D[X][Y]=0
D[Y][X]=0
r[X]=0
r[Y]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,max(M,D[Z][Z]+1)))
    C.append((Y,Z,max(M,D[X][X]+1)))
    C.append((X,Z,max(M,D[Y][Y]+1)))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in C:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-5] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(ma, X[a2][a2] + 1), max(ma, X[a1][a1] + 1)
        X[a2] = [max(x, m) for x, m in zip(X[a2], MA)]
        MA = [max(m, x1, x2) for m, x1, x2 in zip(MA, X[a1], X[a2])]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        X[a][b], X[a][c], X[b][c] = max(ma, X[c][c] + 1), max(ma, X[b][b] + 1), max(ma, X[a][a] + 1)
        X[a] = [max(x, m) for x, m in zip(X[a], MA)]
        X[b] = [max(x, m) for x, m in zip(X[b], MA)]
        X[c] = [max(x, m) for x, m in zip(X[c], MA)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(m, xa, xb, xc) for m, xa, xb, xc in zip(MA, X[a], X[b], X[c])]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def check_triple(L):
    ret = L[:]
    for l in L:
        if L.count(l) >= 3:
            val = l
            for i in range(3):
                ret.remove(l)
            return True, ret
    return False, ret

'''
    dic = defaultdict(lambda:0)
    val = None
    for l in L:
        dic[l] += 1
        if dic[l] == 3:
            val = l
            break
    if val != None:
        ret = []
        cnt = 0
        for l in L:
            if l == val and cnt < 3:
                cnt += 1
                continue
            else:
                ret.append(l)
        return True, ret
    else:
        return False, L
'''


def run():
    N, *A = map(int, read().split())

    dp = [defaultdict(lambda:0) for i in range(N)]
    prim = sorted(A[:2])
    prim = tuple(prim)
    dp[0][prim] = 0
    for i in range(N-1):
        for key, score in dp[i].items():
            a, b = key
            temp_lis = [a,b] + A[2 + i * 3: 5 + i * 3]
            temp_lis = sorted(temp_lis)

            #print(temp_lis, '--->')
            ANS, temp_lis = check_triple(temp_lis)

            #print(temp_lis)
            if ANS:
                temp_lis = tuple(sorted(temp_lis))
                dp[i+1][temp_lis] = max(score + 1, dp[i+1][temp_lis])
            else:
                temp_lis = sorted(temp_lis)
                for idx, a in enumerate(temp_lis):
                    for b in temp_lis[idx+1:]:
                        dp[i+1][(a, b)] = max(dp[i+1][(a,b)], score)

    ans = max(dp[N-1].values())

    for key, score in dp[N-1].items():
        a, b = key
        if a == b and a == A[-1]:
            ans = max(ans, score + 1)

    print(ans)



if __name__ == "__main__":
    #a = [1,2,3,4,5]
    #for i in range(1000000):
    #    check_triple(a)
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def check_triple(L):
    val = 0
    for l in L:
        if L.count(l) >= 3:
            val = l
            break
    if val:
        for i, l in enumerate(L):
            if l == val:
                ret = L[:i] + L[i+3:]
                break
        return True, ret
    else:
        return False, L

'''
    dic = defaultdict(lambda:0)
    val = None
    for l in L:
        dic[l] += 1
        if dic[l] == 3:
            val = l
            break
    if val != None:
        ret = []
        cnt = 0
        for l in L:
            if l == val and cnt < 3:
                cnt += 1
                continue
            else:
                ret.append(l)
        return True, ret
    else:
        return False, L
'''


def run():
    N, *A = map(int, read().split())

    dp = [defaultdict(lambda:0) for i in range(N)]
    prim = sorted(A[:2])
    prim = tuple(prim)
    dp[0][prim] = 0
    for i in range(N-1):
        for key, score in dp[i].items():
            a, b = key
            temp_lis = [a,b] + A[2 + i * 3: 5 + i * 3]
            temp_lis = sorted(temp_lis)

            #print(temp_lis, '--->')
            ANS, temp_lis = check_triple(temp_lis)

            #print(temp_lis)
            if ANS:
                temp_lis = tuple(sorted(temp_lis))
                dp[i+1][temp_lis] = max(score + 1, dp[i+1][temp_lis])
            else:
                temp_lis = sorted(temp_lis)
                for idx, a in enumerate(temp_lis):
                    for b in temp_lis[idx+1:]:
                        dp[i+1][(a, b)] = max(dp[i+1][(a,b)], score)

    ans = max(dp[N-1].values())

    for key, score in dp[N-1].items():
        a, b = key
        if a == b and a == A[-1]:
            ans = max(ans, score + 1)

    print(ans)



if __name__ == "__main__":
    #print('start')
    #for i in range(1):
    #    print(check_triple([1,1,2,2,2]))
    #print('dane')
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def check_triple(L):
    dic = defaultdict(lambda:0)
    val = None
    for l in L:
        dic[l] += 1
        if dic[l] == 3:
            val = l
            break
    if val != None:
        ret = []
        cnt = 0
        for l in L:
            if l == val and cnt < 3:
                cnt += 1
                continue
            else:
                ret.append(l)
        return True, ret
    else:
        return False, L


def run():
    N, *A = map(int, read().split())

    dp = [defaultdict(lambda:0) for i in range(N)]
    prim = sorted(A[:2])
    prim = tuple(prim)
    dp[0][prim] = 0
    for i in range(N-1):
        for key, score in dp[i].items():
            a, b = key
            temp_lis = [a,b] + A[2 + i * 3: 5 + i * 3]
            #print(temp_lis, '--->')
            ANS, temp_lis = check_triple(temp_lis)

            #print(temp_lis)
            if ANS:
                temp_lis = tuple(sorted(temp_lis))
                dp[i+1][temp_lis] = max(score + 1, dp[i+1][temp_lis])
            else:
                temp_lis = sorted(temp_lis)
                for idx, a in enumerate(temp_lis):
                    for b in temp_lis[idx+1:]:
                        dp[i+1][(a, b)] = max(dp[i+1][(a,b)], score)

    ans = max(dp[N-1].values())

    for key, score in dp[N-1].items():
        a, b = key
        if a == b and a == A[-1]:
            ans = max(ans, score + 1)

    print(ans)










if __name__ == "__main__":
    #print(check_triple([1,2,1,2,2]))
    run()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(i,x,y):
        if mem[(i,x,y)] is not None:
            return mem[(i,x,y)]
        cnt = {}
        f = [1]*5
        res = 0
        c = [x,y]+a[i+2:i+5]
        for b in c:
            if b in cnt:
                cnt[b] += 1
                if cnt[b] >= 3:
                    res += 1
                    for j in range(5):
                        if c[j] == b:
                            f[j] = 0
                            cnt[b] -= 1
                        if cnt[b] < 1:
                            break
                    break
            else:
                cnt[b] = 1
        if i == 3*(n-1):
            return res
        m = 0
        for k in range(5):
            if not f[k]:
                continue
            for j in range(k):
                if not f[j]:
                    continue
                r = dfs(i+3, c[j], c[k])
                if m < r:
                    m = r
        res += m
        mem[(i,x,y)] = mem[(i,y,x)] = res
        return res
    n = I()
    a = LI()
    mem = defaultdict(lambda : None)
    print(dfs(0,a[0],a[1]))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()


n = ni()
a = na()

dp = [[-99999999] * (n+1) for _ in range(n+1)]
dp[a[0]][a[1]] = 0

dprow = [-99999999] * (n+1)
dpcol = [-99999999] * (n+1)
dprow[a[0]] = 0
dpcol[a[1]] = 0

margin = 0
for i in range(2, 3*n-2, 3):
    if a[i] == a[i+1] and a[i+1] == a[i+2]:
        margin += 1
    else:
        q = []
        for jj in range(i, i+3):
            if dp[a[jj]][a[jj]] < 0:
                continue
            if jj == i:
                q.append((a[i+1], a[i+2], dp[a[jj]][a[jj]] + 1))
            if jj == i+1:
                q.append((a[i], a[i+2], dp[a[jj]][a[jj]] + 1))
            if jj == i+2:
                q.append((a[i], a[i+1], dp[a[jj]][a[jj]] + 1))

        for jj in range(i, i+3):
            for kk in range(jj+1, i+3):
                if a[jj] == a[kk]:
                    rem = i+i+1+i+2-jj-kk
                    for t in range(n+1):
                        if dp[a[jj]][t] >= 0:
                            q.append((t, a[rem], dp[a[jj]][t] + 1))
                        if dp[t][a[jj]] >= 0:
                            q.append((t, a[rem], dp[t][a[jj]] + 1))
        for j in range(n+1):
            if dprow[j] >= 0:
                for k in (a[i], a[i + 1], a[i + 2]):
                    q.append((j, k, dprow[j]))
            if dpcol[j] >= 0:
                for k in (a[i], a[i + 1], a[i + 2]):
                    q.append((k, j, dpcol[j]))
        mx = max(dprow)
        for jj in range(i, i+3):
            for kk in range(jj+1, i+3):
                q.append((a[jj], a[kk], mx))
        for u in q:
            dp[u[0]][u[1]] = max(dp[u[0]][u[1]], u[2])
            dprow[u[0]] = max(dprow[u[0]], u[2])
            dpcol[u[1]] = max(dpcol[u[1]], u[2])
        # print(i)
        # for row in dp:
        #     print(row)
        # print(dprow)
        # print(dpcol)

ans = max(*dprow, dp[a[-1]][a[-1]] + 1)

print(ans+margin)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(i,x,y):
        if mem[(i,x,y)] is not None:
            return mem[(i,x,y)]
        cnt = {}
        f = [1]*5
        res = 0
        c = [x,y]+a[i+2:i+5]
        for b in c:
            if b in cnt:
                cnt[b] += 1
                if cnt[b] >= 3:
                    res += 1
                    for j in range(5):
                        if c[j] == b:
                            f[j] = 0
                            cnt[b] -= 1
                        if cnt[b] < 1:
                            break
                    break
            else:
                cnt[b] = 1
        if i == 3*(n-1):
            return res
        m = 0
        for k in range(5):
            if not f[k]:
                continue
            for j in range(k):
                if not f[j]:
                    continue
                r = dfs(i+3, c[j], c[k])
                if m < r:
                    m = r
        res += m
        mem[(i,x,y)] = res
        return res
    n = I()
    a = LI()
    mem = defaultdict(lambda : None)
    print(dfs(0,a[0],a[1]))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys #追加
sys.setrecursionlimit(500*500)

n=int(input())
a=list(map(int,input().split()))

point=0
import itertools

#aryは残ったインデックスに、3*k,3*k+1,3*k+2が追加される
def saiki(ary,k,p):
    #print(ary,k,p)
    global point,a,n

    if k==n:
        if a[ary[0]]==a[ary[1]] and a[ary[0]]==a[3*k-1]:
            point=max(point,p+1)
        else:
            point=max(point,p)
        return
    else:

        full_index=ary+[3*k-1,3*k,3*k+1]
        kouho_index=itertools.permutations(full_index, 3)
        for index_pair in kouho_index:

            amari=[]
            for i in full_index:
                if i not in index_pair:
                    amari.append(i)


            if a[index_pair[0]]==a[index_pair[1]] and a[index_pair[1]]==a[index_pair[2]]:
                saiki(amari,k+1,p+1)
            else:
                saiki(amari,k+1,p)
saiki([0,1],1,0)
print(point)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()


n = ni()
a = na()

dp = [[-99999999] * (n+1) for _ in range(n+1)]
dp[a[0]][a[1]] = 0

dprow = [-99999999] * (n+1)
dpcol = [-99999999] * (n+1)
dprow[a[0]] = 0
dpcol[a[1]] = 0

margin = 0
for i in range(2, 3*n-2, 3):
    if a[i] == a[i+1] and a[i+1] == a[i+2]:
        margin += 1
    else:
        q = []
        for jj in range(i, i+3):
            if jj == i:
                q.append((a[i+1], a[i+2], dp[a[jj]][a[jj]] + 1))
            if jj == i+1:
                q.append((a[i], a[i+2], dp[a[jj]][a[jj]] + 1))
            if jj == i+2:
                q.append((a[i], a[i+1], dp[a[jj]][a[jj]] + 1))

        for jj in range(i, i+3):
            for kk in range(jj+1, i+3):
                if a[jj] == a[kk]:
                    rem = i+i+1+i+2-jj-kk
                    for t in range(n+1):
                        q.append((t, a[rem], dp[a[jj]][t] + 1))
                        q.append((t, a[rem], dp[t][a[jj]] + 1))
        for j in range(n+1):
            for k in (a[i], a[i + 1], a[i + 2]):
                q.append((j, k, dprow[j]))
                q.append((k, j, dpcol[j]))
        mx = max(dprow)
        for jj in range(i, i+3):
            for kk in range(jj+1, i+3):
                q.append((a[jj], a[kk], mx))
        for u in q:
            dp[u[0]][u[1]] = max(dp[u[0]][u[1]], u[2])
            dprow[u[0]] = max(dprow[u[0]], u[2])
            dpcol[u[1]] = max(dpcol[u[1]], u[2])
        # print(i)
        # for row in dp:
        #     print(row)
        # print(dprow)
        # print(dpcol)

ans = max(*dprow, dp[a[-1]][a[-1]] + 1)

print(ans+margin)

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    dp = defaultdict(int)
    dp[(A[0], A[1])] = 0
    # print(dp)

    for i in range(n - 1):
        ndp = defaultdict(int)
        for key, val in dp.items():
            B = list(key)
            for j in range(3 * i + 2, 3 * i + 5):
                B.append(A[j])
            B.sort()
            for s in range(5):
                for t in range(s + 1, 5):
                    C = B[:]
                    C.remove(B[s])
                    C.remove(B[t])
                    if len(set(C)) == 1:
                        ndp[B[s], B[t]] = max(ndp[B[s], B[t]], val + 1)
                    else:
                        ndp[B[s], B[t]] = max(ndp[B[s], B[t]], val)

        dp = ndp

    ans = 0
    for key, val in dp.items():
        if key[0] == key[-1] == A[-1]:
            val += 1
        ans = max(ans, val)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10]*n for _ in range(n)]
mx = [-10]*(n+1)
nmx = [-10]*(n+1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = dp[b][a] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if val > dp[i][j]:
        dp[i][j] = dp[j][i] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n-1):
    abc = aa[i*3+2:i*3+5]
    # print(abc)
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # b==cのときa==bになるようにする
    if b == c: a, c = c, a
    # ペアがある場合
    if a == b:
        vc = dp[c][c]
        for x, v in enumerate(dp[a][:]): chmax(c, x, v+1)
        chmax(a, c, max(mx[n], dp[a][a]+1))
        chmax(a, a, max(mx[n], vc+1))
        for x in range(n): chmax(a, x, mx[x])
        for x in range(n): chmax(c, x, mx[x])
    # 3枚とも異なる場合
    else:
        # a,b,cから2枚残す場合
        chmax(b, c, max(dp[a][a]+1, mx[n]))
        chmax(a, c, max(dp[b][b]+1, mx[n]))
        chmax(a, b, max(dp[c][c]+1, mx[n]))
        # a,b,cから1枚残す場合
        for x in range(n):
            chmax(a, x, mx[x])
            chmax(b, x, mx[x])
            chmax(c, x, mx[x])

    for x in range(n+1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)
    # print()

a = aa[-1]
ans = max(mx[n], dp[a][a]+1)+base
print(ans)

Submission status: Accepted

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

N=int(input())
A=list(map(int,input().split()))

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)
SCMAX=0

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #for d in DP:
    #    print(*d)
    #print()
    #print(x,y,z)
    #print()

    NLIST=[]
    SCMAX2=0

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)
    
    if x==y:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,z,max(DP[i][z],DP[i][x]+1)))
                #DP[i][z]=DP[z][i]=max(DP[i][z],DP[i][x]+1)
         
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if DP[i][y]!=-1:
                NLIST.append((i,x,max(DP[i][x],DP[i][y]+1)))
                #DP[i][x]=DP[x][i]=max(DP[i][x],DP[i][y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,y,max(DP[i][y],DP[i][x]+1)))
                #DP[i][y]=DP[y][i]=max(DP[i][y],DP[i][x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    for i,j,sc in NLIST:
        DP[i][j]=DP[j][i]=max(DP[i][j],sc)
        SCMAX2=max(SCMAX,DP[i][j])

    #for d in DP:
    #    print(*d)
    #print()

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],MAXDP[i])
        DP[i][y]=DP[y][i]=max(DP[i][y],MAXDP[i])
        DP[i][z]=DP[z][i]=max(DP[i][z],MAXDP[i])
        SCMAX2=max(SCMAX2,DP[i][x],DP[i][y],DP[i][z])
                   
        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])
        NMAXDP[x]=max(NMAXDP[x],DP[i][x])
        NMAXDP[y]=max(NMAXDP[y],DP[i][y])
        NMAXDP[z]=max(NMAXDP[z],DP[i][z])

    DP[x][y]=DP[y][x]=max(SCMAX,xy)
    DP[y][z]=DP[z][y]=max(SCMAX,yz)
    DP[z][x]=DP[x][z]=max(SCMAX,zx)
    SCMAX2=max(SCMAX2,DP[x][y],DP[y][z],DP[z][x])

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])
    SCMAX=SCMAX2

#for d in DP:
#    print(*d)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Submission status: Accepted

Solution code:
def insertR(a, b):
  if a not in R: R[a] = {}
  if b not in R[a]: R[a][b] = 0

N = int(input())
A = list(map(int, input().split()))

if N == 1:
  print(1)
  exit()

DP = [[-1] * (N + 1) for _ in range(N + 1)]
D = [-1] * (N + 1)
R = {}
for i in range(5):
  a = A[i]
  if a in R:
    R[a] += 1
  else:
    R[a] = 1

Flag = 0
for i in R.keys():
  if R[i] >= 3:
    Flag = 1
    R[i] -= 3

L = []
for i in R.keys():
  if R[i] == 2:
    L.append(i)
    DP[i][i] = Flag
    D[i] = Flag
  elif R[i] == 1:
    L.append(i)
    D[i] = Flag

for i in range(len(L) - 1):
  for j in range(i + 1, len(L)):
    DP[L[i]][L[j]] = Flag

common = 0
for i in range(5, N * 3 - 3, 3):
  L = []
  for j in range(i, i + 3):
    for k in range(len(L)):
      if L[k][1] == A[j]:
        L[k][0] += 1
        break
    else :
      L.append([1, A[j]])
  L.sort()
  R = {}
  # 3
  if len(L) == 1:
    common += 1
  # 1:2
  elif len(L) == 2:
    a = L[0][1]
    b = L[1][1]
    # 1個のほうを揃える場合
    if DP[a][a] != -1:
      insertR(b, b)
      R[b][b] = max([R[b][b], DP[b][b], DP[a][a] + 1])
    # 2個のほうを揃える場合
    for j in range(N + 1):
      n = max(DP[b][j], DP[j][b])
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max([R[a][j], DP[a][j], n + 1])
    # 揃えない場合
    for j in range(N + 1):
      n = D[j]
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max(R[a][j], n)
      insertR(b, j)
      R[b][j] = max(R[b][j], n)
    n = max(D)
    insertR(a, b)
    R[a][b] = max(R[a][b], n)
    insertR(b, b)
    R[b][b] = max(R[b][b], n)
  # 1:1:1
  elif len(L) == 3:
    a = L[0][1]
    b = L[1][1]
    c = L[2][1]
    insertR(b, c)
    insertR(a, c)
    insertR(a, b)
    #揃える場合
    if DP[a][a] != -1:  
      R[b][c] = max(R[b][c], DP[a][a] + 1)
    if DP[b][b] != -1:      
      R[a][c] = max(R[a][c], DP[b][b] + 1)
    if DP[c][c] != -1:
      R[a][b] = max(R[a][b], DP[c][c] + 1)
    #揃えない場合
    for j in range(N + 1):
      n = D[j]
      if n == -1: continue
      insertR(a, j)
      R[a][j] = max(R[a][j], n)
      insertR(b, j)
      R[b][j] = max(R[b][j], n)
      insertR(c, j)
      R[c][j] = max(R[c][j], n)
    n = max(D)
    R[a][b] = max(R[a][b], n)
    R[b][c] = max(R[b][c], n)
    R[a][c] = max(R[a][c], n)

  for k in R.keys():
    for kk in R[k].keys():
      n = R[k][kk]
      DP[k][kk] = max(DP[k][kk], n)
      DP[kk][k] = max(DP[kk][k], n)
      D[k] = max(D[k], n)
      D[kk] = max(D[kk], n)

a = A[-1]
if DP[a][a] != -1:
  DP[a][a] += 1

ans = 0
for i in DP:
  for j in i:
    ans = max(ans, j)

ans += common

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def upd(a, b, v):
    global N
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[N][a] = max(dp[N][a], v)
    dp[N][b] = max(dp[N][b], v)
    dp[a][N] = max(dp[a][N], v)
    dp[b][N] = max(dp[b][N], v)
    dp[N][N] = max(dp[N][N], v)


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

INF = 1 << 32
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
upd(A[0], A[1], 0)
base = 0
q = deque()

for i in range(2, 3 * N - 1, 3):
    x, y, z = A[i], A[i + 1], A[i + 2]
    if x == y == z:  # x, y, z 3文字すべて等しいとき
        base += 1
    else:
        for _ in range(3):
            # a, b, x, y, z のうち, b, y, z を消すとき
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            # a, b, x, y, z のうち, a, b, z を消すとき
            v = max(dp[z][z] + 1, dp[N][N])
            q.append((x, y, v))
            # x, y, z をローテート
            x, y, z = z, x, y
        while q:
            a, b, v = q.popleft()
            upd(a, b, v)

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)