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:
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)]
g=[[] for i in range(3)]
for i in range(n):
    for j in range(n):
        g[(i+j+2)%3].append(c_[i][j]-1)
#print(g)
'''
for i in range(c):
    for j in range(c):
        for k in range(c):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(d)
'''
f=[[] for i in range(3)]
for i in range(3):
    for j in range(c):
        x=0
        for k in g[i]:
            x+=d[k][j]
        f[i].append((j,x))
    f[i]=sorted(f[i],key=lambda x:x[1])[:3]
ans=[]
#print()
for i in f[0]:
    for j in f[1]:
        for k in f[2]:
            if i[0]!=j[0] and k[0]!=j[0] and i[0]!=k[0]:
                #print(i[0],j[0],k[0])
                #print(i[1],j[1],k[1])
                ans.append(i[1]+j[1]+k[1])
print(min(ans))

Submission status: Accepted

Solution code:
N,C=map(int,input().split())

Dmat=[]
for i in range(C):
  array=list(map(int,input().split()))
  Dmat.append(array)
#print(Dmat)

grid_list=[{},{},{}]
for i in range(N):
  array=list(map(int,input().split()))
  for j in range(N):
    c=array[j]-1    
    mod=(i+j)%3
    if c in grid_list[mod]:
      grid_list[mod][c]+=1
    else:
      grid_list[mod][c]=1
#print(grid_list)

min_cost=10**9
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
          
      cost=0 
      for c,num in grid_list[0].items():
        cost+=Dmat[c][i]*num
      for c,num in grid_list[1].items():
        cost+=Dmat[c][j]*num
      for c,num in grid_list[2].items():
        cost+=Dmat[c][k]*num
          
      if cost<min_cost:
        #print(i,j,k,cost)
        min_cost=cost
          
print(min_cost)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())

Dmat=[]
for i in range(C):
  array=list(map(int,input().split()))
  Dmat.append(array)
#print(Dmat)

cmat=[]
for i in range(N):
  array=list(map(int,input().split()))
  cmat.append(array)
#print(cmat)
grid_list=[{},{},{}]
for i in range(N):
  for j in range(N):
    c=cmat[i][j]-1
    mod=(i+j)%3
    if c in grid_list[mod]:
      grid_list[mod][c]+=1
    else:
      grid_list[mod][c]=1
#print(grid_list)

min_cost=10**9
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
          
      cost=0 
      for c in grid_list[0]:
        num=grid_list[0][c]
        cost+=Dmat[c][i]*num
      for c in grid_list[1]:
        num=grid_list[1][c]
        cost+=Dmat[c][j]*num
      for c in grid_list[2]:
        num=grid_list[2][c]
        cost+=Dmat[c][k]*num
          
      if cost<min_cost:
        #print(i,j,k,cost)
        min_cost=cost
          
print(min_cost)

Submission status: Accepted

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

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

diff = [[0]*(C+1) for _ in range(3)]

for i, naname in enumerate(diago):
    for color in range(1, C+1):
        for j, cell in enumerate(naname):
            diff[i][color] += D[j-1][color-1] * cell
#print(diff)

candicate = []
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:
                candicate.append(diff[0][i]+diff[1][j]+diff[2][k])
print(min(candicate))

Submission status: Accepted

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

def main():
    n, nc = map(int, input().split())
    d = [list(map(int, input().split())) for i in range(nc)]
    c = [list(map(int, input().split())) for i in range(n)]

    cnt = [[0 for _ in range(nc)] for eta in range(3)]
    for i in range(n):
        for j in range(n):
            eta = (i + j) % 3
            cnt[eta][c[i][j] - 1] += 1

    iwamin = 10 ** 9
    for c1 in range(nc):
        for c2 in range(nc):
            for c3 in range(nc):
                if len(set([c1, c2, c3])) < 3:
                    continue
                iwa = 0
                for c4 in range(nc):
                    iwa += cnt[0][c4] * d[c4][c1]
                    iwa += cnt[1][c4] * d[c4][c2]
                    iwa += cnt[2][c4] * d[c4][c3]
                iwamin = min(iwamin, iwa)
    print(iwamin)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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)]#kokomadeha wakaru

indices = [2, 0, 1]
count_color = [[0] * C for i in range(3)]
for i in range(N):
  idx = indices[i%3]
  for j in range(N):
    count_color[idx][c[i][j]-1] += 1#1 minus surunoha list ni awaserutame iro to amari no kakezan
    idx = (idx + 1) % 3#koreha indices wo yatteirudake
    
# 色の対応関係をC_P_3通り全て試す
ans = float('inf')
correspondence = list(itertools.permutations(range(C), 3))
# (i+j)%3のマス目をcorr[(i+j)%3]に書き換える
for corr in correspondence:
  cost = 0
  for idx in range(3): # idx : (i+j)%3
    for color in range(C):
      cost += count_color[idx][color] * D[color][corr[idx]]
  ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import itertools as it
n,c= map(int,input().split())
dtab = []
dtab.append([0 for _ in range(c+1)])
for i in range(c):dtab.append([0] + list(map(int,input().split())))
ctab = []
ctab.append([0 for _ in range(n+1)])
for i in range(n):ctab.append([0]+list(map(int,input().split())))
ssd = [{},{},{}]
for i in range(1,n+1):
    for j in range(1,n+1):
        temp = (i+j)%3
        temp2 = ctab[i][j]
        ssd[temp][temp2] = ssd[temp].get(temp2,0) + 1
e = [i+1 for i in range(c)]
cpm = it.permutations(e, 3)
ming=999999999
for f in cpm:
    fl=list(f)
    cg = 0
    for i in range(3):
        for p in ssd[i].keys():cg += dtab[p][fl[i]] * ssd[i][p]
    ming = min(ming,cg)
print(ming)

Submission status: Accepted

Solution code:
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)]
    ans = [None]*3
    for k in range(3):
        costs = []
        for nc in range(c):
            cost = 0
            for i in range(n):
                s = (i+k)%3
                ci = C[i]
                for j in range(2-s, n, 3):
                    color = ci[j]-1
                    cost += D[color][nc]
            costs.append(cost)
        ans[k] = list(sorted({index:cost for index, cost in enumerate(costs)}.items(), key=lambda x: x[1]))[:3]
    out = 10**12
    for i in range(3):
        for j in range(3):
            for k in range(3):
                if len(set([ans[0][i][0], ans[1][j][0], ans[2][k][0]])) == 3:
                    out = min(out, ans[0][i][1]+ans[1][j][1]+ans[2][k][1])
    print(out)
            
    
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)]
g1 = []
g2 = []
g3 = []
for i in range(N):
    for j in range(N):
        G[i][j] -= 1
        if (i+j)%3 == 0:
            g1.append(G[i][j])
        if (i+j)%3 == 1:
            g2.append(G[i][j])
        if (i+j)%3 == 2:
            g3.append(G[i][j])



cost = [[0]*3 for _ in range(C)]
for c in range(C):
    for g in range(3):
        if g == 0:
            cost[c][0] = sum(D[clr_g1][c] for clr_g1 in g1)
        if g == 1:
            cost[c][1] = sum(D[clr_g2][c] for clr_g2 in g2)
        if g == 2:
            cost[c][2] = sum(D[clr_g3][c] for clr_g3 in g3)



ans = float('inf')
for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            temp = 0
            if c1 == c2 or c2 == c3 or c3 == c1:
                continue
            # temp += sum(D[clr_g1][c1] for clr_g1 in g1)
            # temp += sum(D[clr_g2][c2] for clr_g2 in g2)
            # temp += sum(D[clr_g3][c3] for clr_g3 in g3)
            temp = cost[c1][0] + cost[c2][1] + cost[c3][2]
            ans = min(ans,temp)
print(ans)

Submission status: Accepted

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

from collections import Counter
cs = [Counter() for _ in range(3)]
for i,row in enumerate(CS):
    for j,c in enumerate(row):
        cs[(i+j)%3][c-1] += 1

ans = float('inf')
for i in range(C):
    d1 = 0
    for c,v in cs[0].items():
        d1 += D[c][i]*v
    for j in range(C):
        if i==j: continue
        d2 = 0
        for c,v in cs[1].items():
            d2 += D[c][j]*v
        for k in range(C):
            if k==i or k==j: continue
            d3 = 0
            for c,v in cs[2].items():
                d3 += D[c][k]*v
            ans = min(ans, d1+d2+d3)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
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)]
table=[dd(int) for i in range(3)]

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

ans=10**10
for i in range(C):
    t1=0
    for x in table[0]:
        t1+=d[x][i]*table[0][x]
    for j in range(C):
        if i==j:continue
        t2=0
        for x in table[1]:
            t2+=d[x][j]*table[1][x]
        for k in range(C):
            if i==k or j==k:continue
            t3=0
            for x in table[2]:
                t3+=d[x][k]*table[2][x]
            
            ans=min(ans,t1+t2+t3)
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)]

X1=[0]*(c+1)
X2=[0]*(c+1)
X0=[0]*(c+1)

for i in range(n):
    for j in range(n):
        if (i+1+j+1)%3==0:
            X0[C[i][j]]+=1
        elif (i+1+j+1)%3==1:
            X1[C[i][j]]+=1
        else:
            X2[C[i][j]]+=1
A=[]
for c1 in range(c):
    for c2 in range(c):
        if c2==c1:
            continue
        for c3 in range(c):
            if c3==c2 or c3==c1:
                continue
            ans=0
            for i in range(1,c+1):
                ans+=X0[i]*D[i-1][c1]+X1[i]*D[i-1][c2]+X2[i]*D[i-1][c3]
            A.append(ans)
print(min(A))

Submission status: Accepted

Solution code:
# 想定解法
import itertools

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

indices = [2, 0, 1]
count_color = [[0] * C for i in range(3)]
for i in range(N):
  idx = indices[i%3]
  for j in range(N):
    count_color[idx][c[i][j]-1] += 1
    idx = (idx + 1) % 3

# 色の対応関係をC_P_3通り全て試す
ans = float('inf')
correspondence = list(itertools.permutations(range(C), 3))
# (i+j)%3のマス目をcorr[(i+j)%3]に書き換える
for corr in correspondence:
  cost = 0
  for idx in range(3): # idx : (i+j)%3
    for color in range(C):
      cost += count_color[idx][color] * D[color][corr[idx]]
  ans = min(ans, cost)

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)]
x=[[0]*(C+1) for _ in range(3)]
for i in range(N):
    for j in range(N):
        x[(i+j+2)%3][c[i][j]]+=1

from itertools import permutations
ans=1<<32
for ch in permutations(range(1,C+1),3):
    ans1=0
    for i in range(3):
        for j in range(1,C+1):
            ans1+=x[i][j]*d[j-1][ch[i]-1]
    ans=min(ans,ans1)
print(ans)

Submission status: Accepted

Solution code:
N,C = map(int, input().split())
# D[i][j]: 色iから色jに塗り替える場合のコスト
D = [[int(i) for i in input().split()] for _ in range(C)]

cnt = [[0] * C for _ in range(3)]
for i in range(1, N + 1):
    line = [int(i) for i in input().split()]
    for j, c in enumerate(line, start=1):
        cnt[(i + j) % 3][c - 1] += 1

ans = 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
            cost = 0
            for x in range(C):
                cost += D[x][i] * cnt[0][x]
                cost += D[x][j] * cnt[1][x]
                cost += D[x][k] * cnt[2][x]
            
            ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,C=map(int, input().split())
    D=[tuple(map(int, input().split())) for _ in range(C)]
    c=[tuple(map(int, input().split())) for _ in range(N)]

    c0=[c[i][j]-1 for i in range(N) for j in range(N) if (i+j)%3==0]
    c1=[c[i][j]-1 for i in range(N) for j in range(N) if (i+j)%3==1]
    c2=[c[i][j]-1 for i in range(N) for j in range(N) if (i+j)%3==2]

    from collections import Counter
    cc=[Counter(c0), Counter(c1), Counter(c2)]

    ans = 10**10
    from itertools import permutations
    for colors in permutations(range(C), 3):
        tmp = 0
        for i,cci in enumerate(cc):
            for k,v in cci.items():
                tmp += D[k][colors[i]] * v
        ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,C = LI()
    d = LIR(C)
    c = LIR(n)
    ans = 0
    s = [[0]*C for i in range(3)]
    for i in range(n):
        for j in range(n):
            s[(i+j)%3][c[i][j]-1] += 1
    ans = float("inf")
    for x in range(C):
        bx = 1<<x
        for y in range(C):
            if x == y:
                continue
            by = 1<<y
            for z in range(C):
                if z == x or z == y:
                    continue
                cost = 0
                for j in range(C):
                    cost += s[0][j]*d[j][x]
                    cost += s[1][j]*d[j][y]
                    cost += s[2][j]*d[j][z]
                if cost < ans:
                    ans = cost
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

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(lambda x: int(x)-1, input().split())) for N in range(N)]
val = [[0] * C for _ in range(3)]
for i in range(N):
    for j in range(N):
        for k in range(C):
            val[(i + j) % 3][k] += D[c[i][j]][k]
ans = 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
            ans = min(ans, val[0][i] + val[1][j] + val[2][k])
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)]

cnt = [[0] * C for _ in range(3)]
for h in range(N):
    for w, c in enumerate(map(int, input().split())):
        cnt[(h + w) % 3][c - 1] += 1

ans = 10**18
for perm in permutations(range(C), r=3):
    cost = 0
    for c, ns in zip(perm, cnt):
        for fr in range(C):
            if fr == c:
                continue
            cost += D[fr][c] * ns[fr]
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
#099_D
from collections import Counter
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 = [], [], []
for i in range(n):
    for j in range(n):
        if (i + j) % 3 == 0:
            C0.append(C[i][j]-1)
        elif (i + j) % 3 == 1:
            C1.append(C[i][j]-1)
        else:
            C2.append(C[i][j]-1)
C0 = Counter(C0)
C1 = Counter(C1)
C2 = Counter(C2)

ans = 10 ** 10
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
            tmp = 0
            for col, num in C0.items():
                tmp += D[col][i] * num
            for col, num in C1.items():
                tmp += D[col][j] * num
            for col, num in C2.items():
                tmp += D[col][k] * num
            
            ans = min(tmp, ans)
            
print(ans)

Submission status: Accepted

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

ans = 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
            res = 0
            for l in range(C):
                res += D[l][i] * t[0][l]
                res += D[l][j] * t[1][l]
                res += D[l][k] * t[2][l]
            ans = min(ans, res)
print(ans)

Submission status: Accepted

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

n, c = [int(x) for x in input().split()]

d_list = [[int(x) for x in input().split()] for _ in range(c)]
c_ = [[int(x) for x in input().split()] for _ in range(n)]

mod_0 = [0] * c
mod_1 = [0] * c
mod_2 = [0] * c

for i in range(n):
    for j in range(n):
        if (i + j) % 3 == 0:
            m = mod_0
        elif (i + j) % 3 == 1:
            m = mod_1
        else:
            m = mod_2
        for k in range(c):
            m[k] += d_list[c_[i][j] - 1][k]

ans = 10 ** 18

for i in range(c):
    for j in range(i + 1, c):
        for k in range(j + 1, c):
            a = mod_0[i] + mod_1[j] + mod_2[k]
            b = mod_0[i] + mod_1[k] + mod_2[j]
            c__ = mod_0[j] + mod_1[i] + mod_2[k]
            d = mod_0[j] + mod_1[k] + mod_2[i]
            e = mod_0[k] + mod_1[i] + mod_2[j]
            f = mod_0[k] + mod_1[j] + mod_2[i]
            ans = min(ans, a, b, c__, d, e, f)

print(ans)

Submission status: Accepted

Solution code:
import itertools
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)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)

conv_0, conv_1, conv_2 = [],[],[]
for i in range(c):
    tmp0, tmp1, tmp2 = 0,0,0
    for j in range(len(mod0)):
        tmp0 += D[mod0[j]][i]
    for j in range(len(mod1)):
        tmp1 += D[mod1[j]][i]
    for j in range(len(mod2)):
        tmp2 += D[mod2[j]][i]
    conv_0.append(tmp0)
    conv_1.append(tmp1)
    conv_2.append(tmp2)
res = float('inf')
for x,y,z in itertools.permutations(list(range(c)), 3):
    cnt = conv_0[x] + conv_1[y] + conv_2[z]
    res = min(cnt, res)
print(res)

Submission status: Accepted

Solution code:
import itertools
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)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)

conv_0, conv_1, conv_2 = [],[],[]
for i in range(c):
    tmp0, tmp1, tmp2 = 0,0,0
    for j in range(len(mod0)):
        tmp0 += D[mod0[j]][i]
    for j in range(len(mod1)):
        tmp1 += D[mod1[j]][i]
    for j in range(len(mod2)):
        tmp2 += D[mod2[j]][i]
    conv_0.append(tmp0)
    conv_1.append(tmp1)
    conv_2.append(tmp2)
res = float('inf')
color_range = list(range(c))
for x,y,z in itertools.permutations(color_range, 3):
    cnt = 0
    cnt = conv_0[x] + conv_1[y] + conv_2[z]
    res = min(cnt, res)
print(res)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
s = [list(map(int, input().split())) for _ in range(n)]
c0 = [[0 for _ in range(c)] for _ in range(3)]
c1 = [[0 for _ in range(c)] for _ in range(3)]
for i in range(n):
    for j in range(n):
        if (i + j) % 3 == 0:
            c0[0][s[i][j] - 1] += 1
        elif (i + j) % 3 == 1:
            c0[1][s[i][j] - 1] += 1
        elif (i + j) % 3 == 2:
            c0[2][s[i][j] - 1] += 1
for i in range(3):
    for j in range(c):
        for k in range(c):
            c1[i][j] += d[k][j] * c0[i][k]
"""
c2, c3 = [], []
for i in range(3):
    c2 = []
    for j in range(3):
        x = c1[i]
        a = [min(x), x.index(min(x))]
        c2.append(a)
        c1[i][c1[i].index(min(c1[i]))] = 10 ** 9
    c3.append(c2)
ans = 10 ** 9
for i in range(3):
    for j in range(3):
        for k in range(3):
            if c3[0][i][1] != c3[1][j][1] and c3[0][i][1] != c3[2][k][1] and c3[2][j][1] != c3[2][k][1]:
                m = c3[0][i][0] + c3[1][j][0] + c3[2][k][0]
                if m < ans:
                    ans = m
print(ans)"""
m = 0
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:
                m = c1[0][i] + c1[1][j] + c1[2][k]
                if m < ans:
                    ans = m
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

ans = 1000*n*n
for c123 in permutations(range(cn),3):
    dsum = 0
    for i in range(3):
        for j in range(cn):
            dsum += d[j][c123[i]] * col_count[i][j]
    ans = min(ans,dsum)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

group = [Counter() for _ in range(3)]
for i in range(N):
    for j in range(N):
        group[(i + j) % 3][grid[i][j]] += 1

ans = float('inf')
for c0 in range(C):
    for c1 in range(C):
        if c0 == c1:
            continue
        for c2 in range(C):
            if c2 == c0 or c2 == c1:
                continue
            cnt = 0
            color = [c0, c1, c2]
            for G, nc in zip(group, color):
                for c in list(G.keys()):
                    cnt += G[c] * D[c][nc]
            ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,C=map(int,input().split())

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


col=[[0]*30 for i in range(3)]

for i in range(N):
    for j in range(N):
        col[(i+j+2)%3][c[i][j]-1]+=1

ans=10**9
for col0 in range(C):
    temp0=0
    for i in range(C):
        temp0+=col[0][i]*D[i][col0] 
    for col1 in range(C):
        if col0==col1:
            continue
        #print(temp0)
        temp1=temp0
        for i in range(C):
            temp1+=col[1][i]*D[i][col1]
        for col2 in range(C):
            if col2==col0 or col2==col1:
                continue
            temp2=temp1
            for i in range(C):
                #print(col0,col1,col2)
                temp2+=col[2][i]*D[i][col2]
            #print(col0,col1,col2)
            ans=min(ans,temp2)
            
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc099/tasks/abc099_d
# さまざまな合わせ技
# ダイクストラ、全探索

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため



# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations

# from scipy.sparse.csgraph import dijkstra
# from scipy.sparse import csr_matrix, lil_matrix
# 0 まずはダイクストラでX→Yの最小コストを求めておく #えーーーーこれ想定されてないの？
# 1 座標ごとに3つのグループわけができる(n=1のときだけ場合分け
# 2 グループごとに色をカウント
# 3 各グループの色を仮定して全探索

N, C = read_ints()
D = read_matrix(C)
# D = csr_matrix(D)
# D = dijkstra(D)


# 1 座標のグループわけ
Cmap = read_matrix(N)

if N == 1:
    print(0)
    exit()

lsbymod = defaultdict(lambda: defaultdict(lambda: 0))
for i in range(N):
    for j in range(N):
        lsbymod[(i + j + 2) % 3][Cmap[i][j] - 1] += 1

# グループごとに色のカウント
# for k, v in lsbymod.items():
#     lsbymod[k] = Counter(v)

# 各グループの色を仮定して全探索


def ret_score(*arg):
    # 各仮定から違和感を計算
    ret = 0
    for i in range(3):
        for k, v in lsbymod[i].items():
            ret += v * D[k][arg[i]]
    return ret


ans = 2**63
for a, b, c in permutations(range(C), 3):
    # print(a, b, c, ret_score(a, b, c))
    ans = min(ans, ret_score(a, b, c))

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc099/tasks/abc099_d
# さまざまな合わせ技
# ダイクストラ、全探索

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため



# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations

# from scipy.sparse.csgraph import dijkstra
# from scipy.sparse import csr_matrix, lil_matrix
# 0 まずはダイクストラでX→Yの最小コストを求めておく #えーーーーこれ想定されてないの？
# 1 座標ごとに3つのグループわけができる(n=1のときだけ場合分け
# 2 グループごとに色をカウント
# 3 各グループの色を仮定して全探索

N, C = read_ints()
D = read_matrix(C)
# D = csr_matrix(D)
# D = dijkstra(D)


# 1 座標のグループわけ
Cmap = read_matrix(N)

if N == 1:
    print(0)
    exit()

lsbymod = defaultdict(lambda: [])
for i in range(N):
    for j in range(N):
        lsbymod[(i + j + 2) % 3].append(Cmap[i][j] - 1)

# グループごとに色のカウント
for k, v in lsbymod.items():
    lsbymod[k] = Counter(v)

# 各グループの色を仮定して全探索


# print(D)
# print(lsbymod)


def ret_score(*arg):
    # 各仮定から違和感を計算
    ret = 0
    for i in range(3):
        for k, v in lsbymod[i].items():
            ret += v * D[k][arg[i]]
    return ret


ans = 2**63
for a, b, c in permutations(range(C), 3):
    # print(a, b, c, ret_score(a, b, c))
    ans = min(ans, ret_score(a, b, c))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import product
INF = 10**9
MOD = 10**9 + 7

def main():
    n,c = map(int,input().split())
    D = [list(map(int,input().split())) for _ in range(c)]
    grid0 = []
    grid1 = []
    grid2 = []
    for i in range(n):
        g = [int(i)-1 for i in input().split()]
        for j in range(n):
            if  (i+j)%3 == 0:
                grid0.append(g[j])
            elif (i+j)%3 == 1:
                grid1.append(g[j])
            else:
                grid2.append(g[j])
        
    
    def drew(grid):
        ans = [[INF,-2] for _ in range(3)] 
        for i in range(c):
            t = 0
            for g in grid:
                t += D[g][i]
            if t < ans[0][0]:
                ans[2] = ans[1]
                ans[1] = ans[0]
                ans[0] = [t,i]
            elif t < ans[1][0]:
                ans[2] = ans[1]
                ans[1] = [t,i]
            elif t < ans[2][0]:
                ans[2] = [t,i]

        return ans
    
    a = drew(grid0)
    b = drew(grid1)
    c = drew(grid2)
    ans = INF 
    for x,y,z in product(a,b,c):
        if  x[1] != y[1] and y[1] != z[1] and z[1] != x[1]:
            ans = min(ans,x[0]+y[0]+z[0])
    
    print(ans)
   
if __name__=='__main__':
    main()