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

Solution code:
N = int(input())
cards = list(map(int,input().split()))
points = 0
for _ in range(N-1):
        five_cards = cards[:5]
        five_cards = sorted(five_cards,key=five_cards.count,reverse=True)
        if five_cards.pop(0) == five_cards.pop(0) == five_cards.pop(0):
            points += 1
        cards = five_cards+cards[5:]
if len(set(cards))==1:
        points += 1
print(points)

Submission status: Wrong Answer

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 = 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), p + 1
        for _ in range(3):
            a, b, c = b, c, a
            # 色 a をそろえる遷移
            for k in range(N):
                # もともと a, k をもっている
                cols = np.array([a, b, c, a, k])
                cols = cols[cols != a]
                if len(cols) >= 3:
                    continue
                if len(cols) == 1:
                    cols = np.append(cols, a)
                u, v = cols
                update[p], p = (u, v, dp[a, k] + 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 = max(dp_max, x)
    return dp_max + add

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

print(main(A))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<30)

from functools import lru_cache
from itertools import permutations

N = int(input())

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

@lru_cache(maxsize=None)
def f(a, b, i):
	if i == 3*N-1:
		return 1 if a == b == A[i] else 0

	best = 0
	for perm in permutations([a, b] + A[i:i+3]):
		best = max(best, (1 if perm[0] == perm[1] == perm[2] else 0) + f(*perm[3:], i+3))
	return best


print(f(A[0], A[1], 2))

Submission status: Time Limit Exceeded

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((2,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]
    dp[(i+1)%2].fill(-1)
    for a in range(2000):
        for b in range(a,2000):
            if dp[i%2,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%2,a,b]+1 if same else dp[i%2,a,b]
                if mx_cand > dp[(i+1)%2,an,bn]:
                    dp[(i+1)%2,an,bn]=mx_cand

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

Submission status: Time Limit Exceeded

Solution code:
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 = [None] * (3 * N + 3)

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:
        cur = 0
        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[cur] = (k, x, v)
                cur += 1
            # a, b, x, y, z のうち, a, b, z を消すとき
            v = max(dp[z][z] + 1, dp[N][N])
            q[cur] = (x, y, v)
            cur += 1
            # x, y, z をローテート
            x, y, z = z, x, y
        for j in range(cur):
            upd(*q[j])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def upd(dp, a, b, v):
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[-1][a] = max(dp[-1][a], v)
    dp[-1][b] = max(dp[-1][b], v)
    dp[a][-1] = max(dp[a][-1], v)
    dp[b][-1] = max(dp[b][-1], v)
    dp[-1][-1] = max(dp[-1][-1], v)


def main():
    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(dp, A[0], A[1], 0)
    base = 0

    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:
            q = deque()
            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(dp, a, b, v)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def upd(a, b, v):
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[-1][a] = max(dp[-1][a], v)
    dp[-1][b] = max(dp[-1][b], v)
    dp[a][-1] = max(dp[a][-1], v)
    dp[b][-1] = max(dp[b][-1], v)
    dp[-1][-1] = max(dp[-1][-1], 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

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:
        q = deque()
        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)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input()); n3 = n*3; INF = float("inf")
A = list(map(int,input().split()))
A = [A[i]-1 for i in range(n3)]
m = n+1 #最後は?用
dp = [[-INF]*m for _ in range(m)]
def upd(i,j,x):
  dp[i][j] = max(dp[i][j],x)
  dp[j][i] = max(dp[j][i],x)
  dp[i][n] = max(dp[i][n],x)
  #dp[n][i] = max(dp[n][i],x)
  dp[j][n] = max(dp[j][n],x)
  #dp[n][j] = max(dp[n][j],x)
  dp[n][n] = max(dp[n][n],x)
upd(A[0],A[1],0)
base = 0
for ai in range(2,n3-1,3):
  x = A[ai]; y = A[ai+1]; z = A[ai+2]
  if x == y and y == z:
    base +=1
    continue
  q = []
  for ri in range(3):
    for a in range(m):
      now = dp[a][n]
      if y == z:
        now = max(now,dp[a][y]+1)
      q.append((a,x,now))
        
    now = max(dp[n][n],dp[z][z]+1)
    q.append((x,y,now))
    x,y = y,x; y,z = z,y
  
  for t in q:
    i,j,x = t
    upd(i,j,x)

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

Submission status: Time Limit Exceeded

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

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
col = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
col[a] = 0
low[b]
col[b] = 0
base = 0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    A = list(map(int,input().split()))

    dp = [[-float("INF")]*(n+1) for i in range(n+1)]
    low = [-float("INF")]*(n+1)
    col = [-float("INF")]*(n+1)
    m = 0
    a,b = A[:2]
    dp[a][b] = 0
    dp[b][a] = 0
    low[a] = 0
    col[a] = 0
    low[b]
    col[b] = 0
    base = 0

    for _ in range(1,n):
        a,b,c = A[3*_-1:3*_+2]
        q = []
        if a==b==c:
            base += 1
            continue
        for j in range(3):
            q.append((a,b,max(m,dp[c][c]+1)))
            for i in range(1,n+1):
                q.append((a,i,low[i]))
            if a==b:
                for i in range(1,n+1):
                    q.append((c,i,dp[a][i]+1))
            a,b,c = b,c,a
        for a,b,v in q:
            dp[a][b] = max(dp[a][b],v)
            dp[b][a] = max(dp[b][a],v)
            low[a] = max(low[a],v)  
            low[b] = max(low[b],v)  
            col[a] = max(col[a],v)  
            col[b] = max(col[b],v) 
            m = max(m,v)     
    print(max(m,dp[A[-1]][A[-1]]+1)+base)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
col = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
col[a] = 0
low[b]
col[b] = 0
base = 0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input()); n3 = n*3; INF = float("inf")
A = list(map(int,input().split()))
A = [A[i]-1 for i in range(n3)]
m = n+1 #最後は?用
dp = [[-INF]*m for _ in range(m)]
def upd(i,j,x):
  dp[i][j] = max(dp[i][j],x)
  dp[j][i] = max(dp[j][i],x)
  dp[i][n] = max(dp[i][n],x)
  dp[n][i] = max(dp[n][i],x)
  dp[j][n] = max(dp[j][n],x)
  dp[n][j] = max(dp[n][j],x)
  dp[n][n] = max(dp[n][n],x)
upd(A[0],A[1],0)
base = 0
for ai in range(2,n3-1,3):
  x = A[ai]; y = A[ai+1]; z = A[ai+2]
  if x == y and y == z:
    base +=1
    continue
  q = []
  for ri in range(3):
    for a in range(m):
      now = dp[a][n]
      if y == z:
        now = max(now,dp[a][y]+1)
      q.append((a,x,now))
        
    now = max(dp[n][n],dp[z][z]+1)
    q.append((x,y,now))
    x,y = y,x; y,z = z,y
  
  for t in q:
    i,j,x = t
    upd(i,j,x)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input()); n3 = n*3; INF = float("inf")
A = list(map(int,input().split()))
A = [A[i]-1 for i in range(n3)]
m = n+1 #最後は?用
dp = [[-INF]*m for _ in range(m)]
def upd(i,j,x):
  dp[i][j] = max(dp[i][j],x)
  dp[j][i] = max(dp[j][i],x)
  dp[i][n] = max(dp[i][n],x)
  dp[n][i] = max(dp[n][i],x)
  dp[j][n] = max(dp[j][n],x)
  dp[n][j] = max(dp[n][j],x)
  dp[n][n] = max(dp[n][n],x)
upd(A[0],A[1],0)
base = 0
for ai in range(2,n3-1,3):
  x = A[ai]; y = A[ai+1]; z = A[ai+2]
  if x == y and y == z:
    base +=1
    continue
  q = []
  for ri in range(3):
    for a in range(m):
      now = dp[a][n]
      if y == z:
        now = max(now,dp[a][y]+1)
      q.append((a,x,now))
        
    now = max(dp[n][n],dp[z][z]+1)
    q.append((x,y,now))
    x,y = y,x; y,z = z,y
  
  for t in q:
    i,j,x = t
    upd(i,j,x)

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

Submission status: Time Limit Exceeded

Solution code:
from typing import List


class DP:
    N: int
    table: List[List[int]]
    max_all: int
    max_arr: List[int]
    inc: int

    def __init__(self, N: int, x: int, y: int):
        self.N = N
        self.table = [[-(1 << 28)] * (N + 1) for _ in range(N + 1)]
        self.table[x][y] = self.table[y][x] = 0
        self.max_all = 0
        self.max_arr = [-(1 << 28)] * (N + 1)
        self.max_arr[x] = self.max_arr[y] = 0
        self.inc = 0

    def update(self, p: int, q: int, r: int) -> None:
        if p == q == r:
            self.inc += 1
            return

        npqr = self._update_pqr(p, q, r)
        nqrp = self._update_pqr(q, r, p)
        nrpq = self._update_pqr(r, p, q)

        npq = self._update_pq(p, q)
        nqr = self._update_pq(q, r)
        nrp = self._update_pq(r, p)

        np = self._update_p(p)
        nq = self._update_p(q)
        nr = self._update_p(r)

        pq, qr, rp = None, None, None

        if p == q:
            pq = self._update_pair(p, r)

        if q == r:
            qr = self._update_pair(q, p)

        if r == p:
            rp = self._update_pair(r, q)

        self._update_maximum(q, r, npqr)
        self._update_maximum(r, p, nqrp)
        self._update_maximum(p, q, nrpq)

        self._update_maximum(p, q, npq)
        self._update_maximum(q, r, nqr)
        self._update_maximum(r, p, nrp)

        for k in range(self.N + 1):
            self._update_maximum(k, p, np[k])
            self._update_maximum(k, q, nq[k])
            self._update_maximum(k, r, nr[k])

        if pq:
            for k in range(self.N + 1):
                self._update_maximum(k, r, pq[k])

        if qr:
            for k in range(self.N + 1):
                self._update_maximum(k, p, qr[k])

        if rp:
            for k in range(self.N + 1):
                self._update_maximum(k, q, rp[k])


    def _update_maximum(self, x: int, y: int, v: int) -> None:
        self.table[x][y] = self.table[y][x] = max(self.table[x][y], v)
        self.max_all = max(self.max_all, v)
        self.max_arr[x] = max(self.max_arr[x], v)
        self.max_arr[y] = max(self.max_arr[y], v)

    def _update_pair(self, p: int, q: int) -> List[int]:
        return [max(self.table[k][q], self.table[k][p] + 1, self.table[p][k] + 1) for k in range(self.N + 1)]

    def _update_pqr(self, p: int, q: int, r: int) -> int:
        return max(self.table[q][r], self.table[p][p] + 1)

    def _update_pq(self, p: int, q: int) -> int:
        return max(self.table[p][q], self.max_all)

    def _update_p(self, p) -> List[int]:
        return [max(self.table[p][k], self.table[k][p], self.max_arr[k]) for k in range(self.N + 1)]

    def ans(self):
        return self.max_all + self.inc


N = int(input())
A = list(map(int, input().split())) + [0, 0]

dp = DP(N, A[0], A[1])

for i in range(N):
    Z = A[3 * i + 2: 3 * i + 5]
    dp.update(Z[0], Z[1], Z[2])
    # print("out", dp.table, dp.max_all, dp.max_arr)

print(dp.ans())

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()
def resolve():
    n = int(input())
    A = list(map(lambda x : int(x) - 1, input().split()))

    # n : wild card
    dp = [[-INF] * (n + 1) for _ in range(n + 1)]
    def update(i, j, v):
        dp[i][j] = max(dp[i][j], v)
        dp[j][i] = max(dp[j][i], v)
        dp[i][n] = max(dp[i][n], v)
        dp[n][i] = max(dp[n][i], v)
        dp[n][j] = max(dp[n][j], v)
        dp[j][n] = max(dp[j][n], v)
        dp[n][n] = max(dp[n][n], v)

    # initialize
    update(A[0], A[1], 0)

    # iterate
    base = 0
    for i in range(n - 1):
        x, y, z = A[3 * i + 2 : 3 * i + 5]
        if x == y == z:
            base += 1
            continue
        update_queue = []
        for _ in range(3):
            # 手持ちから1枚使う
            for a in range(n):
                update_queue.append((a, x, dp[a][n]))
                if y == z:
                    update_queue.append((a, x, dp[a][y] + 1))
            # 手持ちから0枚使う
            update_queue.append((x, y, dp[n][n]))
            update_queue.append((x, y, dp[z][z] + 1))
            x, y, z = y, z, x
        for i, j, v in update_queue:
            update(i, j, v)

    ans = max(dp[n][n], dp[A[-1]][A[-1]] + 1)
    ans += base
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def solve(n, aaa):
    dp = [[-1] * n for _ in range(n)]
    dp_max = [-1] * n
    ans = 0

    a0, a1 = sorted(aaa[:2])
    dp[a0][a1] = 0
    dp_max[a0] = 0
    dp_max[a1] = 0

    for k in range(n - 1):
        a0, a1, a2 = sorted(aaa[2 + 3 * k:5 + 3 * k])
        if a0 == a1 and a1 == a2:
            ans += 1
            continue

        dp_max_max = max(dp_max)
        update_tasks = []

        if a0 == a1 or a1 == a2:
            rev = a1 == a2
            if rev:
                a0, a2 = a2, a0

            for b in range(n):
                c, d = min(a0, b), max(a0, b)
                e, f = min(a2, b), max(a2, b)
                update_tasks.append((e, f, dp_max[b]))
                if dp[c][d] != -1:
                    update_tasks.append((e, f, dp[c][d] + 1))

            update_tasks.append((a0, a0, dp_max_max))
            if dp[a2][a2] != -1:
                update_tasks.append((a0, a0, dp[a2][a2] + 1))

            if rev:
                update_tasks.append((a2, a0, dp_max_max))
            else:
                update_tasks.append((a0, a2, dp_max_max))

        else:
            update_tasks.append((a0, a1, dp_max_max))
            update_tasks.append((a0, a2, dp_max_max))
            update_tasks.append((a1, a2, dp_max_max))
            if dp[a0][a0] != -1:
                update_tasks.append((a1, a2, dp[a0][a0] + 1))
            if dp[a1][a1] != -1:
                update_tasks.append((a0, a2, dp[a1][a1] + 1))
            if dp[a2][a2] != -1:
                update_tasks.append((a0, a1, dp[a2][a2] + 1))

            for b in range(n):
                b_max = dp_max[b]
                for a in (a0, a1, a2):
                    c, d = min(a, b), max(a, b)
                    update_tasks.append((c, d, b_max))

        for a, b, c in update_tasks:
            dp[a][b] = max(dp[a][b], c)
            dp_max[a] = max(dp_max[a], c)
            dp_max[b] = max(dp_max[b], c)

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

    return max(map(max, dp)) + ans


n = int(input())
aaa = [a - 1 for a in map(int, input().split())]
ans = solve(n, aaa)
print(ans)

Submission status: Time Limit Exceeded

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

if N==1:
    if A[0]==A[1]==A[2]:
        print(1)
    else:
        print(0)
    exit()

INF = float('inf')
ans = 0
dp = [[-INF]*(N+1) for _ in range(N+1)]
dp[A[0]][A[1]] = dp[A[1]][A[0]] = 0
maxdp = [max(row) for row in dp]

for i in range(N-1):
    a,b,c = A[i*3+2:i*3+5]
    if a==b==c:
        ans += 1
        continue
    update = []
    if a==b:
        for j in range(1,N+1):
            update.append((j,c, dp[j][a] + 1))
    elif b==c:
        for j in range(1,N+1):
            update.append((j,a, dp[j][b] + 1))
    elif c==a:
        for j in range(1,N+1):
            update.append((j,b, dp[j][c] + 1))
    update.append((a,b, dp[c][c] + 1))
    update.append((b,c, dp[a][a] + 1))
    update.append((c,a, dp[b][b] + 1))
    mx = max(maxdp)
    update.append((a,b, mx))
    update.append((b,c, mx))
    update.append((c,a, mx))
    for j in range(1,N+1):
        update.append((j,a, maxdp[j]))
        update.append((j,b, maxdp[j]))
        update.append((j,c, maxdp[j]))
    for l,m,n in update:
        dp[l][m] = dp[m][l] = max(dp[l][m], dp[m][l], n)
        maxdp[l] = max(maxdp[l], n)
        maxdp[m] = max(maxdp[m], n)

tmp = max(maxdp)
tmp = max(tmp, dp[A[-1]][A[-1]] + 1)
ans += tmp
print(ans)

Submission status: Time Limit Exceeded

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

if N==1:
    if A[0]==A[1]==A[2]:
        print(1)
    else:
        print(0)
    exit()

INF = float('inf')
ans = 0
dp = [[-INF]*(N+1) for _ in range(N+1)]
dp[A[0]][A[1]] = dp[A[1]][A[0]] = 0
maxdp = [max(row) for row in dp]

for i in range(N-1):
    a,b,c = A[i*3+2:i*3+5]
    if a==b==c:
        ans += 1
        continue
    update = []
    if a==b:
        for j in range(1,N+1):
            update.append((j,c, max(dp[a][j], dp[j][a]) + 1))
    elif b==c:
        for j in range(1,N+1):
            update.append((j,a, max(dp[b][j], dp[j][b]) + 1))
    elif c==a:
        for j in range(1,N+1):
            update.append((j,b, max(dp[c][j], dp[j][c]) + 1))
    update.append((a,b, dp[c][c] + 1))
    update.append((b,c, dp[a][a] + 1))
    update.append((c,a, dp[b][b] + 1))
    mx = max(maxdp)
    update.append((a,b, mx))
    update.append((b,c, mx))
    update.append((c,a, mx))
    for j in range(1,N+1):
        update.append((j,a, maxdp[j]))
        update.append((j,b, maxdp[j]))
        update.append((j,c, maxdp[j]))
    for l,m,n in update:
        dp[l][m] = dp[m][l] = max(dp[l][m], dp[m][l], n)
        maxdp[l] = max(maxdp[l], n)
        maxdp[m] = max(maxdp[m], n)

tmp = max(maxdp)
tmp = max(tmp, dp[A[-1]][A[-1]] + 1)
ans += tmp
print(ans)

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 i in range(N-1):

    cards = A[2+3*i:5+3*i]
    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):
            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):
            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:

"""

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:
        if nmax < tmp:
            nmax = tmp
        if dp[c1][c2] < tmp:
            dp[c1][c2] = tmp
        if dp[c2][c1] < tmp:
            dp[c2][c1] = tmp
        if maxin[c1] < tmp:
            maxin[c1] = tmp
        if maxin[c2] < tmp:
            maxin[c2] = tmp

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

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