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:
#!/usr/bin/env python
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)]

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

points = []
for i in range(3):
    row = []
    for color in range(1, c+1):
        x = 0
        for j, m in enumerate(grid[i]):
            x += m * D[j][color-1]
        row.append([x, color])
    points.append(row)

for i in range(3):
    points[i].sort()

ans = 1000*n*n
for i in range(27):
    x = points[0][i//9]
    y = points[1][i//3%3]
    z = points[2][i%3]
    if x[1] == y[1] or y[1] == z[1] or z[1] == x[1]:
        continue
    ans = min(ans, x[0]+y[0]+z[0])
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c_map = [list(map(int, input().split())) for _ in range(N)]
count = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        c = c_map[i][j]
        amari = (i+j)%3
        count[amari][c-1]+=1
ans = float('inf')
for i in range(C):
    for j in range(C):
        for k in range(C):
            tmp = 0
            if i == k or j == k or i==j:
                continue
            else:
                for l in range(C):
                    tmp+=count[0][l]*D[l][i]
                    tmp+=count[1][l]*D[l][j]
                    tmp+=count[2][l]*D[l][k]
            ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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)]
cnt = [[0] * C for i in range(3)]
for i in range(N):
    for j in range(N):
        cnt[(i + j + 2) % 3][c[i][j] - 1] += 1
ans = float('inf')
for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            tmp = 0
            for i in range(3):
                for j in range(C):
                    tmp += d[j][[c1, c2, c3][i]] * cnt[i][j]
            ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
tot = 10**12
n,c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
clr = [list(map(int, input().split())) for _ in range(n)]
l = [ddict(int) for _ in range(3)]
for y in range(n):
  for x in range(n):
    l[(x+y)%3][clr[y][x]] += 1
for c1 in range(c):
  for c2 in range(c):
    if c1 == c2:
      continue
    for c3 in range(c):
      if c1==c3 or c2==c3:
        continue
      ctot = 0
      cl = [c1,c2,c3]
      for i in range(3):
        for x in l[i]:
          ctot += d[x-1][cl[i]]*l[i][x]
      if tot > ctot:
        tot = ctot
print(tot)

Submission status: Accepted

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

a = [[0]*c for _ in range(3)]
b = [[[0,i] for i in range(c)] for _ in range(3)]

for i in range(n):
  l = list(map(int,input().split()))
  for j in range(n):
    a[(i+j)%3][l[j]-1] += 1
    
for i in range(3):
  for k in range(c):
    b[i][k][0] = sum([a[i][t]*d[t][k] for t in range(c)])
#print(a)
#print(b)
p = [[],[],[]]
for i in range(3):
  p[i] = sorted(b[i])[:3]
m = []
for t in p[0]:
  for s in p[1]:
    for u in p[2]:
      if (t[1] != s[1]) and (t[1] != u[1]) and (s[1] != u[1]):
        m.append(t[0]+s[0]+u[0])
print(min(m))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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)]

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

for i_y in range(N):
    for i_x in range(N):
        colorcnt[(i_x + i_y) % 3][c[i_y][i_x] - 1] += 1

# print("#", colorcnt)            
            
pentab = [[0] * C for _ in range(3)]
for grp in range(3):
    for c_dst in range(C):
        penalty = 0
        for c_src in range(C):
            penalty += colorcnt[grp][c_src] * D[c_src][c_dst]
        pentab[grp][c_dst] = penalty

# print("#", pentab)

import itertools

ans = 10 ** 18
for c_ans in itertools.permutations(range(C), 3):
    ans_tmp = sum([pentab[i][c_ans[i]] for i in range(3)])
    if ans > ans_tmp:
        ans = ans_tmp

print(ans)

Submission status: Accepted

Solution code:
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()))

cost0 = [0] * C
cost1 = [0] * C
cost2 = [0] * C
for color in range(C):
    for h in range(N):
        for w in range(N):
            mod = (h + w) % 3
            if mod == 0:
                cost0[color] += D[grid[h][w] - 1][color]
            elif mod == 1:
                cost1[color] += D[grid[h][w] - 1][color]
            else:
                cost2[color] += D[grid[h][w] - 1][color]

ans = float('inf')
for i in range(C):
    j_list = list(range(C))
    j_list.remove(i)
    for j in j_list:
        k_list = list(range(C))
        k_list.remove(i)
        k_list.remove(j)
        for k in k_list:
            ans = min(ans, cost0[i] + cost1[j] + cost2[k])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
p = [defaultdict(int), defaultdict(int), defaultdict(int)]
for i in range(n):
    ci = list(map(int, input().split()))
    for j, cj in enumerate(ci):
        k = (i + j + 2) % 3
        p[k][cj] += 1
ans = []
for i in range(1, c + 1):
    x = 0
    for ci, ti in p[0].items():
        x += D[ci - 1][i - 1] * ti

    for j in range(1, c + 1):
        if j == i:
            continue
        y = 0
        for cj, tj in p[1].items():
            y += D[cj - 1][j - 1] * tj

        for k in range(1, c + 1):
            if k in [i, j]:
                continue
            z = 0
            for ck, tk in p[2].items():
                z += D[ck - 1][k - 1] * tk
            ans.append(x + y + z)

print(min(ans))

Submission status: Accepted

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

di = [{}, {}, {}]

for i in range(N) :
    for j in range(N) :
        num = (i+j) % 3
        before = L[i][j] - 1
        
        if before not in di[num] :
            di[num][before] = 1
        else :
            di[num][before] += 1

B = []

for d in di :
    A = []
    for after in range(C) :
        calc = 0
        for before in d :
            calc += D[before][after] * d[before]
        A.append([calc,after])

    A = sorted(A,key=lambda x:x[0],reverse=False)[:3]
    B.append(A)
    
ans = float("inf")

for i in range(3) :
    for j in range(3) :
        for k in range(3) :
            if (B[0][i][1] - B[1][j][1]) * (B[1][j][1] - B[2][k][1]) * (B[2][k][1] - B[0][i][1]) == 0 :
                continue
            
            ans = min(ans, B[0][i][0] + B[1][j][0] + B[2][k][0])

print(ans)

Submission status: Accepted

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

d0 = {}
d1 = {}
d2 = {}

for i in range(N) :
    for j in range(N) :
        before = L[i][j] - 1
        
        if (i+j) % 3 == 0 :
            if before not in d0 :
                d0[before] = 1
            else :
                d0[before] += 1

        elif (i+j) % 3 == 1 :
            if before not in d1 :
                d1[before] = 1
            else :
                d1[before] += 1

        else :
            if before not in d2 :
                d2[before] = 1
            else :
                d2[before] += 1


B = []

for d in [d0,d1,d2] :
    A = []
    for after in range(C) :
        calc = 0
        for before in d :
            calc += D[before][after] * d[before]
        A.append([calc,after])

    A = sorted(A,key=lambda x:x[0],reverse=False)[:3]
    B.append(A)
    
    

ans = float("inf")

for i in range(3) :
    for j in range(3) :
        for k in range(3) :
            if (B[0][i][1] - B[1][j][1]) * (B[1][j][1] - B[2][k][1]) * (B[2][k][1] - B[0][i][1]) == 0 :
                continue
            
            ans = min(ans, B[0][i][0] + B[1][j][0] + B[2][k][0])

print(ans)

Submission status: Accepted

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

d0 = {}
d1 = {}
d2 = {}

for i in range(N) :
    for j in range(N) :
        before = L[i][j] - 1
        
        if (i+j) % 3 == 0 :
            if before not in d0 :
                d0[before] = 1
            else :
                d0[before] += 1

        elif (i+j) % 3 == 1 :
            if before not in d1 :
                d1[before] = 1
            else :
                d1[before] += 1

        else :
            if before not in d2 :
                d2[before] = 1
            else :
                d2[before] += 1



A0 = []
A1 = []
A2 = []

for after in range(C) :
    calc = 0
    for before in d0 :
        calc += D[before][after] * d0[before]
    A0.append([calc,after])

for after in range(C) :
    calc = 0
    for before in d1 :
        calc += D[before][after] * d1[before]
    A1.append([calc,after])

for after in range(C) :
    calc = 0
    for before in d2 :
        calc += D[before][after] * d2[before]
    A2.append([calc,after])
    
A0 = sorted(A0,key=lambda x:x[0],reverse=False)[:3]
A1 = sorted(A1,key=lambda x:x[0],reverse=False)[:3]
A2 = sorted(A2,key=lambda x:x[0],reverse=False)[:3]
B = [A0,A1,A2]

ans = float("inf")

for i in range(3) :
    for j in range(3) :
        for k in range(3) :
            if (B[0][i][1] - B[1][j][1]) * (B[1][j][1] - B[2][k][1]) * (B[2][k][1] - B[0][i][1]) == 0 :
                continue
            
            ans = min(ans, B[0][i][0] + B[1][j][0] + B[2][k][0])

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

x = [0 for i in range(c)]
y = [0 for i in range(c)]
z = [0 for i in range(c)]

for i in range(n):
    for j in range(n):
        if (i+j+2)%3 == 0:
            x[e[i][j]-1] += 1
        elif (i+j+2)%3 == 1:
            y[e[i][j]-1] += 1
        else:
            z[e[i][j]-1] += 1

f = [i for i in range(c)]

g = list(itertools.permutations(f,3))

ans = float('inf')
for i in range(len(g)):
    a = 0
    for j in range(c):
        a += d[j][g[i][0]]*x[j] + d[j][g[i][1]]*y[j] + d[j][g[i][2]]*z[j]
    ans = min(ans, a)

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int, sys.stdin.readline().split())) for _ in range(C)]
CM = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

CG = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        nc = CM[i][j] - 1
        for c in range(C):
            CG[(i+j)%3][c] += D[nc][c]
ans = 10**10
for c1, c2, c3 in permutations(range(C), 3):
    ans = min(ans, CG[0][c1] + CG[1][c2] + CG[2][c3])
print(ans)

Submission status: Accepted

Solution code:
def sol():
    n,c=map(int,input().split())
    d=[[int(i) for i in input().split()] for i in range(c)]
    t=[[int(i) for i in input().split()] for i in range(n)]
    x0,x1,x2={},{},{}
    for p in range(n**2):
        h,w=p//n,p%n
        x=(h+w)%3
        o=t[h][w]-1
        if x==0:
            if o in x0: x0[o]+=1
            else: x0[o]=1
        if x==1:
            if o in x1: x1[o]+=1
            else: x1[o]=1
        if x==2:
            if o in x2: x2[o]+=1
            else: x2[o]=1
    ans=-1
    for a in range(c**2):
        for k in range(c):
            i,j=a//c,a%c
            q=[i,j,k]
            if len(set(q))<3: continue
            chk=0
            for p in x0:
                chk+=d[p][q[0]]*x0[p]
            for p in x1:
                chk+=d[p][q[1]]*x1[p]
            for p in x2:
                chk+=d[p][q[2]]*x2[p]
            if ans==-1: ans=chk
            ans=min(ans,chk)

    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N,C = map(int,input().split())
D = np.array([[int(x) for x in input().split()] for _ in range(C)])
c = np.array([[int(x) for x in input().split()] for _ in range(N)])
c -= 1
cls = np.zeros_like(c)

for i,j in itertools.product([0,1,2],[0,1,2]):
  cls[i::3,j::3] = (i+j)%3

# 色の分布 cls, color -> count
color_dist = np.zeros((3,C),dtype=np.int64)
for i in range(3):
  for j in range(C):
    color_dist[i,j] = ((cls == i) & (c == j)).sum()

min_cost = np.inf

for a,b,c in itertools.product(range(C),repeat = 3):
  if a == b or a == c or b == c:
    continue
  cost = 0
  cost += (color_dist[0] * D[:,a]).sum()
  cost += (color_dist[1] * D[:,b]).sum()
  cost += (color_dist[2] * D[:,c]).sum()
  min_cost = min(cost,min_cost)
  
print(min_cost)

Submission status: Accepted

Solution code:
import itertools
n,c=map(int,input().split())
C=[i for i in range(c)]
D=[]
for i in range(c):
  Di=[int(i) for i in input().split()]
  D.append(Di)
C0,C1,C2=[],[],[]
for i in range(n):
  ci=[int(i) for i in input().split()]
  for j in range(n):
    if (i+j)%3==0:
      C2.append(ci[j])
    elif (i+j)%3==1:
      C0.append(ci[j])
    else:
      C1.append(ci[j])
C0C,C1C,C2C=[],[],[]
for i in range(c):
  c0,c1,c2=0,0,0
  for j0 in range(len(C0)):
    c0+=D[C0[j0]-1][i]
  for j1 in range(len(C1)):
    c1+=D[C1[j1]-1][i]
  for j2 in range(len(C2)):
    c2+=D[C2[j2]-1][i]
  C0C.append(c0)
  C1C.append(c1)
  C2C.append(c2)
ans=float("inf")
for i,j,k in itertools.permutations(C,3):
  ans=min(ans,C0C[i]+C1C[j]+C2C[k])
print(ans)

Submission status: Accepted

Solution code:
# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = ii2nnn(C)
    c = ii2nnn(N)
    E = [[0] * C for _ in range(3)]
    for i in range(N):
        for j in range(N):
            before = c[i][j]
            e = (i+j) % 3
            for after in range(1, C+1):
                E[e][after-1] += D[before-1][after-1]
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = E[0][c1] + E[1][c2] + E[2][c3]
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
D=[]
r0=[]
r1=[]
r2=[]
for i in range(c):
    sub_list=list(map(int,input().split()))
    D.append(sub_list)
    r0.append(0)
    r1.append(0)
    r2.append(0)
c_list=[]
for i in range(n):
    sub_list=list(map(int,input().split()))
    c_list.append(sub_list)
for i in range(n):
    for j in range(n):
        if (i+j)%3==0:
            r0[c_list[i][j]-1]=r0[c_list[i][j]-1]+1
        elif (i+j)%3==1:
            r1[c_list[i][j]-1]=r1[c_list[i][j]-1]+1
        else:
            r2[c_list[i][j]-1]=r2[c_list[i][j]-1]+1
Min=10**10
for i in range(c):
    for j in range(i+1,c):
        for k in range(j+1,c):
            pat=[(i,j,k),(i,k,j),(j,i,k),(j,k,i),(k,i,j),(k,j,i)]
            for x in pat:
                Sum=0
                for y in range(c):
                    Sum=Sum+r0[y]*D[y][x[0]]+r1[y]*D[y][x[1]]+r2[y]*D[y][x[2]]
                Min=min(Min,Sum)
print(Min)

Submission status: Accepted

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

g0, g1, g2 = [0]*C, [0]*C, [0]*C
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            g0[c[i][j]-1] += 1
        elif (i+j)%3 == 1:
            g1[c[i][j]-1] += 1
        elif (i+j)%3 == 2:
            g2[c[i][j]-1] += 1

ans = 10**20
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                # iはg0, jはg1, kはg2用の色
                tmp = 0
                for l in range(C):
                    tmp += D[l][i]*g0[l]
                    tmp += D[l][j]*g1[l]
                    tmp += D[l][k]*g2[l]
                ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import*
n,c=map(int,input().split())
cost=[list(map(int,input().split()))for i in range(c)]
d=[[0]*c for i in range(3)]
for i in range(n):
    for j,v in enumerate(map(int,input().split())):
        d[(i+j)%3][v-1]+=1
print(min(sum(cost[j][cmb[i]]*d[i][j]for j in range(c)for i in range(3))for cmb in permutations(range(c),3)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def calc_(order, d):
    ret = 0
    for i in range(3):
        target = order[i]
        ret += d[i][target]
    return ret

def calc(G, target, D):
    ret = 0
    for elm in G:
        ret += D[elm - 1][target]
    return ret

def dfs(idx, current, used, d):
    if idx == 3:
        ret = calc_(current, d)
        return ret
    ret = float('inf')
    for i, u in enumerate(used):
        if not u:
            used[i] = True
            tmp = dfs(idx + 1, current + [i], used, d)
            ret = min(ret, tmp)
            used[i] = False
    return ret

def solve(N: int, C: int, D: "List[List[int]]", c: "List[List[int]]"):
    groups = [[] for _ in range(3)]
    for i in range(N):
        for j in range(N):
            cc = c[i][j]
            groups[(i + j) % 3].append(cc)
    #print(groups)
    d = [[] for _ in range(3)]
    for i, G in enumerate(groups):
        for j in range(C):
            d[i].append(calc(G, j, D))
    ret = dfs(0, [], [False] * C, d)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = [ [ int(next(tokens)) for _ in range(C) ] for _ in range(C) ]  # type: "List[List[int]]"
    c = [ [ int(next(tokens)) for _ in range(N) ] for _ in range(N) ]  # type: "List[List[int]]"
    solve(N, C, D, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [[int(x)-1 for x in input().split()] for _ in range(n)]
C0,C1,C2 = [0]*c,[0]*c,[0]*c
for i in range(n):
    for j in range(n):
        if (i+j)%3 == 0:
            C0[C[i][j]] += 1
        elif (i+j)%3 == 1:
            C1[C[i][j]] += 1
        else:
            C2[C[i][j]] += 1
ans = inf
for (i,j,k) in permutations(range(c),3):
    cur = 0
    for l in range(c):
        cur += D[l][i]*C0[l]+D[l][j]*C1[l]+D[l][k]*C2[l]
    ans = min(ans,cur)
print(ans)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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)]
C0,C1,C2 = [0]*c,[0]*c,[0]*c
for i in range(n):
    for j in range(n):
        if (i+j)%3 == 0:
            C0[C[i][j]-1] += 1
        elif (i+j)%3 == 1:
            C1[C[i][j]-1] += 1
        else:
            C2[C[i][j]-1] += 1
ans = inf
for (i,j,k) in permutations(range(c),3):
    cur = 0
    for l in range(c):
        cur += D[l][i]*C0[l]+D[l][j]*C1[l]+D[l][k]*C2[l]
    ans = min(ans,cur)
print(ans)

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n, c = intin()
    dlistlist = [None]
    for _ in range(c):
        dlist = [None]
        dlist.extend(intina())
        dlistlist.append(dlist)
    clistlist = []
    for _ in range(n):
        clistlist.append(intina())

    costs0 = []
    costs1 = []
    costs2 = []

    for cc in range(1, c + 1):

        costs = [0, 0, 0]

        for i in range(n):
            for j in range(n):
                costs[(i + j) % 3] += dlistlist[clistlist[i][j]][cc]

        costs0.append((costs[0], cc))
        costs1.append((costs[1], cc))
        costs2.append((costs[2], cc))

    costs0.sort()
    costs1.sort()
    costs2.sort()

    ans = float('inf')
    for cost0, c0 in costs0[:3]:
        for cost1, c1 in costs1[:3]:
            for cost2, c2 in costs2[:3]:
                if c0 == c1 or c1 == c2 or c2 == c0:
                    continue
                ans = min(ans, cost0 + cost1 + cost2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sections = [[0 for _ in range(C)] for _ in range(3)]
for y in range(N):
    for x in range(N):
        sections[(x+y+2)%3][G[y][x]-1] += 1

discomfort = [[0 for _ in range(C)] for _ in range(3)]
for section in range(3):
    for target in range(C):
        for source in range(C):
            if source != target:
                discomfort[section][target] += D[source][target] * sections[section][source]
ans = float('inf')
for i in range(C):
    for j in range(C):
        if i != j:
            for k in range(C):
                if k not in [i, j]:
                    ans = min(ans, discomfort[0][i]+discomfort[1][j]+discomfort[2][k])
print(ans)

Submission status: Accepted

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)]
color=[{} for i in range(3)]
for i in range(N):
    for j in range(N):
        x=(i+j)%3
        if c[i][j] in color[x]:
            color[x][c[i][j]]+=1
        else:
            color[x][c[i][j]]=1
ans=10**9
for i in range(C):
    for j in range(C):
        if j==i:
            continue
        for k in range(C):
            if k==j or k==i:
                continue
            s0=sum([D[x-1][i]*color[0][x] for x in color[0].keys()])
            s1=sum([D[x-1][j]*color[1][x] for x in color[1].keys()])
            s2=sum([D[x-1][k]*color[2][x] for x in color[2].keys()])
            ans=min(ans,s0+s1+s2)
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict

def calc_cost(data_iwakan, color_dic, ind):
    cost = 0
    for ele in color_dic.keys():
        if ind == ele:
            continue
        cost += color_dic[ele] * data_iwakan[ele - 1][ind - 1]
    return cost



def main():
    masu_num, color_num = map(int, input().split())
    data_iwakan = [list(map(int, input().split())) for i in range(color_num)]
    data_masu = [list(map(int, input().split())) for i in range(masu_num)]

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

    for i in range(masu_num):
        for j in range(masu_num):
            color_dic[(i + j + 2) % 3][data_masu[i][j]] += 1

    ans = 10 ** 12

    for i in range(color_num):
        for j in range(color_num):
            for k in range(color_num):
                if i == j:
                    continue
                if i == k:
                    continue
                if j == k:
                    continue
                kari_ans = 0
                kari_ans += calc_cost(data_iwakan, color_dic[0], i)
                kari_ans += calc_cost(data_iwakan, color_dic[1], j)
                kari_ans += calc_cost(data_iwakan, color_dic[2], k)

                if ans > kari_ans:
                    ans = kari_ans

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(c)]
Grid=[list(map(int,input().split())) for _ in range(n)]
Counter=[[0]*c for _ in range(3)]
for i in range(n):
    for j in range(n):
        Counter[(i+j)%3][Grid[i][j]-1]+=1

Cost=[[0]*c for _ in range(3)]
for i in range(3):
    for j in range(c):
        for k,cnt in enumerate(Counter[i]):
            Cost[i][j]+=D[k][j]*cnt
ans=float('inf')
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
            ans=min(ans,Cost[0][i]+Cost[1][j]+Cost[2][k])
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
def main():
    N,C=map(int,raw_input().split())
    D=[None]
    for _ in range(C):
        D.append([None]+map(int,raw_input().split()))
    c=[]
    for _ in range(N):
        c.append(map(int,raw_input().split()))
    # F[C][mod]
    F=[[0,0,0] for _ in range(31)]
    # m[mod] = [c[mod]]
    m=[[] for i in range(3)]
    for i in range(N):
        for j in range(N):
            m[(i+j)%3].append(c[i][j])

    for mod in range(3):
        for color in range(1,C+1):
            val=0
            for mm in m[mod]:
                F[color][mod]+=D[mm][color]

    ans=1145141919810
    if N==1:
        print(0)
        return
    for c0 in range(1,C+1):
        for c1 in range(1,C+1):
            for c2 in range(1,C+1):
                if c0==c1 or c1==c2 or c2==c0:continue  
                ans=min(ans,F[c0][0]+F[c1][1]+F[c2][2])
    print(ans)





main()

Submission status: Accepted

Solution code:
#coding:utf-8
def main():
    N,C=map(int,raw_input().split())
    D=[None]
    for _ in range(C):
        D.append([None]+map(int,raw_input().split()))
    c=[]
    for _ in range(N):
        c.append(map(int,raw_input().split()))
    # F[C][mod]
    F=[[0,0,0] for _ in range(31)]
    # m[mod] = [c[mod]]
    m=[[] for i in range(3)]
    for i in range(N):
        for j in range(N):
            m[(i+j)%3].append(c[i][j])

    for mod in range(3):
        for color in range(1,C+1):
            val=0
            for mm in m[mod]:
                F[color][mod]+=D[mm][color]

    ans=1145141919810
    if N==1:
        for c0 in range(1,C+1):
            print(0)
            return

    for c0 in range(1,C+1):
        for c1 in range(1,C+1):
            for c2 in range(1,C+1):
                if c0==c1 or c1==c2 or c2==c0:continue  
                ans=min(ans,F[c0][0]+F[c1][1]+F[c2][2])
    print(ans)





main()