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

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

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):
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            v = max(dp[z][z] + 1, dp[N][N])
            q.append((x, y, v))
            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: Accepted

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)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[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
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,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))
                m1 = max(m1,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)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Accepted

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)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[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
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,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))
                m1 = max(m1,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)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Accepted

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)
    m = 0
    a,b = A[:2]
    dp[a][b] = 0
    dp[b][a] = 0
    low[a] = 0
    low[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
        m1 = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
        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))
                    m1 = max(m1,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)      
        m = m1
    print(max(m,dp[A[-1]][A[-1]]+1)+base)

if __name__ == "__main__":
    main()

Submission status: Accepted

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)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[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
    m1 = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
    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))
                m1 = max(m1,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)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)

Submission status: Accepted

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 run():
    N, *A_ = map(int, read().split())
    dp = [[-INF] * (N+1) for _ in range(N+1)]
    dp_max = [-INF] * (N+1)
    a, b = A_[:2]
    dp[a][b] = dp[b][a] = dp_max[a] = dp_max[b] = 0

    triplets = 0
    chunks = []

    for i in range(N-1):
        x,y,z = A_[3*i+2 : 3*i+5]
        if x == y == z:
            triplets+=1
        else:
            chunks.append((x,y,z))

    for x,y,z in chunks:
        cache = []
        # transition : a = x = y
        if y == z:
            x,y,z = y,z,x
        elif z == x:
            x,y,z = z,x,y

        if x == y:
            for i in range(1, N+1):
                cache.append((z, i, dp[x][i] + 1))

        # trainsition : a = b = x
        cache.append((y, z, dp[x][x] + 1))
        cache.append((z, x, dp[y][y] + 1))
        cache.append((x, y, dp[z][z] + 1))

        # trainsition : only fill next
        MAX = max(dp_max)
        cache.append((x, y, MAX))
        cache.append((y, z, MAX))
        cache.append((z, x, MAX))
        for i in range(1, N+1):
            cache.append((i, x, dp_max[i]))
            cache.append((i, y, dp_max[i]))
            cache.append((i, z, dp_max[i]))

        # Update
        for a, b, value in cache:
            dp[a][b] = dp[b][a] = max(value, dp[a][b])
            dp_max[a] = max(dp_max[a], dp[a][b])
            dp_max[b] = max(dp_max[b], dp[a][b])

    a = A_[-1]
    dp[a][a] += 1
    dp_max[a] = max(dp[a][a], dp_max[a])

    print(max(dp_max) + triplets)
    #print(chunks)


if __name__ == "__main__":
    run()

Submission status: Accepted

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

N = int(input().strip())+2
A = list(map(int,input().split()))+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = [i-1 for i in sorted(A[:5])]

if a == b == c:
  dp[d][e] = dp[e][d] = dpmaxj[d] = dpmaxj[e] = dpmax = 1
elif b == c == d:
  dp[a][e] = dp[e][a] = dpmaxj[a] = dpmaxj[e] = dpmax = 1
elif c == d == e:
  dp[a][b] = dp[b][a] = dpmaxj[a] = dpmaxj[b] = dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      p,q = L[i],L[j]
      dp[p][q] = dp[q][p] = dpmaxj[p] = dpmaxj[q] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1); update(k,c)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1); update(c,k)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1); update(k,b)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1); update(b,k)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1); update(k,a)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1); update(a,k)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
  
  dp[b][c] = max(dp[b][c],dpd[a] + 1); update(b,c)
  dp[c][b] = max(dp[c][b],dpd[a] + 1); update(c,b)
  dp[a][c] = max(dp[a][c],dpd[b] + 1); update(a,c)
  dp[c][a] = max(dp[c][a],dpd[b] + 1); update(c,a)
  dp[a][b] = max(dp[a][b],dpd[c] + 1); update(a,b)
  dp[b][a] = max(dp[b][a],dpd[c] + 1); update(b,a)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax); update(a,b)
  dp[b][a] = max(0,dp[b][a],prevdpmax); update(b,a)
  dp[b][c] = max(0,dp[b][c],prevdpmax); update(b,c)
  dp[c][b] = max(0,dp[c][b],prevdpmax); update(c,b)
  dp[a][c] = max(0,dp[a][c],prevdpmax); update(a,c)
  dp[c][a] = max(0,dp[c][a],prevdpmax); update(c,a)

  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j]); update(j,a)
    dp[j][b] = max(dp[j][b],prevdpmaxj[j]); update(j,b)
    dp[j][c] = max(dp[j][c],prevdpmaxj[j]); update(j,c)
    dp[a][j] = max(dp[a][j],prevdpmaxj[j]); update(a,j)
    dp[b][j] = max(dp[b][j],prevdpmaxj[j]); update(b,j)
    dp[c][j] = max(dp[c][j],prevdpmaxj[j]); update(c,j)
    
print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Submission status: Accepted

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

N = int(input().strip())+2
A = list(map(int,input().split()))+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = [i-1 for i in sorted(A[:5])]

if a == b == c:
  dp[d][e] = dp[e][d] = dpmaxj[d] = dpmaxj[e] = dpmax = 1
elif b == c == d:
  dp[a][e] = dp[e][a] = dpmaxj[a] = dpmaxj[e] = dpmax = 1
elif c == d == e:
  dp[a][b] = dp[b][a] = dpmaxj[a] = dpmaxj[b] = dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      p,q = L[i],L[j]
      dp[p][q] = dp[q][p] = dpmaxj[p] = dpmaxj[q] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
      update(k,c)
      update(c,k)
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
      update(k,b)
      update(b,k)
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
      update(k,a)
      update(a,k)
  dp[b][c] = max(dp[b][c],dpd[a] + 1)
  dp[c][b] = max(dp[c][b],dpd[a] + 1)
  dp[a][c] = max(dp[a][c],dpd[b] + 1)
  dp[c][a] = max(dp[c][a],dpd[b] + 1)
  dp[a][b] = max(dp[a][b],dpd[c] + 1)
  dp[b][a] = max(dp[b][a],dpd[c] + 1)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax)
  dp[b][a] = max(0,dp[b][a],prevdpmax)
  dp[b][c] = max(0,dp[b][c],prevdpmax)
  dp[c][b] = max(0,dp[c][b],prevdpmax)
  dp[a][c] = max(0,dp[a][c],prevdpmax)
  dp[c][a] = max(0,dp[c][a],prevdpmax)
  update(a,b)
  update(a,c)
  update(b,a)
  update(b,c)
  update(c,a)
  update(c,b)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j])
    dp[j][b] = max(dp[j][b],prevdpmaxj[j])
    dp[j][c] = max(dp[j][c],prevdpmaxj[j])
    dp[a][j] = max(dp[a][j],prevdpmaxj[j])
    dp[b][j] = max(dp[b][j],prevdpmaxj[j])
    dp[c][j] = max(dp[c][j],prevdpmaxj[j])
    update(j,a)
    update(j,b)
    update(j,c)
    update(a,j)
    update(b,j)
    update(c,j)

print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Submission status: Accepted

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

N = int(input().strip())+2
A = list(map(int,input().split()))+[N-1,N]
INF = N
dp = [[-INF for j in range(N)] for i in range(N)]
dpmax = -INF
dpmaxj = [-INF for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
  dpmaxj[d] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
  dpmaxj[a] = 1
  dpmaxj[e] = 1
  dpmax = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1
  dpmaxj[a] = 1
  dpmaxj[b] = 1
  dpmax = 1
else:
  L = [a,b,c,d,e]
  for i in range(5):
    for j in range(i+1,5):
      p,q = L[i],L[j]
      dp[p][q] = 0
      dp[p][q] = 0
      dpmaxj[p] = 0
      dpmaxj[q] = 0
  dpmax = 0 

def update(i,j):
  dpmaxj[i] = max(dpmaxj[i],dp[i][j])
  dpmaxj[j] = max(dpmaxj[j],dp[i][j])

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxj = dpmaxj[:]
  dpd = [dp[k][k] for k in range(N)]
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  prevdpka = [dp[i][a] for i in range(N)]
  prevdpla = [dp[a][i] for i in range(N)] 
  prevdpkb = [dp[i][b] for i in range(N)]
  prevdplb = [dp[b][i] for i in range(N)] 
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][c],max(prevdpka[k],prevdpla[k]) + 1)
      dp[c][k] = max(dp[c][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][c],dp[c][k])
      update(k,c)
      update(c,k)
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][b],max(prevdpka[k],prevdpla[k]) + 1)
      dp[b][k] = max(dp[b][k],max(prevdpka[k],prevdpla[k]) + 1)
      dpmax = max(dpmax,dp[k][b],dp[b][k])
      update(k,b)
      update(b,k)
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][a],max(prevdpkb[k],prevdplb[k]) + 1)
      dp[a][k] = max(dp[a][k],max(prevdpkb[k],prevdplb[k]) + 1)
      dpmax = max(dpmax,dp[k][a],dp[a][k])
      update(k,a)
      update(a,k)
  dp[b][c] = max(dp[b][c],dpd[a] + 1)
  dp[c][b] = max(dp[c][b],dpd[a] + 1)
  dp[a][c] = max(dp[a][c],dpd[b] + 1)
  dp[c][a] = max(dp[c][a],dpd[b] + 1)
  dp[a][b] = max(dp[a][b],dpd[c] + 1)
  dp[b][a] = max(dp[b][a],dpd[c] + 1)
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b],dp[c][b],dp[c][a],dp[b][a])
  
  dp[a][b] = max(0,dp[a][b],prevdpmax)
  dp[b][a] = max(0,dp[b][a],prevdpmax)
  dp[b][c] = max(0,dp[b][c],prevdpmax)
  dp[c][b] = max(0,dp[c][b],prevdpmax)
  dp[a][c] = max(0,dp[a][c],prevdpmax)
  dp[c][a] = max(0,dp[c][a],prevdpmax)
  update(a,b)
  update(a,c)
  update(b,a)
  update(b,c)
  update(c,a)
  update(c,b)
  for j in range(N):
    dp[j][a] = max(dp[j][a],prevdpmaxj[j])
    dp[j][b] = max(dp[j][b],prevdpmaxj[j])
    dp[j][c] = max(dp[j][c],prevdpmaxj[j])
    dp[a][j] = max(dp[a][j],prevdpmaxj[j])
    dp[b][j] = max(dp[b][j],prevdpmaxj[j])
    dp[c][j] = max(dp[c][j],prevdpmaxj[j])
    update(j,a)
    update(j,b)
    update(j,c)
    update(a,j)
    update(b,j)
    update(c,j)

print(max(dp[N-2][N-1],dp[N-1][N-2])+score)

Submission status: Accepted

Solution code:
def solve(n, aaa):
    NINF = -(10 ** 12)
    dp = [[NINF] * n for _ in range(n)]
    dp_max = [NINF] * 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]))
                update_tasks.append((e, f, dp[c][d] + 1))

            update_tasks.append((a0, a0, dp_max_max))
            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))
            update_tasks.append((a1, a2, dp[a0][a0] + 1))
            update_tasks.append((a0, a2, dp[a1][a1] + 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: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:] - 1
    dp = np.full((n, n), -1, dtype=np.int16)
    dp_max = np.full(n, -1, dtype=np.int16)
    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 = dp_max.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 dp.max() + ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Submission status: Accepted

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]
use = {A[0], A[1]}

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 use:
            update.append((j,c, max(dp[a][j], dp[j][a]) + 1))
    elif b==c:
        for j in use:
            update.append((j,a, max(dp[b][j], dp[j][b]) + 1))
    elif c==a:
        for j in use:
            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 use:
        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)
    use.add(a)
    use.add(b)
    use.add(c)

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

Submission status: Accepted

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

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

a.append(n+1)
a.append(n+1)

dp = [[-1]*(n+2) for i in range(n+2)]
ma = [-1]*(n+2)

dp[a[0]][a[1]] = 0
ma[a[0]] = 0
ma[a[1]] = 0

after = 0

for i in range(n):
    x,y,z = a[3*i+2],a[3*i+3],a[3*i+4]
    if x == z:
        y,z = z,y
    if y == z:
        x,z = z,x
    
    if x == z:
        after += 1
        continue

    
    tank = []

    if x != y:
        for i in range(n+1):
            tank.append((i,x,ma[i]))
            tank.append((i,y,ma[i]))
            tank.append((i,z,ma[i]))       
        tank.append((x,y,max(max(ma),dp[z][z] + 1)))
        tank.append((x,z,max(max(ma),dp[y][y] + 1)))
        tank.append((y,z,max(max(ma),dp[x][x] + 1)))
    else:
        for i in range(n+1):
            tank.append((i,x,ma[i]))
            tank.append((i,y,ma[i]))
            tmp = ma[i]
            if dp[i][x] != -1:
                tmp = max(tmp,dp[i][x] + 1)
            if dp[x][i] != -1:
                tmp = max(tmp,dp[x][i] + 1)
            tank.append((i,z,tmp))
        tank.append((x,y,max(max(ma),dp[z][z] + 1)))
        tank.append((x,z,max(max(ma),dp[y][y] + 1)))
        tank.append((y,z,max(max(ma),dp[x][x] + 1)))

    for p,q,c in tank:
        dp[p][q] = max(dp[p][q],c)
        ma[p] = max(ma[p],c)
        ma[q] = max(ma[q],c)

res = 0
for i in range(n+2):
    for j in range(n+2):
        res = max(res,dp[i][j])

print(res+after)

Submission status: Accepted

Solution code:
#ABC176 #F 問題 (Question F) #解説方針 #提出参考
N = int(input())
A = list(map(int, input().split()))

#DP(動的計画法)用配列
ans = [[-N] * (N+1) for _ in range(N+1)]
#初期化 (Initialization)
a0, a1 = A[:2]
ans[a0][a1] = 0
ans[a1][a0] = 0

##最大値の管理
#ans[i] の最大値を集めた配列 (0 <= i <= N)
ma = [-N] * (N+1) 
#ans の初期化に合わせて初期化
ma[a0] = 0
ma[a1] = 0
#ansの全要素の最大値、0で初期化
all_max = 0

#3, 4, 5番目の数が等しいときに加算するための変数
add = 0

#DP部分 多分 O(N ** 2)
for i in range(N - 1): 
    #3, 4, 5番目の数を a, b, c とする
    a, b, c = A[3 * i + 2], A[3 * i + 3], A[3 * i + 4]
    #3つとも等しいとき、最後の三枚を消す
    if a == b == c:
        add += 1
        continue
    Q = []
    for _ in range(3):
        a, b, c = b, c, a
        # a, b, c から残す数を2つ選ぶ
        # ans[c][c] + 1 は [c,c,a,b,c]を想定
        # all_max は DP[i][k][l]の最大値で最大化するときに対応
        Q.append((a, b, max(all_max, ans[c][c] + 1)))
        
        # a, b, c から残す数を1つ選ぶ
        for j in range(1, N + 1):
            #これまでのDP[i][k][l] (k, lのうち片方の変数として見たとき) の最大値
            val = ma[j]
            #2つの数が等しいとき
            if b == c:
                val = max(val, ans[b][j] + 1)
            Q.append((a, j, val))
            
        #配列を使いまわしているので、DP[i + 1][k][l] を DP[i][k][l]で最大化し直す必要なし
        #もしDP[i][k][l]が最大なら、maxを取る過程でこれが残る
    for i, j, val in Q:
        #DP配列の更新
        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)
        all_max = max(all_max, val)
        
#ans の中から最大の値を見つけ出す。O(N ** 2)        
answer = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        #最後に残った3枚が同じならもう1点加算
        if i == j == A[-1]:
            answer = max(answer, ans[i][j] + 1)
        else:
            answer = max(answer, ans[i][j])
            
print(answer + add)

Submission status: Accepted

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
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):
            tmpmax = maxin[c2]
            if c1 > c2:
                change.append((c2,c1,tmpmax))
            else:
                change.append((c1,c2,tmpmax))

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

    for c1,c2,tmp in change:
        nmax = max(nmax,tmp)
        dp[c1][c2] = max(dp[c1][c2],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)