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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()+2
if N == 3:
  print(1)
  exit()

A = IL()+[N-1,N]

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 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
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1

for i in range(N-3):
  prevdpmax = dpmax
  prevdpmaxk = dpmaxk[:]
  prevdpmaxl = dpmaxl[:]
  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
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dp[c][k] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dp[b][k] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dp[a][k] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
  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])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c],dp[b][a])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c],dp[a][b])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b],dp[a][c])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b],dp[c][b])
  dp[a][b] = prevdpmax
  dp[b][a] = prevdpmax
  dp[b][c] = prevdpmax
  dp[c][b] = prevdpmax
  dp[a][c] = prevdpmax
  dp[c][a] = prevdpmax
  for j in range(N):
    dp[j][a] = prevdpmaxk[j]
    dp[j][b] = prevdpmaxk[j]
    dp[j][c] = prevdpmaxk[j]
    dp[a][j] = prevdpmaxl[j]
    dp[b][j] = prevdpmaxl[j]
    dp[c][j] = prevdpmaxl[j]

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
if N == 1:
  print(1)
  exit()

A = IL()

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 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
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1

for i in range(N-2):
  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
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dp[c][k] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dp[b][k] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dp[a][k] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
  
  dp[b][c] = dpd[a] + 1
  dp[c][b] = dpd[a] + 1
  dp[a][c] = dpd[b] + 1
  dp[c][a] = dpd[b] + 1
  dp[a][b] = dpd[c] + 1
  dp[b][a] = dpd[c] + 1
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c],dp[b][a])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c],dp[a][b])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b],dp[a][c])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b],dp[c][b])
  dp[a][b] = dpmax
  dp[b][a] = dpmax
  dp[b][c] = dpmax
  dp[c][b] = dpmax
  dp[a][c] = dpmax
  dp[c][a] = dpmax
  for j in range(N):
    dp[j][a] = dpmaxk[j]
    dp[j][b] = dpmaxk[j]
    dp[j][c] = dpmaxk[j]
    dp[a][j] = dpmaxl[j]
    dp[b][j] = dpmaxl[j]
    dp[c][j] = dpmaxl[j]

z = A[-1]-1
print(max(dpmax,dp[z][z]+1)+score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
if N == 1:
  print(1)
  exit()

A = IL()

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 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
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1

for i in range(N-2):
  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
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
  
  dp[b][c] = dpd[a] + 1
  dp[a][c] = dpd[b] + 1
  dp[a][b] = dpd[c] + 1
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b])
  dp[a][b] = dpmax
  dp[b][c] = dpmax
  dp[a][c] = dpmax
  for j in range(N):
    dp[j][a] = dpmaxk[j]
    dp[j][b] = dpmaxk[j]
    dp[j][c] = dpmaxk[j]
    dp[a][j] = dpmaxl[j]
    dp[b][j] = dpmaxl[j]
    dp[c][j] = dpmaxl[j]

z = A[-1]-1
print(max(dpmax,dp[z][z]+1)+score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()+[N+1,N+2]

dp = [[0 for j in range(N+2)] for i in range(N+2)]
dpmax = 0
dpmaxk = [0 for i in range(N+2)]
dpmaxl = [0 for i in range(N+2)]
score = 0
a,b,c,d,e = sorted(A[:5])

if a == b == c:
  score += 1
elif b == c == d:
  score += 1
elif c == d == e:
  score += 1

for i in range(N-1):
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
    continue
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
    continue
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
    continue
  dp[b][c] = dp[a][a] + 1
  dp[a][c] = dp[b][b] + 1
  dp[a][b] = dp[c][c] + 1
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b])
  dp[a][b] = dpmax
  dp[b][c] = dpmax
  dp[a][c] = dpmax
  for i in range(N):
    dp[i][a] = dpmaxk[i]
    dp[i][b] = dpmaxk[i]
    dp[i][c] = dpmaxk[i]
    dp[a][i] = dpmaxl[i]
    dp[b][i] = dpmaxl[i]
    dp[c][i] = dpmaxl[i]
print(dpmax+score)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
import itertools
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
    
    
def main():
    N = I()
    mylist = LI()
    #Nが１の場合・・・
    if N == 1:
        count = Counter(mylist).most_common()
        if count[0][1] >= 3:
            print(1)
        else:
            print(0)
        sys.exit()
    mylist = deque(mylist)
    dq = deque()
    score = 0
    dq.append([mylist.popleft() for i in range(2)])

    for i in range(N-1):
        new_deque = deque()
        temp2 = [mylist.popleft() for i in range(3)]
        while dq:
            temp = dq.popleft()
            count = Counter(temp+temp2).most_common()
            if count[0][1] >= 3:
                templ=[]
                for key, value in count:
                    if value >= 3:
                        value -= 3
                    for j in range(value):
                        templ.append(key)
                new_deque = deque()
                new_deque.append(templ)
                score += 1
                break 
            else:
                for templ in itertools.combinations((temp+temp2),2):
                    new_deque.append(list(templ))
        dq = deque(get_unique_list(new_deque))

    while dq:
        temp = dq.popleft()
        count = Counter(temp+list(mylist)).most_common()
        if count[0][1] == 3:
            print(score+1)
            sys.exit()
    print(score)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
import itertools
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    mylist = LI()
    #Nが１の場合・・・
    if N == 1:
        count = Counter(mylist).most_common()
        if count[0][1] >= 3:
            print(1)
        else:
            print(0)
        sys.exit()
    mylist = deque(mylist)
    score = 0
    dq = [[mylist.popleft() for i in range(2)]]

    for i in range(N-1):
        new_deque = set()
        temp2 = [mylist.popleft() for i in range(3)]
        for temp in dq:
            temp = list(temp)
            count = Counter(temp+temp2).most_common()
            if count[0][1] >= 3:
                templ=[]
                for key, value in count:
                    if value >= 3:
                        value -= 3
                    for j in range(value):
                        templ.append(key)
                new_deque = [templ]
                score += 1
                break 
            else:
                for templ in itertools.combinations((temp+temp2),2):
                    new_deque = new_deque | {templ}
        dq = new_deque

    for temp in dq:
        temp = list(temp)
        count = Counter(temp+list(mylist)).most_common()
        if count[0][1] >= 3:
            print(score+1)
            sys.exit()
    print(score)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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, max(maxdp[j], maxdp[a])))
        update.append((j,b, max(maxdp[j], maxdp[b])))
        update.append((j,c, max(maxdp[j], maxdp[c])))
    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: Wrong Answer

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):
            tmpmax = maxin[c2]
            if c1 > c2:
                c1,c2 = c2,c1
            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)
        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)