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

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

n,c = map(int, input().split())
color = []
for _ in range(c):
    color.append(list(map(int, input().split())))

grid = {i:{} for i in range(3)}
for i in range(n):
    for j,t in enumerate(map(int, input().split())):
        t -= 1
        if t not in grid[(i+j + 2) % 3]:
            grid[(i+j + 2) % 3][t] = 0
        grid[(i+j + 2) % 3][t] += 1

costs = [[0 for _ in range(c)],[0 for _ in range(c)],[0 for _ in range(c)]]
for cc in range(c):
    for i in range(3):
        for d,cnt in grid[i].items():
            costs[i][cc] += color[d][cc] * cnt

rc = range(c)
x = sorted(list(rc), key=lambda x: costs[0][x])[:3]
y = sorted(list(rc), key=lambda x: costs[1][x])[:3]
z = sorted(list(rc), key=lambda x: costs[2][x])[:3]

mn = 10**9
for i in x:
    for j in y:
        for k in z:
            if i == j or j == k or k == i:
                continue
            if mn > costs[0][i] + costs[1][j] + costs[2][k]:
                mn = costs[0][i] + costs[1][j] + costs[2][k]
print(mn)

Submission status: Accepted

Solution code:
n,c = map(int, input().split())
color, grid = [], []
for _ in range(c):
    color.append(list(map(int, input().split())))
grid = {i:{} for i in range(3)}

for i in range(n):
    for j,t in enumerate(map(int, input().split())):
        t -= 1
        if t not in grid[(i+j + 2) % 3]:
            grid[(i+j + 2) % 3][t] = 0
        grid[(i+j + 2) % 3][t] += 1

costs = [[0 for _ in range(c)],[0 for _ in range(c)],[0 for _ in range(c)]]
for cc in range(c):
    for i in range(3):
        for d,cnt in grid[i].items():
            costs[i][cc] += color[d][cc] * cnt

x = sorted(list(range(c)), key=lambda x: costs[0][x])[:3]
y = sorted(list(range(c)), key=lambda x: costs[1][x])[:3]
z = sorted(list(range(c)), key=lambda x: costs[2][x])[:3]
mn = 10**9
for i in x:
    for j in y:
        for k in z:
            if i == j or j == k or k == i:
                continue
            if mn > costs[0][i] + costs[1][j] + costs[2][k]:
                mn = costs[0][i] + costs[1][j] + costs[2][k]
print(mn)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, c = LI()
D = LIR(c)
C = LIR(n)
#　mod_color[mod3][color]
mod_color = [[0] * c for _ in range(3)]
for y in range(n):
    for x in range(n):
        mod_color[(y + x + 2) % 3][C[y][x] - 1] += 1


# 30 * 29 * 28
ans = INF
# もともとmod0のところをiに、mod1のところをjに、mod2のところをkにする。
for i, j, k in permutations(range(c), 3):
    ret = 0
    for l in range(3):
        for m in range(c):
            if l == 0:
                ret += mod_color[l][m] * D[m][i]
            elif l == 1:
                ret += mod_color[l][m] * D[m][j]
            else:
                ret += mod_color[l][m] * D[m][k]
    ans = min(ans, ret)


print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, c = LI()
D = LIR(c)
C = LIR(n)
#　mod_color[mod3][color]
mod_color = [[0] * c for _ in range(3)]
for y in range(n):
    for x in range(n):
        mod_color[(y + x + 2) % 3][C[y][x] - 1] += 1


# 30 * 29 * 28
ans = INF
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
# もともとmod0のところをiに、mod1のところをjに、mod2のところをkにする。
            ret = 0
            for l in range(3):
                for m in range(c):
                    if l == 0:
                        ret += mod_color[l][m] * D[m][i]
                    elif l == 1:
                        ret += mod_color[l][m] * D[m][j]
                    else:
                        ret += mod_color[l][m] * D[m][k]
            ans = min(ans, ret)


print(ans)

Submission status: Accepted

Solution code:
#good grid
n,c=map(int,input().split())
mod1=[]
mod2=[]
mod3=[]
change=[0 for j in range(c)]
for i in range(c):
    change[i]=list(map(int,input().split()))
    
for i in range(n):
    s=list(map(int,input().split()))
    for some in range(n):
        if (((some+1)+(i+1))%3)==0:
            mod3.append(s[some])
        if (((some+1)+(i+1))%3)==1:
            mod1.append(s[some])
        if (((some+1)+(i+1))%3)==2:
            mod2.append(s[some])
change_to_some=[[0 for i in range(c)]  for k in range(3)]
for j in range(c):
    a=0
    for k in (mod1):
        a+=change[k-1][j]
    change_to_some[0][j]=a
for j in range(c):
    a=0
    for k in (mod2):
        a+=change[k-1][j]
    change_to_some[1][j]=a
for j in range(c):
    a=0
    for k in (mod3):
        a+=change[k-1][j]
    change_to_some[2][j]=a

anslist=[]
for a in range(c):
    for b in range(c):
        for k in range(c):
            if a!=b and b!=k and a!=k:
                anslist.append(change_to_some[0][a]+change_to_some[1][b]+change_to_some[2][k])
print(min(anslist))

Submission status: Accepted

Solution code:
import itertools
N, C = map(int, input().split())
D = [[int(a) for a in input().split()] for i in range(C)]
X = [[int(a)-1 for a in input().split()] for i in range(N)]
T = [[0] * C for _ in range(3)]
for i in range(N):
    for j in range(N):
        T[(i+j)%3][X[i][j]] += 1

P = [[0] * C for _ in range(3)]
for i in range(3):
    for j in range(C):
        P[i][j] = sum([D[k][j] * T[i][k] for k in range(C)])
    
ans = 1<<100
for a, b, c in itertools.permutations(range(C), 3):
    ans = min(ans, P[0][a] + P[1][b] + P[2][c])
print(ans)

Submission status: Accepted

Solution code:
# D - Good Grid

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

group0, group1, group2 = [0]*C, [0]*C, [0]*C
for row in range(N):
    for col in range(N):
        if (row + col) % 3 == 0:
            group0[c[row][col] -1] += 1
        elif (row + col) % 3 == 1:
            group1[c[row][col] -1] += 1
        else:
            group2[c[row][col] -1] += 1

ans = []
for color0 in range(C):
    for color1 in range(C):
        for color2 in range(C):
            if len(set([color0, color1, color2])) == 3:
                tmp = 0
                for idx in range(C):
                    tmp += D[idx][color0] * group0[idx]
                    tmp += D[idx][color1] * group1[idx]
                    tmp += D[idx][color2] * group2[idx]
                ans.append(tmp)

print(min(ans))

Submission status: Accepted

Solution code:
from itertools import permutations 
n,m=map(int,input().split())
cost=[]
for i in range(m):
    cost.append([int(i) for i in input().split()])
clr=[]
for i in range(n):
    clr.append([int(i) for i in input().split()])
l=[i for i in range(m)]
ind=[[0 for j in range(m)] for i in range(4)]
for i in range(n):
    for j in range(n):
        curr=(i+1+j+1)%3 
        ind[curr][clr[i][j]-1]+=1 
mini=10**9 
for i in range(m):
    for j in range(m):
        for k in range(m):
            if i==j or i==k or j==k:
                continue 
            curr=0 
            for it in range(3): 
                for it1 in range(m): 
                    if it==0:
                        k1=i 
                    elif it==1:
                        k1=j 
                    else:
                        k1=k 
                    curr+=ind[it][it1]*cost[it1][k1] 
            mini=min(mini,curr)
print(mini)

Submission status: Accepted

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

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

nc = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        nc[(i+j)%3][c[i][j]-1] += 1

strangeness = [[sum(nc[k][oldc] * D[oldc][newc] for oldc in range(C))
                for newc in range(C)] for k in range(3)]
ans = 1000 * N * N
for xyz in itertools.product(range(C),repeat=3):
    x, y, z = xyz
    if x != y and y != z and z != x:
        s = sum(strangeness[k][xyz[k]] for k in range(3))
        if s < ans:
            ans = s
print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split())) for i in range(c)]
grid=[list(map(int,input().split())) for i in range(n)]
lst=[[0]*(c+1) for i in range(3)]
for i in range(n):
    for j in range(n):
        num=grid[i][j]
        a=(i+j)%3
        lst[a][num]+=1
li=[[0]*(c+1) for i in range(3)]
for i in range(3):
    u=lst[i]
    for j in range(1,c+1):
        count=0
        for k in range(1,c+1):
            count+=d[k-1][j-1]*u[k]
        li[i][j]=count
ans=float("inf")
for i in range(1,c+1):
    for j in range(1,c+1):
        for k in range(1,c+1):
            if i!=j and j!=k and k!=i:
                a=li[0][i]+li[1][j]+li[2][k]
                ans=min(ans,a)
print(ans)

Submission status: Accepted

Solution code:
import sys

#+++++

def naiseki(va,vb):
	return sum([a*b for a,b in zip(va,vb)])

def main():
	n , c = map(int, input().split())
		
	ccc=[0]*c
	for i in range(c):
		ccc[i]=[0]*c
	for i in range(c):
		temp=list(map(int,input().split()))
		#ccc[i]=temp
		for j,v in enumerate(temp):
			ccc[j][i]=v
		
	pa(ccc)
		
	ddl=[0,0,0]
	for i in range(3):
		ddl[i]=[0]*c
		
	for i in range(1,n+1):
		ll=list(map(int, input().split()))
		for j, color_v in enumerate(ll,start=1):
			group=(i+j)%3
			ddl[group][color_v-1]+=1
			
	pa('_____ddl_____')
	for i in range(3):
		pa(ddl[i])
		
	rrb=[0]*3
	for i in range(3):
		rrb[i]=[0]*c	
		for j in range(c):
			rrb[i][j]=(naiseki(ddl[i], ccc[j]),j)
			
	pa('____rrb_____')
	for i in range(3):
		pa(rrb[i])
	
	c=[0]	* 3
	for i in range(3):
		rrb[i].sort()
		aa=rrb[i][:3]
		c[i]=aa
		
	pa('____ c _____')
	for i in range(3):
		pa(c[i])
		
	mm=None
	for i in range(3):
		for j in range(3):
			for k in range(3):
				ii=c[0][i][1]
				ji=c[1][j][1]
				ki=c[2][k][1]
				if ii !=ji and ji!=ki and ki!=ii:
					temp=c[0][i][0]+c[1][j][0]+c[2][k][0]
					#pa(temp)
					mm = temp if mm is None else min(mm,temp)
					
	return mm
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# ABC099D - Good Grid
import sys
input = sys.stdin.readline

from collections import Counter
from itertools import product


def main():
    N, C = map(int, input().split())
    D = [0] + list([0] + list(map(int, input().split())) for _ in range(C))
    grid = tuple(tuple(map(int, input().split())) for _ in range(N))
    cost = [Counter() for _ in range(3)]
    for i, g in enumerate(grid):  # classify each cell by mod3
        for j in range(3):
            cost[(i + j) % 3].update(g[j::3])
    dist = [[] for _ in range(3)]
    # compute the actual cost to change color
    for i, tgt in product(range(3), range(1, C + 1)):
        cur = sum(D[src][tgt] * cnt for src, cnt in cost[i].items())
        dist[i].append(cur)
    ans = 1 << 60
    # fix two colors and compute the minimum cost
    for i, j in product(range(C), repeat=2):
        if i == j:
            continue
        cur = dist[0][i] + dist[1][j]
        cur += min(x for k, x in enumerate(dist[2]) if k not in (i, j))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099D - Good Grid
import sys
input = sys.stdin.readline

from collections import defaultdict
from itertools import product


def main():
    N, C = map(int, input().split())
    D = [0] + list([0] + list(map(int, input().split())) for _ in range(C))
    grid = tuple(tuple(map(int, input().split())) for _ in range(N))
    cost = {i: defaultdict(int) for i in range(3)}
    for i, g in enumerate(grid):
        for j, x in enumerate(g):
            cost[(i + j) % 3][x] += 1
    dist = [[] for _ in range(3)]
    for i, tgt in product(range(3), range(1, C + 1)):
        cur = sum(D[src][tgt] * cnt for src, cnt in cost[i].items())
        dist[i].append(cur)
    ans = 1 << 60
    for i, j in product(range(C), repeat=2):
        if i == j:
            continue
        cur = dist[0][i] + dist[1][j]
        cur += min(x for k, x in enumerate(dist[2]) if k not in (i, j))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099D - Good Grid
import sys

readline = sys.stdin.buffer.readline

from collections import Counter
from itertools import product


def main():
    N, C = map(int, readline().split())
    D = [0] + list([0] + list(map(int, readline().split())) for _ in range(C))
    grid = tuple(tuple(map(int, readline().split())) for _ in range(N))
    cost = [Counter() for _ in range(3)]
    for i, g in enumerate(grid):
        for j in range(3):
            cost[j].update(g[(j - i) % 3 :: 3])
    dist = [[] for _ in range(3)]
    for i, tgt in product(range(3), range(1, C + 1)):
        cur = sum(D[src][tgt] * cnt for src, cnt in cost[i].items())
        dist[i].append(cur)
    ans = 1 << 60
    for i, j in product(range(C), repeat=2):
        if i == j:
            continue
        cur = dist[0][i] + dist[1][j]
        cur += min(x for k, x in enumerate(dist[2]) if k not in (i, j))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099D - Good Grid
import sys
input = sys.stdin.readline

from collections import Counter
from itertools import product


def main():
    N, C = map(int, input().split())
    D = [0] + list([0] + list(map(int, input().split())) for _ in range(C))
    grid = tuple(tuple(map(int, input().split())) for _ in range(N))
    cost = [Counter() for _ in range(3)]
    for i, g in enumerate(grid):
        for j in range(3):
            cost[j].update(g[(j - i) % 3 :: 3])
    dist = [[] for _ in range(3)]
    for i, target in product(range(3), range(1, C + 1)):
        cur = sum(D[source][target] * cnt for source, cnt in cost[i].items())
        dist[i].append(cur)
    ans = 1 << 60
    for i, j in product(range(C), repeat=2):
        if i == j:
            continue
        cur = dist[0][i] + dist[1][j]
        cur += min(x for k, x in enumerate(dist[2]) if k not in (i, j))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099D - Good Grid
import sys
input = sys.stdin.readline

from collections import Counter
from itertools import product


def main():
    N, C = map(int, input().split())
    D = [0] + list([0] + list(map(int, input().split())) for _ in range(C))
    grid = tuple(tuple(map(int, input().split())) for _ in range(N))
    cost = [Counter() for _ in range(3)]
    for i, g in enumerate(grid):
        for j in range(3):
            cost[j].update(g[(j - i) % 3 :: 3])
    dist = [[] for _ in range(3)]
    for i, target in product(range(3), range(1, C + 1)):
        cur = sum(D[source][target] * cnt for source, cnt in cost[i].items())
        dist[i].append(cur)
    ans = 1 << 60
    for i, j in product(range(C), repeat=2):
        if i == j:
            continue
        cur = dist[0][i] + dist[1][j]
        cur += min(dist[2][k] for k in range(C) if k not in (i, j))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,C = map(int, input().split())
D = [[int(d) for d in input().split()] for _ in range(C)]
clist = [[int(c) for c in input().split()] for _ in range(N)]

L0 = [0]*C
L1 = [0]*C
L2 = [0]*C

for i in range(N):
    for j in range(N):
        if (i+j+2)%3 == 0:
            L0[clist[i][j]-1] += 1
        elif (i+j+2)%3 == 1:
            L1[clist[i][j]-1] += 1
        else:
            L2[clist[i][j]-1] += 1
            
ans = 10**9
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                c = 0
                for l in range(C):
                    c += L0[l]*D[l][i]
                    c += L1[l]*D[l][j]
                    c += L2[l]*D[l][k]
                ans = min(ans, c)
                
print(ans)

Submission status: Accepted

Solution code:
n, c = [int(i) for i in 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)]
 
X = [[0]*c for i in range(3)]
 
for i in range(n):
    for j in range(n):
        X[(i+j+2)%3][C[i][j]-1] += 1
 
cost = [[0]*c for i in range(3)]
 
for i in range(c):
    for j in range(c):
        cost[0][j] += X[0][i] * D[i][j]
        cost[1][j] += X[1][i] * D[i][j]
        cost[2][j] += X[2][i] * D[i][j]
 
ans = []
 
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.append(cost[0][i] + cost[1][j] + cost[2][k])
 
print(min(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
N, C = map(int, input().split())

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

d = [defaultdict(int) for i in range(3)]


for i in range(N):
    c = [int(x) for x in input().split()]
    for j in range(N):
        for k in range(C):
            d[(i+j) % 3][k] += D[c[j]-1][k]
# print(d)

ans = 10**9
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, d[0][i]+d[1][j]+d[2][k])

print(ans)

Submission status: Accepted

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

group = [[0] * C for _ in range(3)]
for i in range(N):
    for j in range(N):
        group[(i + j) % 3][c[i][j] - 1] += 1

def calc(g, color): #g: groupをcolorに変える違和感を返す
    cost = 0
    for i in range(C):
        cost += group[g][i] * D[i][color]
    return cost

# for i in group:
#     print (i)

ans0 = []
for i in range(C):
    ans0.append((calc(0, i), i))
ans0.sort()

ans1 = []
for i in range(C):
    ans1.append((calc(1, i), i))
ans1.sort()

ans2 = []
for i in range(C):
    ans2.append((calc(2, i), i))
ans2.sort()

# print (ans0)
# print (ans1)
# print (ans2)

ans = 10 ** 18
for i in range(3):
    for j in range(3):
        for k in range(3):
            if ans0[i][1] != ans1[j][1] and ans1[j][1] != ans2[k][1] and ans2[k][1] != ans0[i][1]:
                ans = min(ans, ans0[i][0] + ans1[j][0] + ans2[k][0])

print (ans)

Submission status: Accepted

Solution code:
import itertools



def resolve():
    N,C=map(int,input().split())
    cost=[[int(i) for i in input().split()] for j in range(C)]
    count=[[0 for i in range(C)] for i in range(3)]
    grid=[[int(i)-1 for i in input().split()] for j in range(N)]
    for i in range(N):
        for j in range(N):
            count[(i+j)%3][grid[i][j]]+=1
    seq=list(range(C))
    mx=2**29
    for i in itertools.permutations(seq,3):
        temp=0
        temp+=sum([cost[j][i[0]]*count[0][j] for j in range(C)])
        temp+=sum([cost[j][i[1]]*count[1][j] for j in range(C)])
        temp+=sum([cost[j][i[2]]*count[2][j] for j in range(C)])
        mx=min(mx,temp)
    print(mx)

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)]
lis_c=[list(map(int,input().split())) for i in range(n)]
ans=float("inf")
cnt=[[0]*c for i in range(3)]
for i in range(n):
    for j in range(n):
        cnt[(i+j)%3][lis_c[i][j]-1]+=1
# print(cnt)
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i==j or j==k or i==k:
                continue
            tmp=0
            color=[i,j,k]
            for l in range(3):
                for m in range(c):
                    tmp+=cnt[l][m]*d[m][color[l%3]]
            ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import*
n,c=map(int,input().split());d=[list(map(int,input().split()))for _ in range(c)];e=[c*[0]for _ in range(3)]
for i in range(n):
  s=list(map(int,input().split()))
  for j in range(n):e[(i+j)%3][s[j]-1]+=1
if n==1:print(0);exit()
print(min(sum(d[t][i]*e[0][t]+d[t][j]*e[1][t]+d[t][k]*e[2][t]for t in range(c))for i,j,k in permutations((i for i in range(c)),3)))

Submission status: Accepted

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

for i in range(N):
    c.append(list(map(int, input().split())))

color = [[0 for i in range(C+1)] for j in range(3)]
for i in range(N):
    for j in range(N):
        color[(i+j)%3][c[i][j]] += 1

ans = 10000000000
for i in range(1, C+1):
    for j in range(1, C+1):
        for k in range(1, C+1):
            if i == j or j == k or k == i:
                continue
            temp = 0
            for b in range(1, C+1):
                temp += cost[b-1][i-1] * color[0][b]
            for b in range(1, C+1):
                temp += cost[b-1][j-1] * color[1][b]
            for b in range(1, C+1):
                temp += cost[b-1][k-1] * color[2][b]
            ans = min(temp, ans)

print(ans)

Submission status: Accepted

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

color_count = [[0]*c for i in range(3)]
for i in range(n):
    for j in range(n):
        color_count[(i+j)%3][C[i][j]-1] += 1

min_wrongness = 10**9

for i in range(c):
    for j in range(c):
        for k in range(c):
            if i!=j and j!=k and k!=i:
                wrongness = 0
                for l in range(3):
                    for m in range(c):
                        if l == 0:
                            wrongness += D[m][i]*color_count[l][m]
                        elif l == 1:
                            wrongness += D[m][j]*color_count[l][m]
                        else:
                            wrongness += D[m][k]*color_count[l][m]
                min_wrongness = min(min_wrongness,wrongness)
                
print(min_wrongness)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, C = map(int, input().split())
    D = np.array([list(map(int, input().split())) for i in range(C)])
    board = [list(map(int, input().split())) for i in range(N)]

    # cost[i][j] := mod3==iのグループを色jにする際の違和感の総和
    cost = np.zeros((3, C), dtype=int)
    for i in range(N):
        for j in range(N):
            cost[(i+j)%3] += D[board[i][j] - 1]

    ans = int(1e20)
    for i in range(C):
        for j in range(C):
            if i == j:
                continue
            for k in range(C):
                if k==i or k==j:
                    continue
                ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, C = map(int, input().split())
    D = np.array([list(map(int, input().split())) for i in range(C)])
    board = [list(map(int, input().split())) for i in range(N)]

    # cost[i][j] := mod3==iのグループを色jにする際の違和感の総和
    cost = np.zeros((3, C), dtype=int)
    count = np.zeros((3, C), dtype=int)
    for i in range(N):
        for j in range(N):
            count[(i + j)%3][board[i][j] - 1] += 1
    for i in range(3):
        for j in range(C):
            cost[i] += D[j] * count[i][j]

    ans = int(1e20)
    for i in range(C):
        for j in range(C):
            if i == j:
                continue
            for k in range(C):
                if k==i or k==j:
                    continue
                ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N,C = map(int,input().split())
D = [[0 for _ in range(C)]]
for _ in range(C):
    row = list(map(int,input().split()))
    row.insert(0,0)
    D.append(row)
A = [[0 for _ in range(N)]]
for _ in range(N):
    row = list(map(int,input().split()))
    row.insert(0,0)
    A.append(row)
G = {0:{c:0 for c in range(1,C+1)},1:{c:0 for c in range(1,C+1)},2:{c:0 for c in range(1,C+1)}}
for i in range(1,N+1):
    for j in range(1,N+1):
        a = (i+j)%3
        G[a][A[i][j]] += 1
B = {0:{c:0 for c in range(1,C+1)},1:{c:0 for c in range(1,C+1)},2:{c:0 for c in range(1,C+1)}}
for c in range(1,C+1):
    for i in range(3):
        for d in range(1,C+1):
            B[i][c] += G[i][d]*D[d][c]
dmin = 10**10
for x in itertools.permutations(range(1,C+1),3):
        dmin = min(dmin,B[0][x[0]]+B[1][x[1]]+B[2][x[2]])
print(dmin)

Submission status: Accepted

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

ccount = [[0] * C for _ in range(3)]
for y in range(N) :
    for x in range(N) :
        ccount[(x + y) % 3][c[y][x]-1] += 1

ccost = [[0] * C for _ in range(3)]
for i, cc in enumerate(ccount) :
    m = float('inf')
    for j in range(C) :
        ccost[i][j] = sum([cc[k] * D[k][j] for k in range(C)])
        
ret = float('inf')
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
            ret = min(ret, ccost[0][i] + ccost[1][j] + ccost[2][k])
print(ret)

Submission status: Accepted

Solution code:
import collections
import itertools

n, c = map(int, input().split())
ds = [list(map(int, input().split())) for _ in range(c)]
colors = [collections.Counter() for _ in range(3)]
for i in range(n):
    for j, color in enumerate(map(int, input().split())):
        colors[(i + j) % 3][color - 1] += 1
res = float('inf')
for cs in itertools.permutations(range(c), 3):
    s = 0
    for i in range(3):
        for k, v in colors[i].items():
            s += ds[k][cs[i]] * v
    res = min(res, s)
print(res)

Submission status: Accepted

Solution code:
import collections
import itertools

n, c = map(int, input().split())
ds = [list(map(int, input().split())) for _ in range(c)]
colors = [collections.Counter() for _ in range(3)]
for i in range(n):
    for j, color in enumerate(map(int, input().split())):
        colors[(i + j) % 3][color - 1] += 1
res = float('inf')
for cs in itertools.combinations(range(c), 3):
    for cs2 in itertools.permutations(cs):
        s = 0
        for i in range(3):
            for k, v in colors[i].items():
                s += ds[k][cs2[i]] * v
        res = min(res, s)
print(res)

Submission status: Accepted

Solution code:
# 少ないときは総当たりゲーミング

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

g = [[0]*C for _ in range(3)]
for y, e in enumerate(E):
    for x, e_i in enumerate(e):
        g[(x+y)%3][e_i-1] += 1
# print(g)

min_cost = 10**18
for c0 in range(C):
    for c1 in range(C):
        for c2 in range(C):
            if len({c0, c1, c2}) < 3:
                continue
            colors = [c0, c1, c2]
            # print(colors)
            cost = 0
            for i, g_i in enumerate(g):
                for j, g_j in enumerate(g_i):
                    # print(i, (j, colors[i]), D[j][colors[i]])
                    cost += D[j][colors[i]]*g_j
            min_cost = min(min_cost, cost)

print(min_cost)