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: Accepted

Solution code:
n = int(input())
a = [*map(int, input().split())]
for i in range(n * 3):
    a[i] -= 1

INF = 1<<30
dp = [[-INF] * n for i in range(n)]
mx = [-INF] * n
mx_all = -INF
add_all = 0

dp[a[0]][a[1]] = dp[a[1]][a[0]] = 0
mx[a[0]] = mx[a[1]] = 0
mx_all = 0

for i in range(n - 1):
    x, y, z = sorted(a[i * 3 + 2 : i * 3 + 5])
    update = []
    # パターン1
    if x == y == z:
        add_all += 1
        continue
    # パターン2
    if x == y:
        for j in range(n):
            update.append((j, z, dp[j][x] + 1))
    if y == z:
        for j in range(n):
            update.append((j, x, dp[j][y] + 1))
    # パターン3
    update.append((y, z, dp[x][x] + 1))
    update.append((x, z, dp[y][y] + 1))
    update.append((x, y, dp[z][z] + 1))
    # パターン2-2
    for j in range(n):
        update.append((j, x, mx[j]))
        update.append((j, y, mx[j]))
        update.append((j, z, mx[j]))
    # パターン3-2
    update.append((y, z, mx_all))
    update.append((x, z, mx_all))
    update.append((x, y, mx_all))
    # in-place にするために更新を遅延させる
    for j, k, val in update:
        if dp[j][k] < val:
            dp[j][k] = dp[k][j] = val
        if mx[j] < val:
            mx[j] = val
        if mx[k] < val:
            mx[k] = val
        if mx_all < val:
            mx_all = val

# 最後の 1 回
if mx_all < dp[a[-1]][a[-1]] + 1:
    mx_all = dp[a[-1]][a[-1]] + 1
print(mx_all + add_all)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    a = [int(i)-1 for i in ipt().split()]
    dp = [[-10000]*n for i in range(n)]
    add = 0
    ma = 0
    manm = [-10000]*n
    manm[a[0]] = 0
    manm[a[1]] = 0

    dp[a[0]][a[1]] = 0
    for k in range(3,3*n,3):
        a0 = a[k-1]
        a1 = a[k]
        a2 = a[k+1]

        if a0 == a1 == a2:
            add += 1

        elif a0 != a1 != a2 != a0:
            pdp0 = dp[a0][a0]*1
            pdp1 = dp[a1][a1]*1
            pdp2 = dp[a2][a2]*1
            dp0 = dp[a0]
            dp1 = dp[a1]
            dp2 = dp[a2]

            #[a0][x],[a1][x],[a2][x]を更新
            for i in range(n):
                dp0[i] = manm[i]
                dp1[i] = manm[i]
                dp2[i] = manm[i]

            #[a1][a2]を更新
            if ma < pdp0+1:
                dp1[a2] = pdp0+1
            else:
                dp1[a2] = ma
            #[a0][a2]を更新
            if ma < pdp1+1:
                dp0[a2] = pdp1+1
            else:
                dp0[a2] = ma
            #[a0][a1]を更新
            if ma < pdp2+1:
                dp0[a1] = pdp2+1
            else:
                dp0[a1] = ma

            #manm,maの更新
            manm[a0] = max(dp0)
            manm[a1] = max(dp1)
            manm[a2] = max(dp2)
            if manm[a2] < dp1[a2]:
                manm[a2] = dp1[a2]
            if manm[a2] < dp0[a2]:
                manm[a2] = dp0[a2]
            if manm[a1] < dp0[a1]:
                manm[a1] = dp0[a1]
            ma = max(manm)

        else:
            if a0 == a1:
                p = a0
                q = a2
            elif a1 == a2:
                p = a1
                q = a0
            else:
                p = a2
                q = a1
            pdpp = dp[p][p]*1
            pdpq = dp[q][q]*1
            dpp = dp[p]
            dpq = dp[q]

            do = []
            dpip = [dp[i][p] for i in range(n)]
            #[q][x]を更新
            for i in range(n):
#                print("A",i,manm[i],dpp[i],dpip[i])
                if manm[i] >= dpp[i]+1 and manm[i] >= dpip[i]+1:
                    dpq[i] = manm[i]
                else:
                    if dpp[i] > dpip[i]:
                        dpq[i] = dpp[i]+1
                    else:
                        dpq[i] = dpip[i]+1
                do.append((q,dpq[i]))
                do.append((i,dpq[i]))
            #[p][x]を更新
            for i in range(n):
                if manm[i] > dpp[i]:
                    dpp[i] = manm[i]
                    do.append((p,manm[i]))
            #[p][p]を更新
            if ma > pdpq+1:
                dpp[p] = ma
            else:
                dpp[p] = pdpq+1
            do.append((p,dpp[p]))
            #[p][q]を更新
            if ma > pdpp+1:
                dpp[q] = ma
            else:
                dpp[q] = pdpp+1
            do.append((p,dpp[q]))
            do.append((q,dpp[q]))

            #manm,maの更新
            for i,j in do:
                if manm[i] < j:
                    manm[i] = j
            ma = max(manm)

    dp[a[-1]][a[-1]] += 1

    ma = 0
    for i in dp:
        for j in i:
            if j > ma:
                ma = j

    print(ma+add)



    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    ans = [[-N] * (N+1) for _ in range(N+1)]
    a0, a1 = A[:2]
    ans[a0][a1] = 0
    ans[a1][a0] = 0
    ma = [-N] * (N+1)
    ma[a0] = 0
    ma[a1] = 0
    mama = 0
    add = 0
    for i in range(N-1):
        a, b, c = A[i*3+2:i*3+5]
        if a == b == c:
            add += 1
            continue
        Q = []
        for _ in range(3):
            a, b, c = b, c, a
            # choose 2
            Q.append((a, b, max(mama, ans[c][c] + 1)))
            # choose 1
            for j in range(1, N+1):
                val = ma[j]
                if b == c:
                    val = max(val, ans[b][j] + 1)
                Q.append((a, j, val))
        for i, j, val in Q:
            ans[i][j] = max(ans[i][j], val)
            ans[j][i] = max(ans[j][i], val)
            ma[i] = max(ma[i], val)
            ma[j] = max(ma[j], val)
            mama = max(mama, val)
    ANS = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            if i == j == A[-1]:
                ANS = max(ANS, ans[i][j] + 1)
            else:
                ANS = max(ANS, ans[i][j])
    print(ANS + add)


if __name__ == '__main__':
    main()

Submission status: Accepted

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
D[A[0]][A[1]]=0
D[A[1]][A[0]]=0
r[A[0]]=0
r[A[1]]=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,D[Z][Z]+1))
    C.append((Y,Z,D[X][X]+1))
    C.append((X,Z,D[Y][Y]+1))
    C.append((X,Y,M))
    C.append((X,Z,M))
    C.append((Y,Z,M))
    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: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
INF = 2*N
DP = [[-INF]*(N+1) for _ in range(N+1)]
M = 0
rowM = [-INF]*(N+1)

def chmax(i,j,k):
    DP[i][j] = max(k,DP[i][j])
    DP[j][i] = max(k,DP[j][i])
    rowM[i] = max(rowM[i],DP[i][j])
    rowM[j] = max(rowM[j],DP[i][j])
    global M
    M = max(M,k)

ans = 0
DP[A[0]][A[1]] = 0
DP[A[1]][A[0]] = 0
rowM[A[0]] = 0
rowM[A[1]] = 0
for i in range(N-1):
    new = A[3*i+2:3*i+5]
    change = []
    if len(set(new)) == 1:
        ans += 1
        continue
    if len(set(new)) == 2:
        for j in range(3):
            if new.count(new[j]) == 2:
                X = new[j]
            else:
                Y = new[j]
        for j in range(1,N+1):
            change.append((j,Y,DP[X][j]+1))
    X,Y,Z = new
    change.append((X,Y,DP[Z][Z]+1))
    change.append((Y,Z,DP[X][X]+1))
    change.append((X,Z,DP[Y][Y]+1))
    change.append((X,Y,M))
    change.append((X,Z,M))
    change.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            change.append((j,new[k],rowM[j]))
    for j,k,l in change:
        chmax(j,k,l)
M = max(M,DP[A[-1]][A[-1]]+1)
print(ans+M)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
N = len(A) // 3
A = A[:3*N]
#print(N, A)
A.append(0)
A.append(0)

ans = 0
def ind(a, b):
  t = sorted((a, b))
  return t[0] * (N+1) + t[1]
def inv(i):
  b = i % (N+1)
  a = i // (N + 1)
  return a, b

dp = [-1] * (N+1)**2
dp[ind(A[0],A[1])] = 0
current_max = 0
dp1 = [-1] * (N+1)
dp1[A[0]] = 0
dp1[A[1]] = 0

ans = 0
for i in range(0, N):
  a = A[2+3*i] 
  b = A[2+3*i+1]
  c = A[2+3*i+2]
  #print(a,b,c)
  if a == b == c:
    ans+=1
    continue
  dp_new = {}
  for x, y, z in [(a, b, c), (b, c, a), (c, a, b)]:
    # choose 1 (x), leave y, z
    i = ind(y, z)
    if i not in dp_new:
      dp_new[i] = 0
    dp_new[i] = max(dp_new[i], current_max)
    if dp[ind(x, x)] >= 0:
      dp_new[i] = max(dp_new[i], dp[ind(x, x)] + 1)
    
    # choose 2 (x, y), leave t, z
    for t in range(1, N+1):
      i = ind(t,z)
      # Not making three
      if dp1[t] >= 0:
        if i not in dp_new:
          dp_new[i]=0
        dp_new[i] = max(dp_new[i], dp1[t])
      # Making three (x==y)
      if x == y and dp[ind(t, x)] >= 0:
        if i not in dp_new:
          dp_new[i] = 0
        dp_new[i] = max(dp_new[i], dp[ind(t, x)] + 1)
        
  #print(a,b,c)
  #print({inv(i):v for i, v in dp_new.items() })
  for i, s in dp_new.items():
    dp[i] = max(dp[i], s)
    ta, tb = inv(i)
    dp1[ta] = max(dp1[ta], s)
    dp1[tb] = max(dp1[tb], s)
    current_max = max(current_max, s)

#print(doubles)
print(ans + max(dp1))

Submission status: Accepted

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 = [-10**10] * (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(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        X[a2] = [max(X[a2][j], MA[j]) for j in range(N+1)]
        MA = [max(m, x1, x2) for m, x1, x2 in zip(MA, X[a1], X[a2])]
        MA[a1] = max(MA[a1], max(X[a1]), X[a2][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(X[a][b], ma, X[c][c] + 1), max(X[a][c], ma, X[b][b] + 1), max(X[b][c], ma, X[a][a] + 1)
        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: Accepted

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 = [-10**10] * (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[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(ma, X[a2][a2], X[a1][a1] + 1)
        # X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        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(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        #
        X[a2] = [max(X[a2][j], MA[j]) for j in range(N+1)]
        MA = [max(MA[j], X[a1][j], X[a2][j]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]), X[a2][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(X[a][b], ma, X[c][c] + 1), max(X[a][c], ma, X[b][b] + 1), max(X[b][c], ma, X[a][a] + 1)
        X[a] = [max(X[a][j], MA[j]) for j in range(N+1)]
        X[b] = [max(X[b][j], MA[j]) for j in range(N+1)]
        X[c] = [max(X[c][j], MA[j]) for j in range(N+1)]
        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(MA[j], X[a][j], X[b][j], X[c][j]) for j in range(N+1)]
        ma = max(ma, MA[a], MA[b], MA[c])

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

Submission status: Accepted

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)
dprow[a[0]] = 0
dprow[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]))
        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])
            dprow[u[1]] = max(dprow[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: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(A):
    A = A - 1
    N = len(A) // 3
    A = np.append(A, (N, N))
    INF = 1 << 30
    dp = np.full((N + 1, N + 1), -INF, np.int64)
    a, b = A[:2]
    dp[a, b] = dp[b, a] = 0
    dp_max = np.full(N + 1, -INF, np.int64)
    dp_max[a] = dp_max[b] = 0
    add = 0
    update = np.empty((100 * N, 3), np.int64)
    for n in range(N):
        a, b, c = A[3 * n + 2:3 * n + 5]
        if a == b == c:
            add += 1
            continue
        p = 0
        # 色を持ちかえるだけの遷移
        for _ in range(3):
            a, b, c = b, c, a
            update[p], p = (a, b, dp_max.max()), p + 1
            for k in range(N):
                update[p], p = (k, a, dp_max[k]), p + 1

        for _ in range(3):
            a, b, c = b, c, a
            # 色 a をそろえる遷移
            if a == b:
                for k in range(N):
                    # もともと a, k をもっている
                    update[p], p = (c, k, dp[a, k] + 1), p + 1
            # もともと a, a, をもっている
            update[p], p = (b, c, dp[a, a] + 1), p + 1
        for i in range(p):
            a, b, x = update[i]
            dp[a, b] = dp[b, a] = max(dp[a, b], x)
            dp_max[a] = max(dp_max[a], x)
            dp_max[b] = max(dp_max[b], x)
    return dp_max.max() + add

A = np.array(read().split(), np.int64)[1:]

print(main(A))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
from functools import lru_cache
from itertools import combinations
setrecursionlimit(2500)

def solve():
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    @lru_cache(None)
    def dp(a, b, i):
        if i == 3 * N - 1:
            return 1 if a == b == A[i] else 0

        av = [a, b, A[i], A[i + 1], A[i + 2]]
        av.sort()
        
        if av[0] == av[1] == av[2]:
            return 1 + dp(av[3], av[4], i + 3)
        elif av[2] == av[3] == av[4]:
            return 1 + dp(av[0], av[1], i + 3)

        ans = 0
        for com in combinations(range(5), 3):
            left = [av[i] for i in range(5) if not i in com]
            ans = max(ans, dp(left[0], left[1], i + 3))
        return ans  
    return dp(A[0], A[1], 2)


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from itertools import combinations

def solve():
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    @lru_cache(None)
    def dp(a, b, i):
        if i == 3 * N - 1:
            return 1 if a == b == A[i] else 0

        av = [a, b, A[i], A[i + 1], A[i + 2]]
        av.sort()
        
        if av[0] == av[1] == av[2]:
            return 1 + dp(av[3], av[4], i + 3)
        elif av[2] == av[3] == av[4]:
            return 1 + dp(av[0], av[1], i + 3)

        ans = 0
        for com in combinations(range(5), 3):
            left = [av[i] for i in range(5) if not i in com]
            ans = max(ans, dp(left[0], left[1], i + 3))
        return ans  
    return dp(A[0], A[1], 2)


if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
import copy
import itertools
n = int(input())
a = list(map(int,input().split()))
dp1 = [[0]*(n+1) for i in range(n+1)]
f = copy.deepcopy(dp1)
for k in list(itertools.permutations(a[0:5])):
  x = k[2]==k[3] and k[2]==k[4]
  dp1[k[0]][k[1]] = int(x)
  f[k[0]][k[1]] = 1
dp2 = copy.deepcopy(dp1)
x = 0
for i in range(1,n-1):
  p,q,r = sorted(a[(3*i+2):(3*i+5)])
  if p==r:
    x += 1
  elif p==q:
    for j in range(n):
      if f[j+1][p] == 1:
        dp2[j+1][r] = dp1[j+1][p] + 1
        dp2[r][j+1] = dp1[j+1][p] + 1
        f[j+1][r],dp2[r][j+1] = 1,1
      if f[r][r] == 1:
        dp2[p][p] = dp1[r][r] + 1
        f[p][p] = 1
  elif q==r:
    for j in range(n):
      if f[j+1][q] == 1:
        dp2[j+1][p] = dp1[j+1][q] + 1
        dp2[p][j+1] = dp1[j+1][q] + 1
        f[j+1][p],dp2[p][j+1] = 1,1
      if f[p][p] == 1:
        dp2[q][q] = dp1[p][p] + 1
        f[q][q] = 1
  else:
    if f[r][r] == 1:
      dp2[p][q] = dp1[r][r] + 1
      f[p][q] = 1
    if f[p][p] == 1:
      dp2[q][r] = dp1[p][p] + 1
      f[q][r] = 1
    if f[p][p] == 1:
      dp2[q][r] = dp1[p][p] + 1
      f[q][r] = 1
  dp1 = copy.deepcopy(dp2)
if f[a[-1]][a[-1]] == 1:
  dp1[a[-1]][a[-1]] += 1
print(x+max(sum(dp1,[])))

Submission status: Runtime Error

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] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = 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]
    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:
        # 得点する
        cc = dp[c][c]
        for x in range(a): chmax(c, x, dp[x][a]+1)
        for x in range(a, n): chmax(c, x, dp[a][x]+1)
        chmax(a, a, cc+1)
        # 得点しない
        chmax(a, a, mx[n])
        chmax(a, c, mx[n])
        for x in range(n): chmax(a, x, mx[x])
        for x in range(n): chmax(c, x, mx[x])
    # 3枚とも異なる場合
    else:
        aa=dp[a][a]
        bb=dp[b][b]
        cc=dp[c][c]
        # 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, max(mx[x],bb+1,cc+1))
            chmax(b, x, max(mx[x],aa+1,cc+1))
            chmax(c, x, max(mx[x],bb+1,aa+1))

    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: Runtime Error

Solution code:
import numpy as np
import itertools
import copy

def f(l):
    lret=[]
    l.sort()
    checked=set()
    for a,b in itertools.combinations(l,2):
        #print(a,b)
        #if a>b:
        #    a,b=b,a
        if (a,b) in checked:
            continue
        checked.add((a,b))

        ltmp=copy.copy(l)
        ltmp.remove(a)
        ltmp.remove(b)
        if len(set(ltmp))==1:
            bret=True
        else:
            bret=False
        lret.append( ((a,b),bret) )
    return lret


N=int(input())
As=list(map(lambda c:int(c)-1,input().split()))
As=As+[0,0]

dp=np.full((N+1,2000,2000),-1,dtype=np.int16)

# initialize
a,b=As[:2]
if a>b:
    a,b=b,a
dp[0][a][b]=0

# デーブル計算
for i in range(N):
    # As[i*3:i*3+5]を並べ替えて3つ取り除く
    # <->
    # As[i*3+2:i*3+2+3]を追加
    Aadd=As[i*3+2:i*3+2+3]
    for a in range(2000):
        for b in range(a,2000):
            if dp[i,a,b]==-1:
                continue
            # ((an,bn),same(T:+1,F:+0) )
            l=f(Aadd+[a,b])

            #print(i)
            #print(a,b,l)

            for pair,same in l:
                an,bn=pair
                mx_cand=dp[i,a,b]+1 if same else dp[i,a,b]
                if mx_cand > dp[i+1,an,bn]:
                    dp[i+1,an,bn]=mx_cand

#print(dp[:,:3,:3])
print(dp[N,0,0])

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
import copy

def f(l):
    lret=[]
    l.sort()
    checked=set()
    for a,b in itertools.combinations(l,2):
        #print(a,b)
        #if a>b:
        #    a,b=b,a
        if (a,b) in checked:
            continue
        checked.add((a,b))

        ltmp=copy.copy(l)
        ltmp.remove(a)
        ltmp.remove(b)
        if len(set(ltmp))==1:
            bret=True
        else:
            bret=False
        lret.append( ((a,b),bret) )
    return lret


N=int(input())
As=list(map(lambda c:int(c)-1,input().split()))
As=As+[0,0]

dp=np.full((N+1,2000,2000),-1,dtype=np.int64)

# initialize
a,b=As[:2]
if a>b:
    a,b=b,a
dp[0][a][b]=0

# デーブル計算
for i in range(N):
    # As[i*3:i*3+5]を並べ替えて3つ取り除く
    # <->
    # As[i*3+2:i*3+2+3]を追加
    Aadd=As[i*3+2:i*3+2+3]
    for a in range(2000):
        for b in range(a,2000):
            if dp[i,a,b]==-1:
                continue
            # ((an,bn),same(T:+1,F:+0) )
            l=f(Aadd+[a,b])

            #print(i)
            #print(a,b,l)

            for pair,same in l:
                an,bn=pair
                mx_cand=dp[i,a,b]+1 if same else dp[i,a,b]
                if mx_cand > dp[i+1,an,bn]:
                    dp[i+1,an,bn]=mx_cand

#print(dp[:,:3,:3])
print(dp[N,0,0])

Submission status: Runtime Error

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

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)
  # 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: Runtime Error

Solution code:
N = input()
i_N = int(N)
card_num = input().split()
list_num = [str(i+1) for i in range(i_N)]
point = 0
how_num = {}

def a(card_num,point):
  read_card = card_num[:5]
  another_card = card_num[5:]
  for i in list_num:
    if read_card.count(i) >= 3:
      pop_list = [str(i) for j in range(3)]
      point += 1
  if len(pop_list) == 3:
    for i in pop_list:
      read_card.remove(i)
  new_list = read_card + another_card
  if len(new_list) < 3:
    print(point)
  else:
    a(new_list,point)
a(card_num,point)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))

dp = [[-2]*(n+1) for i in range(n+1)]
low = [-2]*(n+1)
col = [-2]*(n+1)
m = 0
dp[A[0]][A[1]] = 0
low[A[0]] = 0
col[A[1]] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    if a==b or b==c or c==a:
        if b==c:
            a,b,c = b,c,a
        elif c==a:
            a,b,c = a,c,b
        v = max(m,dp[c][c]+1)
        q.append((3,a,a,v))
        q.append((0,a,v))
        q.append((1,a,v))
        v1 = -2
        for i in range(1,n+1):
            if max(low[i],dp[i][a]+1)>= 0:
                dp[i][c] = max(dp[i][c],low[i],dp[i][a]+1)
                v1 = max(v1,dp[i][c])
                if dp[i][c] > low[i]:
                    q.append((0,i,dp[i][c]))
        q.append((1,c,v1))
        v2 = -2
        for i in range(1,n+1):
            if max(col[i],dp[a][i]+1)>= 0:
                dp[c][i] = max(dp[c][i],col[i],dp[a][i]+1)
                v2 = max(v2,dp[c][i])
                if dp[c][i] > col[i]:
                    q.append((1,i,dp[c][i]))
        q.append((0,c,v2))
        q.append((2,0,max(v,v1,v2)))
    
    else:
        for j in range(3):
            v = max(m,dp[c][c]+1)
            q.append((3,a,b,v))
            q.append((0,a,v))
            q.append((1,a,v))
            
            for i in range(1,n+1):
                if low[i]>= 0:
                    dp[i][c] = low[i]
        
            for i in range(1,n+1):
                if col[i]>= 0:
                    dp[c][i] = col[i]
   
            q.append((2,0,max(v,v1,v2)))

            a,b,c = b,c,a
    for l in q:
        if l[0] == 0:
            low[l[1]] = max(low[l[1]],l[2])
        elif l[0] == 1:
            col[l[1]] = max(col[l[1]],l[2])
        elif l[0] == 2:
            m = max(m,l[2])
        else:
            dp[l[1]][l[2]] = max(dp[l[1]][l[2]],l[3])
        
print(max(m,dp[A[-1]][A[-1]]+1)+base)