Problem:


Score : 400 points

Problem Statement

There is a grid with N rows and N columns of squares. Let (i,j) be the square at the i-th row from the top and the j-th column from the left.

These squares have to be painted in one of the C colors from Color 1 to Color C. Initially, (i,j) is painted in Color c_{i,j}.

We say the grid is a good grid when the following condition is met for all i,j,x,y satisfying 1 \leq i,j,x,y \leq N:

If (i+j) \% 3=(x+y) \% 3, the color of (i,j) and the color of (x,y) are the same.

If (i+j) \%  3 \neq (x+y) \% 3, the color of (i,j) and the color of (x,y) are different.

Here, X \% Y represents X modulo Y.

We will repaint zero or more squares so that the grid will be a good grid.

For a square, the wrongness when the color of the square is X before repainting and Y after repainting, is D_{X,Y}.

Find the minimum possible sum of the wrongness of all the squares.

Constraints

1 \leq N \leq 500

3 \leq C \leq 30

1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)

1 \leq c_{i,j} \leq C

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C
D_{1,1} ... D_{1,C}
:
D_{C,1} ... D_{C,C}
c_{1,1} ... c_{1,N}
:
c_{N,1} ... c_{N,N}

Output

If the minimum possible sum of the wrongness of all the squares is x, print x.

Sample Input 1

2 3
0 1 1
1 0 1
1 4 0
1 2
3 3

Sample Output 1

3

Repaint (1,1) to Color 2. The wrongness of (1,1) becomes D_{1,2}=1.

Repaint (1,2) to Color 3. The wrongness of (1,2) becomes D_{2,3}=1.

Repaint (2,2) to Color 1. The wrongness of (2,2) becomes D_{3,1}=1.

In this case, the sum of the wrongness of all the squares is 3.

Note that D_{i,j} \neq D_{j,i} is possible.

Sample Input 2

4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2

Sample Output 2

428



Sample input:
2 3
0 1 1
1 0 1
1 4 0
1 2
3 3


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
D = []
c = []
d0 = {}
d1 = {}
d2 = {}
N,C = map(int,input().split())
for i in range(C):
    D.append(list(map(int,input().split())))
for i in range(N):
    c.append(list(map(int,input().split())))

for i in range(C):
    d0[i+1]=0
    d1[i+1]=0
    d2[i+1]=0

for i in range(N):
    for j in range(N):
        for k in range(C):
            if (i+j)%3==0:
                d0[k+1]+=D[c[i][j]-1][k]
            elif (i+j)%3==1:
                d1[k+1]+=D[c[i][j]-1][k]
            else:
                d2[k+1]+=D[c[i][j]-1][k]
l = []
for C1 in range(C):
    for C2 in range(C):
        for C3 in range(C):
            if C1 != C2 and C2 != C3 and C3 != C1:
                l.append(d0[C1+1]+d1[C2+1]+d2[C3+1])

print(min(l))

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int,input().split())
D = []
for i in range(C):
    t = list(map(int,input().split()))
    D.append(t)
c = []
for i in range(N):
    t = list(map(int,input().split()))
    c.append(t)
Dsum = []
for k in range(C):
    ccc = [0, 0, 0]
    for i in range(N):
        for j in range(N):
            ccc[(i+j)%3] += D[c[i][j]-1][k]
    Dsum.append(ccc)
ans = 9876543210
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                ans = min(ans, Dsum[i][0]+Dsum[j][1]+Dsum[k][2])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# divide this matrix into 3 groups according to the remainder
# then consider the cost

from itertools import permutations

N, C = [int(elem) for elem in input().split(' ')]
D_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(C)]
assert len(D_matrix) == C
assert len(D_matrix[0]) == C
c_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(c_matrix) == N
assert len(c_matrix[0]) == N

# grouping
# O(N^2)
mod_0, mod_1, mod_2 = [], [], []
for i in range(N):
    for j in range(N):
        if (i + j) % 3 == 0:
            mod_0.append((i, j))
        elif (i + j) % 3 == 1:
            mod_1.append((i, j))
        else:
            mod_2.append((i, j))

# O(C^3 * N^2)
# muda
# only considering top 3 transitions is enough?
min_cost = float('inf')
for colors in permutations(range(C), 3):
    total_cost = 0
    for idx_color, mod in enumerate((mod_0, mod_1, mod_2)):
        for i, j in mod:
            color = c_matrix[i][j] - 1
            total_cost += D_matrix[color][colors[idx_color] - 1]
    min_cost = min(min_cost, total_cost)

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
N,C=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(C)]
c=[list(map(int,input().split())) for _ in range(N)]
cost=[[0 for _ in range(C)],[0 for _ in range(C)],[0 for _ in range(C)]]
for i in range(N):
    for j in range(N):
        for x in range(C):
            cost[(i+j+2)%3][x]+=D[c[j][i]-1][x]
            

ar=[[cost[0][i],i] for i in range(C)]
br=[[cost[1][i],i] for i in range(C)]
cr=[[cost[2][i],i] for i in range(C)]
sa=sorted(ar)
sb=sorted(br)
sc=sorted(cr)
outp=[]
for i in range(3):
    for j in range(3):
        for k in range(3):
            if(sa[i][1]!=sb[j][1] and sa[i][1]!=sc[k][1] and sb[j][1]!=sc[k][1]):
                outp.append(sa[i][0]+sb[j][0]+sc[k][0])
print(min(outp))

Submission status: Time Limit Exceeded

Solution code:
# divide this matrix into 3 groups according to the remainder
# then consider the cost

from itertools import permutations

N, C = [int(elem) for elem in input().split(' ')]
D_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(C)]
assert len(D_matrix) == C
assert len(D_matrix[0]) == C
c_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(c_matrix) == N
assert len(c_matrix[0]) == N

# grouping
# O(N^2)
mod_0, mod_1, mod_2 = [], [], []
for i in range(N):
    for j in range(N):
        if (i + j) % 3 == 0:
            mod_0.append((i, j))
        elif (i + j) % 3 == 1:
            mod_1.append((i, j))
        else:
            mod_2.append((i, j))

# O(C^3 * N^2)
min_cost = float('inf')
for colors in permutations(range(C), 3):
    total_cost = 0
    for idx_color, mod in enumerate((mod_0, mod_1, mod_2)):
        for i, j in mod:
            color = c_matrix[i][j] - 1
            total_cost += D_matrix[color][colors[idx_color] - 1]
    min_cost = min(min_cost, total_cost)

print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
inf = 1000*500*500
D = []
c = []
d = {}
N,C = map(int,input().split())
for i in range(C):
    D.append(list(map(int,input().split())))
for i in range(N):
    c.append(list(map(int,input().split())))

for C1 in range(C):
    for C2 in range(C):
        for C3 in range(C):
            if C1 != C2 and C2 != C3 and C3 != C1:
                d[(C1+1,C2+1,C3+1)]=0
            else:
                d[C1+1,C2+1,C3+1]=inf

for i in range(N):
    for j in range(N):
        for C1 in range(C):
            for C2 in range(C):
                for C3 in range(C):
                    if (i+j)%3==0:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C1]
                    elif (i+j)%3==1:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C2]
                    else:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C3]

l = []
for x in d:
    l.append(d[x])
print(min(l))

Submission status: Time Limit Exceeded

Solution code:
N,C=map(int, raw_input().split())
D=[]
for i in range(C):
    D.append(map(int,raw_input().split()))

c=[]
for i in range(N):
    c.append(map(int,raw_input().split()))

d=[[],[],[]]
for i in range(C):
    d[0].append([0,i])
    d[1].append([0,i])
    d[2].append([0,i])
    for x in range(N):
        for y in range(N):
            d[(x+y)%3][i][0] += D[c[x][y]-1][i]

X = sorted(d[0], key=lambda x: x[0])[:3]
Y = sorted(d[1], key=lambda x: x[0])[:3]
Z = sorted(d[2], key=lambda x: x[0])[:3]

m = -1
for x in range(3):
    for y in range(3):
        for z in range(3):
            if X[x][1] == Y[y][1]:
                continue
            if Y[y][1] == Z[z][1]:
                continue
            if Z[z][1] == X[x][1]:
                continue
            q = X[x][0] + Y[y][0] + Z[z][0]
            if m == -1 or m > q:
                m = q
print m

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,C=map(int,input().split())

D=[None]*C
for i in range(C):
    D[i]=list(map(int,input().split()))

c=[None]*N
for i in range(N):
    c[i]=list(map(int,input().split()))

c_0=[]
c_1=[]
c_2=[]

for i in range(N):
    for j in range(N):
        if (i+j+2)%3==0:
            c_0+=[c[i][j]]
        elif (i+j+2)%3==1:
            c_1+=[c[i][j]]
        else:
            c_2+=[c[i][j]]

L=[]
for i in range(C):
    L+=[i+1]

ROOP=list(itertools.permutations(L,3))


ANS=float("inf")


for i in range(len(ROOP)):
    IWA=0
    for j in c_0:
        IWA+=D[j-1][ROOP[i][0]-1]
    for j in c_1:
        IWA+=D[j-1][ROOP[i][1]-1]
    for j in c_2:
        IWA+=D[j-1][ROOP[i][2]-1]
    if ANS>IWA:
        ANS=IWA

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,C = map(int,input().split())
D = [input().split() for l in range(C)]
c = [input().split() for l in range(N)]
F = list(range(C))
B = list(itertools.permutations(F, 3))
ans = 0
kotae = float("inf")
for e,f,g in B:
    for i in range(N):
        for j in range(N):
            if (i+j+2) %3 == 1:
                    ans += int(D[int(c[i][j])-1][e])
            if (i+j+2) %3 == 2:
                    ans += int(D[int(c[i][j])-1][f])
            if (i+j+2) %3 == 0:
                    ans += int(D[int(c[i][j])-1][g])
    kotae = min(ans,kotae)
    ans = 0
print(kotae)

Submission status: Time Limit Exceeded

Solution code:
N,C = [int(i) for i in input().split()]
D = [[int(j) for j in input().split()] for i in range(C)]
c = [[int(j) for j in input().split()] for i in range(N)]
bank = [[],[],[]]
for i in range(N):
    for j in range(N):
        bank[(i+j)%3].append(c[i][j]-1)


min = 100000
for i in [ii for ii in range(C)]:
    for j in [jj for jj in range(C) if jj != i]:
        for k in [kk for kk in range(C) if kk != i and kk != j]:
            count = 0
            for x in bank[0]:
                if x != i:
                    count += D[x][i]
            for y in bank[1]:
                if y != j:
                    count += D[y][j]
            for z in bank[2]:
                if z != k:
                    count += D[z][k]
            if min > count:
                min = count
print(min)

Submission status: Time Limit Exceeded

Solution code:
N,C = map(int,input().split())
D = []
for i in range(C):
    D.append(list(map(int,input().split())))
c = []
for i in range(N):
    c.append(list(map(int,input().split())))

current_minimum = 1000 * 500 * 500 + 1

import itertools
for (c0,c1,c2) in itertools.permutations(range(C), 3):
	color = [c0,c1,c2]
	tmp = 0
	for (i,j) in itertools.product(range(N),range(N)):
		current_color = c[i][j]
		target_color = color[((i+1)+(j+1)) % 3]
		tmp += D[current_color - 1][target_color-1]
	if current_minimum >= tmp:
		current_minimum = tmp
print(current_minimum)

Submission status: Time Limit Exceeded

Solution code:
N,C=map(int,input().split())
D=[]
for i in range(C):
	D.append(list(map(int,input().split())))
c=[]
for i in range(N):
	c.append(list(map(int,input().split())))

ans=1000000000000
for i in range(1,C+1):
	for j in range(1,C+1):
		if j==i:
			continue
		for k in range(1,C+1):
			if k==j or k==i:
				continue
			x=0
			for p in range(N):
				for q in range(N):
					color=c[p][q]
					if (p+q)%3==0:
						x+=D[color-1][i-1]
					elif (p+q)%3==1:
						x+=D[color-1][j-1]
					else:
						x+=D[color-1][k-1]
			if x<ans:
				ans=x
print(ans)
'''
co=[0]*(C+1)
co1=[0]*(C+1)
for i in range(N):
	for j in range(N):
		if (i+j)%3==0:
			co[c[i][j]]+=1
		else:
			co1[c[i][j]]+=1
min1 = 1000000000000
for i in range(1,C+1):
	k=0
	for j in range(1,C+1):
		if j!=i:
			k+=co[j]*D[j-1][i-1]
	if k<min1:
		min1=k
print(min1)
min2= 0
for i in range(1,C+1):
	while co1[i]>1:
		k=1000000000
		p=0
		for j in range(1,C+1):
			if co1[j]==0 and D[i-1][j-1]<k:
				p=j
				k=D[i-1][j-1]
		co1[p]=1
		co1[i]-=1
		min2+=k
print(min1+min2)
'''

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import itertools

N,C=[int(i) for i in input().split()]
D=[[int(i) for i in input().split()] for _ in range(C)]
c=[[int(i)-1 for i in input().split()] for _ in range(N)]

costXY = [[0]*C for _ in range(3)]



for X in range(3):
    for Y in range(C):
        costXY[X][Y] = sum([D[c[i][j]][Y] for i,j in itertools.product(range(N), repeat=2) if (i+j)%3==X])

#print(costXY)    

ans = 1<<31
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            p=costXY[0][i] + costXY[1][j] + costXY[2][k]
#            print(p)
            ans = min(ans,p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# your code goes here
N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]

ans = 1145141919810
for i in range(C):
	for j in range(C):
		if j == i:
			continue
		for k in range(C):
			if k == i or k == j:
				continue
			tmp = 0
			for x in range(N):
				for y in range(N):
					if (x+y+2)%3==2:
						tmp+= D[c[x][y]-1][i]
					elif (x+y+2)%3==0:
						tmp+= D[c[x][y]-1][j]
					else:
						tmp+= D[c[x][y]-1][k]
			ans = min(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, c = map(int, input().split())
D = [[int(i) for i in input().split()] for j in range(c)]
C = [[int(i) for i in input().split()] for j in range(N)]
A = [[0 for i in range(c)] for j in range(3)]
for i in range(N):
    for j in range(N):
        for k in range(c):
            A[(i+j)%3][k] += D[C[i][j]-1][k]

ans = 1e9
for i in range(c):
    for j in range(i):
        for k in range(j):
            for l in range(3):
                ans = min(ans, A[l][i]+A[(l+1)%3][j]+A[(l+2)%3][k],
                          A[l][i]+A[(l-1)%3][j]+A[(l-2)%3][k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 1. 入出力 (二次元配列)

N, C = map(int, input().split())

D = [ list(map(int, input().split())) for _ in range(C) ]
col = [ list(map(int, input().split())) for _ in range(N) ]

ans = 1 << 60
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or j == k or k == i:
                continue

            temp = 0
            lst = [i, j, k]

            for x in range(N):
                for y in range(N):
                    mod = (x + y) % 3
                    temp += D[ col[x][y] - 1 ][ lst[mod] ]

            ans = min(ans, temp)
            # print(lst, temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
c = [list(map(int, input().split())) for i in range(N)]
col = [[0]*3 for i in range(C)]
for i in range(N):
    for j in range(N):
        p = c[i][j]-1
        for k in range(C):
            col[k][(i+j)%3] += D[p][k]
ans = 10**18
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if i == k or j == k:
                continue
            ans = min(ans, col[i][0] + col[j][1] + col[k][2])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

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

n, u = na()
d = []
for i in range(u):
    d.append(na())

c = []
for i in range(n):
    c.append(na())

for i in range(n):
    for j in range(n):
        c[i][j] -= 1

fs = []
for i in range(u):
    f = [0]*3
    for j in range(n):
        t = j%3
        for k in range(n):
            f[t] += d[c[j][k]][i]
            t += 1
            if t == 3:
                t = 0
    fs.append(f)

ans = 99999999999999999
for i in range(u):
    for j in range(u):
        for k in range(u):
            if i == j or j == k or k == i: continue

            ans = min(ans, fs[i][0] + fs[j][1] + fs[k][2])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

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

n, u = na()
d = []
for i in range(u):
    d.append(na())

c = []
for i in range(n):
    c.append(na())

for i in range(n):
    for j in range(n):
        c[i][j] -= 1

fs = []
for i in range(u):
    f = [0]*3
    for j in range(n):
        for k in range(n):
            f[(j+k)%3] += d[c[j][k]][i]
    fs.append(f)

ans = 99999999999999999
for i in range(u):
    for j in range(u):
        for k in range(u):
            if i == j or j == k or k == i: continue

            ans = min(ans, fs[i][0] + fs[j][1] + fs[k][2])
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, c = map(int, input().split())

d_lst = [list(map(int, input().split())) for _ in range(c)]
c_lst = [list(map(int, input().split())) for _ in range(n)]

lst = [[0] * c for _ in range(3)]

for i in range(n):
    for j in range(n):
        lst[(i + j) % 3][c_lst[i][j]-1] += 1
        
cnt = []

for i in range(c):
    temp = []
    for j in range(3):
        cal = 0
        for k in range(c):
            cal += lst[j][k] * d_lst[k][i]
        temp.append(cal)
    cnt.append(temp) 

 
temp = []
for l in permutations(list(range(c)), 3):
    temp.append(cnt[l[0]][0] + cnt[l[1]][1] + cnt[l[2]][2])

print(min(temp))

Submission status: Accepted

Solution code:
#計算量 max(N ** 2, C ** 3)
N, C = map(int, input().split())
D = [0] * C
for i in range(C):
  D[i] = list(map(int, input().split()))
grid = [0] * N
for i in range(N):
  grid[i] = list(map(int, input().split()))
  
#print(D, grid) 
grid3 = [[0] * C for i in range(3)]
#grid[i][j]:3で割って余りが i のマスで、色がjであるマスの個数
for i in range(N):
  for j in range(N):
    nn = (i + j) % 3
    color = grid[i][j] - 1
    grid3[nn][color] += 1
#print(grid3)  

score = [[0] * C for i in range(3)]
#score[i][j]:3で割って余りが i のマスを、色jにするときの違和感
#3 * C * C
for j in range(C):
  for i in range(3):
    for k in range(C): 
      score[i][j] += grid3[i][k] * D[k][j]
#print(score)            
ans = 10 ** 10  
for i in range(C):
  for j in range(C):
    if i != j:
      for k in range(C):
        if (i != k) and (j != k):
          now = score[0][i] + score[1][j] + score[2][k]
          ans = min(ans, now)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product, permutations
def main():
    n, c = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(c)]
    C = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

    group = [Counter([C[i][j] for i,j in product(range(n), range(n)) if (i+j+2) %3 == k]) for k in range(3)] 
    
    ans = float('inf')
    for color in permutations(range(c), 3):
        diff = 0
        for i in range(3):
            diff += sum(D[before_color][color[i]]*count for before_color, count in group[i].items())
        ans = min(ans, diff)
    print(ans)

main()

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    c = [list(map(int, input().split())) for _ in range(N)]
    score = [[0] * 3 for _ in range(C)]
    for i in range(N):
        for j in range(N):
            for k in range(C):
                score[k][(i+j)%3] += D[c[i][j]-1][k]

    ans = float('inf')
    for balls in permutations(range(C),3):
        tmp = 0
        for i in range(3):
            tmp += score[balls[i]][i]
        ans = min(ans, tmp)
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
import numpy as np
N, C = map(int, input().split())
D = np.ndarray((C, C), dtype=int)
c = np.ndarray((N, N), dtype=int)
for i in range(C):
    D[i] = list(map(int,input().split()))
for i in range(N):
    c[i] = list(map(int,input().split()))
c -= 1
acc = np.zeros((3, C), dtype=int)
for i in range(N):
    for j in range(N):
        acc[(i+j) % 3] += D[c[i][j]]
ans = float("inf")
for i,j,k in permutations(range(C), r=3):
    ans = min(ans, acc[0][i]+acc[1][j]+acc[2][k])
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, C = na()
D = [na() for _ in range(C)]
c = [na() for _ in range(N)]

z = {}
o = {}
t = {}
for i in range(1, N+1):
    for j in range(1, N+1):
        q = (i + j) % 3
        now = c[i - 1][j - 1] - 1
        if q == 0:
            if now not in z.keys():
                z[now] = 1
            else:
                z[now] += 1
        if q == 1:
            if now not in o.keys():
                o[now] = 1
            else:
                o[now] += 1
        if q == 2:
            if now not in t.keys():
                t[now] = 1
            else:
                t[now] += 1

ans = inf
for i, j, l in itertools.permutations(range(C), 3):
    tmp = 0
    for k, v in z.items():
        tmp += v * D[k][i]
    for k, v in o.items():
        tmp += v * D[k][j]
    for k, v in t.items():
        tmp += v * D[k][l]
    ans = min(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [[0] * c for _ in range(3)]
for i, ci in enumerate(cmat):
    for j, cij in enumerate(ci):
        mod = (i + j) % 3
        dcnt[mod][cij - 1] += 1

ans = 10 ** 9
for color in permutations(range(c), 3):
    tmp = 0
    for tgt, cnt in zip(color, dcnt):
        tmp += sum(d[i][tgt] * cnt[i] for i in range(c))
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [[0] * c for _ in range(3)]
for i in range(n):
    for j in range(n):
        mod = (i + j) % 3
        dcnt[mod][cmat[i][j] - 1] += 1

ans = 10 ** 9
for color in permutations(range(c), 3):
    tmp = 0
    for tgt, cnt in zip(color, dcnt):
        tmp += sum(d[i][tgt] * cnt[i] for i in range(c))
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [defaultdict(int) for _ in range(3)]
for i, ci in enumerate(cmat):
    for j, cij in enumerate(ci):
        mod = (i + j) % 3
        dcnt[mod][cij - 1] += 1

ans = 10 ** 9
for color in permutations(range(c), 3):
    tmp = 0
    for tgt, cnt in zip(color, dcnt):
        tmp += sum(d[k][tgt] * cnt[k] for k in cnt)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [defaultdict(int) for _ in range(3)]
for i, ci in enumerate(cmat, 1):
    for j, cij in enumerate(ci, 1):
        mod = (i + j) % 3
        dcnt[mod][cij - 1] += 1

ans = 10 ** 9
for color in permutations(range(c), 3):
    if len(set(color)) == 3:
        tmp = 0
        for i, cnt in enumerate(dcnt):
            tmp += sum(d[k][color[i]] * cnt[k] for k in cnt)
        ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [defaultdict(int) for _ in range(3)]
for i, ci in enumerate(cmat):
    for j, cij in enumerate(ci):
        mod = (i + j) % 3
        dcnt[mod][cij - 1] += 1

ans = 10 ** 9
for color in permutations(range(c), 3):
    tmp = 0
    for ci, cnt in zip(color, dcnt):
        tmp += sum(d[k][ci] * cnt[k] for k in cnt)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [defaultdict(int) for _ in range(3)]
for i, ci in enumerate(cmat, 1):
    for j, cij in enumerate(ci, 1):
        mod = (i + j) % 3
        dcnt[mod][cij - 1] += 1

ans = 10 ** 9
for color in permutations(range(c), 3):
    tmp = 0
    for ci, cnt in zip(color, dcnt):
        tmp += sum(d[k][ci] * cnt[k] for k in cnt)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [defaultdict(int) for _ in range(3)]
for i, ci in enumerate(cmat, 1):
    for j, cij in enumerate(ci, 1):
        mod = (i + j) % 3
        dcnt[mod][cij - 1] += 1

ans = 10 ** 9
for color in permutations(range(c), 3):
    tmp = 0
    for i, cnt in enumerate(dcnt):
        tmp += sum(d[k][color[i]] * cnt[k] for k in cnt)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
cmat = [list(map(int, input().split())) for _ in range(n)]

dcnt = [defaultdict(int) for _ in range(3)]
for i, ci in enumerate(cmat, 1):
    for j, cij in enumerate(ci, 1):
        mod = (i + j) % 3
        dcnt[mod][cij - 1] += 1

ans = 1000 * n ** 2
for color in permutations(range(c), 3):
    tmp = 0
    for i, cnt in enumerate(dcnt):
        tmp += sum(d[k][color[i]] * cnt[k] for k in cnt)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, C = LI()
    D = [LI() for _ in range(C)]
    c = [LI_() for _ in range(N)]

    # 座標グループごとに、その色に塗り替えるとかかるコストを前計算
    a = [[0] * C for _ in range(3)]
    for i, j in itertools.product(range(N), repeat=2):
        for k in range(C):
            a[(i+j)%3][k] += D[c[i][j]][k]

    # 座標グループごとに色の割当とそのコストを全探索
    ans = INF
    for i, j, k in itertools.permutations(range(C), 3):
        ans = min(a[0][i] + a[1][j] + a[2][k], ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
d = [list(map(int,input().split())) for i in range(c)]
s = [list(map(int,input().split())) for i in range(n)]
x = [0] * c
y = [0] * c
z = [0] * c
for i in range(n):
    for j in range(n):
        a = (i+j) % 3
        if a == 0:
            x[s[i][j]-1] += 1
        if a == 1:
            y[s[i][j]-1] += 1
        if a == 2:
            z[s[i][j]-1] += 1
ans = 10 ** 16
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and i != k and j != k:
                o = 0
                for l in range(c):
                    o += d[l][i] * x[l]
                p = 0
                for l in range(c):
                    p += d[l][j] * y[l]
                q = 0
                for l in range(c):
                    q += d[l][k] * z[l]
                ans = min(ans,o+p+q)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

import numpy as np
from numba import njit, i8


@njit(i8[:, :](i8, i8, i8[:, :], i8[:, :]), cache=True)
def calc_cost(N, C, D, c):
    cost = np.zeros((C, 3), dtype=np.int64)
    for i in range(N):
        for j in range(N):
            for k in range(C):
                cost[k][(i + j) % 3] += D[c[i][j] - 1][k]
    return cost


N, C, *Dc = map(int, open(0).read().split())
D = np.array(Dc[: C * C], dtype=np.int64).reshape(C, C)
c = np.array(Dc[C * C :], dtype=np.int64).reshape(N, N)
cost = calc_cost(N, C, D, c)

ans = min(
    sum(cost[c][i] for i, c in enumerate(colors))
    for colors in permutations(range(C), 3)
)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
cost = [[0] * 3 for _ in range(C)]

for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[k][(i + j) % 3] += D[c[i][j] - 1][k]

ans = min(
    sum(cost[c][i] for i, c in enumerate(colors))
    for colors in permutations(range(C), 3)
)
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
N,C = map(int,input().split())
D = [list(map(int,input().split())) for c in range(C)]
G = [list(map(int,input().split())) for n in range(N)]
H = [C*[0] for n in range(3)]

for i in range(N):
  for j,k in enumerate(G[i]):
    H[(i+j)%3][k-1]+=1

ans = float("inf")

for i in permutations(range(C),3):
  c = 0
  for j in range(3):
    for k in range(C):
      c+=D[k][i[j]]*H[j][k]
  ans = min(ans,c)

print(ans)