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:
def main():
  N, C = list(map(int, input().split()))
  D = []
  for i in range(C):
    D.append(list(map(int, input().split())))
  c = []
  for i in range(N):
    c.append(list(map(int, input().split())))
  
  X = {}
  Y = {}
  Z = {}
  for i in range(N):
    for j in range(N):
      col = c[i][j] - 1
      if (i + j + 2) % 3 == 0:
        if col in X:
          X[col] += 1
        else:
          X[col] = 1
      elif (i + j + 2) % 3 == 1:
        if col in Y:
          Y[col] += 1
        else:
          Y[col] = 1
      else:
        if col in Z:
          Z[col] += 1
        else:
          Z[col] = 1
  Ans = 10e10      
  for i in range(C):
    cntX = 0
    for p, q in X.items():
      cntX += D[p][i] * q
    for j in range(C):
      if i == j:
        continue
      cntY = 0
      for p, q in Y.items():
        cntY += D[p][j] * q
      for k in range(C):
        if i == k or j == k:
          continue
        cntZ = 0
        for p, q in Z.items():
          cntZ += D[p][k] * q
        t = cntX + cntY + cntZ
        if t < Ans:
          Ans = t    
  print(Ans)

main()

Submission status: Accepted

Solution code:
from itertools import product, permutations

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

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

for x, y in product(range(N), range(N)):
    cost[(x + y) % 3][grid[x][y]] += 1

minn = float("inf")
for colors in permutations(range(C), 3):
    t = 0
    for s, color_n in enumerate(colors):
        for color_p, n in enumerate(cost[s]):
            t += n * D[color_p][color_n]
    minn = min(minn, t)
print(minn)

Submission status: Accepted

Solution code:
import itertools
N,C = list(map(int,input().split()))
D = [list(map(int,input().split())) for i in range(C)]
data = [list(map(int,input().split())) for i in range(N)]
s = []
total = [[0 for i in range(C)] for j in range(3)]
ans = []
for i in range(C):
    s.append(i)

col = list(itertools.permutations(s,3))

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

for i in col:
    tempans = 0
    for s in range(3):
        for t in range(C):
            tempans += D[t][i[s]]*total[s][t]
    ans.append(tempans)

print(min(ans))

Submission status: Accepted

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

memo0 = {}
memo1 = {}
memo2 = {}

for i in range(grid_num):
  for j in range(grid_num):
    if (i+j)%3 ==0:
      if c[i][j] not in memo0:
        memo0[c[i][j]] = 1
      else:
        memo0[c[i][j]] += 1
    if (i+j)%3 ==1:
      if c[i][j] not in memo1:
        memo1[c[i][j]] = 1
      else:
        memo1[c[i][j]] += 1
    if (i+j)%3 ==2:
      if c[i][j] not in memo2:
        memo2[c[i][j]] = 1
      else:
        memo2[c[i][j]] += 1

#print(memo0)
#print(memo1)
#print(memo2)
        
cost0=[0]*color_num
cost1=[0]*color_num
cost2=[0]*color_num

for i in range(color_num):

  for j in memo0:
    cost0[i] += memo0[j]*(d[j-1][i])
    
  for j in memo1:
    cost1[i] += memo1[j]*(d[j-1][i]) 
    
  for j in memo2:
    cost2[i] += memo2[j]*(d[j-1][i])

    
#print(cost0)
#print(cost1)
#print(cost2)
ans = 1000000000000000
for i in range(color_num):
  for j in range(color_num):
    for k in range(color_num):
      if i != j and j != k and k != i:
        ans = min(ans,cost0[i]+cost1[j]+cost2[k])
    
print(ans)

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)]
C0=[0]*(C+1)
C1=[0]*(C+1)
C2=[0]*(C+1)

for x in range(N):
    for y in range(N):
        if (x+y+2)%3==0: C0[G[x][y]]+=1
        elif (x+y+2)%3==1: C1[G[x][y]]+=1
        elif (x+y+2)%3==2: C2[G[x][y]]+=1

miniwa=250000000
for c0 in range(1,C+1):
    for c1 in range(1,C+1):
        for c2 in range(1,C+1):
            if (c1-c0)*(c2-c1)*(c0-c2)==0: continue
            iwa=0
            for i in range(1,C+1):
                iwa+=(D[i-1][c0-1]*C0[i]+D[i-1][c1-1]*C1[i]+D[i-1][c2-1]*C2[i])
            miniwa=min(miniwa,iwa)
print(miniwa)

Submission status: Accepted

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

def main():
    na = list(map(int, input().split()))
    N, C = na[0], na[1]

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

    s = []
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))

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

    s_min = 500 * 500 * 1000
    for i in range(1, C + 1):
        for j in range(1, C + 1):
            if i == j:
               continue 
            for k in range(1, C + 1):
                if i == k or j == k:
                    continue
                s_min = min(s_min, s[0][i] + s[1][j] + s[2][k])


    print(s_min)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def func(d, c):
    color = [[0 for _ in range(len(d))] for _ in range(3)]
    for i in range(len(c)):
        for j in range(len(c)):
            color[(i + j) % 3][c[i][j]] += 1
    # print("color:{}".format(color))
    _min = 10**10
    for i in range(len(d)):
        # %3==0を色iにする場合
        cost1 = sum([d[prev][i]*color[0][prev] for prev in range(len(color[0]))])
        for j in range(len(d)):
            if i == j:
                continue
            # %3==1を色jにする場合
            cost2 = sum([d[prev][j] * color[1][prev] for prev in range(len(color[0]))])
            for k in range(len(d)):
                if i == k or j == k:
                    continue
                # %3==2を色kにする場合
                cost3 = sum([d[prev][k] * color[2][prev] for prev in range(len(color[0]))])
                _min = min(_min, cost1+cost2+cost3)
                # print("->{} cost1:{} ->{} cost2:{} ->{} cost3:{} total:{}".format(i, cost1, j, cost2, k, cost3, cost1+cost2+cost3))
    return _min
n, C = [int(i) for i in input().split()]
d = [[0 for _ in range(C)] for _ in range(C)]
c = [[0 for _ in range(n)] for _ in range(n)]
for i in range(C):
    d[i] = [int(i) for i in input().split()]
for i in range(n):
    c[i] = [int(i) - 1 for i in input().split()]
print(func(d, c))
"""
# print("print(func({},{}))".format(d, c))
print(func([[0, 1, 1], [1, 0, 1], [1, 4, 0]],[[0, 1], [2, 2]]))
print(func([[0, 12, 71], [81, 0, 53], [14, 92, 0]],[[0, 0, 1, 0], [1, 0, 0, 1], [1, 1, 0, 2], [0, 0, 1, 1]]))
"""

Submission status: Accepted

Solution code:
from collections import Counter

N, C = map(int, input().split())
d_grid = []
for i in range(C):
    d_grid.append(tuple(map(int, input().split())))
c_list = []
for i in range(N):
    c_list.append(tuple(map(int, input().split())))

m0 = []
m1 = []
m2 = []
for i in range(N):
    for j in range(N):
        m = i + j + 2
        tmp = c_list[i][j]
        if m % 3 == 0:
            m0.append(tmp)
        if m % 3 == 1:
            m1.append(tmp)
        if m % 3 == 2:
            m2.append(tmp)

m0_count = Counter(m0)
m1_count = Counter(m1)
m2_count = Counter(m2)

ans = float("inf")

m0_cost = [0 for _ in range(C)]
m1_cost = [0 for _ in range(C)]
m2_cost = [0 for _ in range(C)]

for c1 in range(C):
    for c2 in range(C):
        cost = d_grid[c1][c2]
        m0_cost[c2] += m0_count[c1 + 1] * cost
        m1_cost[c2] += m1_count[c1 + 1] * cost
        m2_cost[c2] += m2_count[c1 + 1] * cost
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or i == k or j == k:
                continue
            ans = min(ans, m0_cost[i] + m1_cost[j] + m2_cost[k])
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, C = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(C)]
c = [tuple(map(lambda x: x-1, map(int, input().split()))) for _ in range(N)]

grid = [[0] * C for _ in range(3)]
for i, j in itertools.product(range(N), repeat=2):
    grid[(i+j)%3][c[i][j]] += 1

ans = float("inf")
for color_after in itertools.permutations(range(C), 3):
    s = sum([sum([grid[g][color_before]*D[color_before][color_after[g]] for color_before in range(C)]) for g in range(3)])
    ans = min(ans, s)

print(ans)

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)]
mod_0,mod_1,mod_2={},{},{}
for i in range(n):
    for j in range(n):
        if (i+j)%3==0:
            mod_2.setdefault(s[i][j]-1,0)
            mod_2[s[i][j]-1]+=1
        elif (i+j)%3==1:
            mod_0.setdefault(s[i][j]-1,0)
            mod_0[s[i][j]-1]+=1
        else:
            mod_1.setdefault(s[i][j]-1,0)
            mod_1[s[i][j]-1]+=1
cost0=[0 for _ in range(c)]
cost1=[0 for _ in range(c)]
cost2=[0 for _ in range(c)]
for i in range(c):
    for j in mod_0.keys():
        cost0[i]+=d[j][i]*mod_0[j]
for i in range(c):
    for k in mod_1.keys():
        cost1[i]+=d[k][i]*mod_1[k]
for i in range(c):
    for l in mod_2.keys():
        cost2[i]+=d[l][i]*mod_2[l]
ans=float('inf')
for i in range(c):
    for j in range(c):
        if i==j:
            continue
        for k in range(c):
            if j==k or i==k:
                continue
            else:
                ans=min(ans,cost0[i]+cost1[j]+cost2[k])
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, C = [int(_) for _ in input().split()]
D = [[int(_) for _ in input().split()] for _ in range(C)]
c = [[int(_) - 1 for _ in input().split()] for _ in range(N)]  #0-indexed

grid = [[0] * C for _ in range(3)]
for i, j in itertools.product(range(N), repeat=2):
    grid[(i + j) % 3][c[i][j]] += 1
ans = float('inf')
for color_after in itertools.permutations(range(C), 3):
    ans = min(
        ans,
        sum([
            sum([
                grid[g][color_before] * D[color_before][color_after[g]]
                for color_before in range(C)
            ]) for g in range(3)
        ]))
print(ans)

Submission status: Accepted

Solution code:
def cnter(List,c):
  ans = [0]*c
  for i in List:
    ans[i-1] += 1
  return ans
n,c = map(int, input().split())
d = []
e = []
for i in range(c):
  d1 = list(map(int, input().split()))
  d.append(d1)
for i in range(n):
  e1 = list(map(int, input().split()))
  e.append(e1)
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
  for j in range(n):
    b = i + j
    if b % 3 == 0:
      mod2.append(e[i][j])
    elif b % 3 == 1:
      mod0.append(e[i][j])
    else:
      mod1.append(e[i][j])
mod0 = cnter(mod0,c)
mod1 = cnter(mod1,c)
mod2 = cnter(mod2,c)
len_0, len_1, len_2= sum(mod0), sum(mod1), sum(mod2)
mod0_p = []
mod1_p = []
mod2_p = []
md0 = 0
md1 = 0
md2 = 0
for i in range(c):
  md0 = 0
  md1 = 0
  md2 = 0
  for j in range(c):
    md0 += d[j][i] * mod0[j]
    md1 += d[j][i] * mod1[j]
    md2 += d[j][i] * mod2[j]
  mod0_p.append(md0)
  mod1_p.append(md1)
  mod2_p.append(md2)
ans = 2**31-1
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i != j and j != k and k != i:
        if mod0_p[i] + mod1_p[j] + mod2_p[k] < ans:
          ans = mod0_p[i] + mod1_p[j] + mod2_p[k]
print(ans)

Submission status: Accepted

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

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]

COL = [[0, 0, 0] for _ in range(C)]

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

for p in range(3):
    for toC in range(C):
        for fromC in range(C):
            I[toC][p] += D[fromC][toC] * COL[fromC][p]

# I[toC][pattern] += D[c[i][j] - 1][toC]

ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        if p1 == p2:
            continue
        a = I[p1][0] + I[p2][1]
        for p3 in range(C):
            if p1 == p3 or p2 == p3:
                continue
            ans = min(ans, a + I[p3][2])

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
cN = [list(map(int, input().split())) for i in range(N)]

# [mod 3でどれになるか][今の色] = 該当する数
memo = [[0] * C for i in range(3)]
for i in range(N):
    for j in range(N):
        memo[(i+j+2)%3][cN[i][j]-1] += 1

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
            sm = 0
            # 元の色ループ
            for l in range(C):
                # メモを元に、各塗り替えでどのくらい違和感が出るか算出
                sm += D[l][i] * memo[0][l]
                sm += D[l][j] * memo[1][l]
                sm += D[l][k] * memo[2][l]
            ans = min(sm, ans)
print(ans)

Submission status: Accepted

Solution code:
import collections
import itertools
#横にn個入力
n, c = map(int, input().split())
#行列
d = []
for i in range(c):#h:高さ
    d.append([int(m) for m in input().split()])
#行列
e = []
for i in range(n):#h:高さ
    e.append([int(m) for m in input().split()])

li0 = []
li1 = []
li2 = []
for i in range(n):
    for j in range(n):
        if (i + j + 2) % 3 == 0:
            li0.append(e[i][j])
        elif (i + j + 2) % 3 == 1:
            li1.append(e[i][j])
        elif (i + j + 2) % 3 == 2:
            li2.append(e[i][j])

c0 = collections.Counter(li0)
c1 = collections.Counter(li1)
c2 = collections.Counter(li2)

cost0 = {}
cost1 = {}
cost2 = {}
dost0 = []
dost1 = []
dost2 = []
k0 = 0
k1 = 0
k2 = 0
for i in range(c):
    for v0 in c0:
        k0 += d[v0 - 1][i] * c0[v0]
    cost0[i + 1] = k0
    dost0.append([k0, i + 1])
    k0 = 0
    for v1 in c1:
        k1 += d[v1 - 1][i] * c1[v1]
    cost1[i + 1] = k1
    dost1.append([k1, i + 1])
    k1 = 0
    for v2 in c2:
        k2 += d[v2 - 1][i] * c2[v2]
    cost2[i + 1] = k2
    dost2.append([k2, i + 1])
    k2 = 0

dost0.sort()
dost1.sort()
dost2.sort()
w0 = [dost0[0][1], dost0[1][1], dost0[2][1]]
w1 = [dost1[0][1], dost1[1][1], dost1[2][1]]
w2 = [dost2[0][1], dost2[1][1], dost2[2][1]]

ansli = []
for x0 in itertools.permutations(w0, 1):
    for x1 in itertools.permutations(w1, 1):
        for x2 in itertools.permutations(w2, 1):
            if x0[0] != x1[0] and x1[0] != x2[0] and x2[0] != x0[0]:
                ansli.append(cost0[x0[0]] + cost1[x1[0]] + cost2[x2[0]])

print(min(ansli))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]

cnt = {
    0: {},
    1: {},
    2: {}
}

for i in range(n):
    cl = list(map(int, input().split()))
    for j in range(n):
        k = (i+j)%3
        if cl[j] not in cnt[k]:
                cnt[k][cl[j]] = 0
        cnt[k][cl[j]] += 1

res = 10**3 * 500**2 + 10
for ci in range(c):
    for cj in range(c):
        if ci==cj:
            continue
        for ck in range(c):
            if ci==ck or cj==ck:
                continue

            t = 0
            cc = [ci, cj, ck]
            for r in range(3):
                for k in cnt[r].keys():
                    t += d[k-1][cc[r]]*cnt[r][k]
            res = min(res, t)
print(res)

Submission status: Accepted

Solution code:
N,C = list(map(int,input().split()))
D = []

for i in range(C):
    D.append(list(map(int,input().split())))

c = []

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

color_list = [[0 for i in range(C)] for j in range(3)]

for i in range(N):
    for j in range(N):
        color_list[(i+j)%3][c[i][j]-1]+=1
score_list = [[] for i in range(3)]
for i in range(3):
    for j in range(C):
        score=0
        for k in range(C):
            score+=D[k][j]*color_list[i][k]
        score_list[i].append([score,j])
        
for i in range(3):
    score_list[i]=sorted(score_list[i],key=lambda x: x[0])

min_score=10**28
for i in range(3):
    for j in range(3):
        for k in range(3):
          
            if score_list[0][i][1]!=score_list[1][j][1] and score_list[1][j][1]!=score_list[2][k][1] and score_list[2][k][1]!=score_list[0][i][1]:
                min_score=min(score_list[0][i][0]+score_list[1][j][0]+score_list[2][k][0],min_score)

print(min_score)

Submission status: Accepted

Solution code:
N, C = ( int(i) for i in input().split())
dd = [[int(j) for j in input().split()] for i in range(C)]
cc = [[int(j) for j in input().split()] for i in range(N)]

cc0 = []
cc1 = []
cc2 = []
for i in range(N):
    for j in range(N):
        if (i + j)%3 == 0:
            cc0.append(cc[i][j])
        elif (i + j)%3 == 1:
            cc1.append(cc[i][j])
        else:
            cc2.append(cc[i][j])

ds = [[],[],[]]
for c1 in range(C):
    temp = 0
    for c2 in cc0:
        temp += dd[c2-1][c1]
    ds[0].append((temp,c1))
    temp = 0
    for c2 in cc1:
        temp += dd[c2-1][c1]
    ds[1].append((temp,c1))
    temp = 0
    for c2 in cc2:
        temp += dd[c2-1][c1]
    ds[2].append((temp,c1))

cut = []

for dss in ds:
    dss.sort()
    cut.append(dss[:3])

res = []
for i in range(3):
    for j in range(3):
        for k in range(3):
            dd0, c0 = cut[0][i]
            dd1, c1 = cut[1][j]
            dd2, c2 = cut[2][k]
            if c0 != c1 and c1 != c2 and c2 != c0:
                res.append(dd0 + dd1 + dd2)

res.sort()
print(res[0])

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
D = [[0 for j in range(C)] for i in range(C)]
for i in range(C):
  D[i] = [int(x) for x in input().split()]
Cxy = [[0 for j in range(C)] for i in range(3)]
for i in range(N):
  for j, c in enumerate(input().split()):
    Cxy[(i + j + 2) % 3][int(c) - 1] += 1
Change = [[[0, j] for j in range(C)] for i in range(3)]
for i in range(3):
  for j in range(C):
    for k in range(C):
      Change[i][j][0] += D[k][j] * Cxy[i][k]
for i in range(3):
  Change[i].sort()
cost = Change[0][2][0] + Change[1][2][0] + Change[2][2][0]
for i in range(3):
  for j in range(3):
    for k in range(3):
      if Change[0][i][1] != Change[1][j][1] and Change[1][j][1] != Change[2][k][1] and Change[2][k][1] != Change[0][i][1]:
        cost = min(Change[0][i][0] + Change[1][j][0] + Change[2][k][0], cost)
print(cost)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from pprint import pprint
from collections import defaultdict
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)]

mod3_dict_tbl = [defaultdict(int) for _ in range(3)]
for i in range(N):
    for j in range(N):
        mod3_dict_tbl[(i+1+j+1) % 3][c[i][j]-1] += 1

ans = []

colors = [i for i in range(C)]

for to_colors in itertools.permutations(colors, 3):
    tmp_diff = 0
    for i,to_color in enumerate(to_colors):
        for k,v in mod3_dict_tbl[i].items():
            tmp_diff += D[k][to_color]*v
    ans.append(tmp_diff)

print(min(ans))

Submission status: Accepted

Solution code:
def intlist():
    k = [int(i) for i in input().split()]
    return k
def intmat(x):
    k = [[int(i) for i in input().split()] for i in range(x)]
    return k
#ここから下に書く
N,C = intlist()
d = intmat(C)
c = intmat(N)
anss=[]
numbercount0,numbercount1,numbercount2 = {},{},{}
for i in range(C):
    numbercount0[str(i)]=0
    numbercount1[str(i)]=0
    numbercount2[str(i)]=0
for i in range(N):
    for j in range(N):
        if (i+j+2)%3==0:
            numbercount0[str(c[i][j]-1)] +=1
        if (i+j+2)%3==1:
            numbercount1[str(c[i][j]-1)] +=1
        if (i+j+2)%3==2:
            numbercount2[str(c[i][j]-1)] +=1
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=0
            for l in range(C):
                ans+=d[l][i]*numbercount0[str(l)]
                ans+=d[l][j]*numbercount1[str(l)]
                ans+=d[l][k]*numbercount2[str(l)]
            anss+=[ans]
print(min(anss))

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)]
modl = [[0 for i in range(C)] for i in range(3)]
for i in range(N):
    for j in range(N):
        modl[((i+1)+(j+1))%3][c[i][j]-1] += 1
ans = float('inf')
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or i==k or j==k:
                continue
            total = 0
            for l in range(C):
                total += D[l][i]*modl[0][l]+D[l][j]*modl[1][l]+D[l][k]*modl[2][l]
            ans = min(ans,total)
print(ans)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
D=[[int(i) for i in input().split()] for i in range(C)]
grid=[[int(i) for i in input().split()] for i in range(N)]
colors0=[0]*C
colors1=[0]*C
colors2=[0]*C
for i in range(1,N+1):
  for j in range(1,N+1):
    if (i+j)%3==0:
      colors0[grid[i-1][j-1]-1]+=1
    if (i+j)%3==1:
      colors1[grid[i-1][j-1]-1]+=1
    if (i+j)%3==2:
      colors2[grid[i-1][j-1]-1]+=1

d0=[10**20]*3
d1=[10**20]*3
d2=[10**20]*3
c0=[0]*3
c1=[0]*3
c2=[0]*3
s0=0
s1=0
s2=0
for c in range(C):
  for i in range(C):
    s0+=colors0[i]*D[i][c]
  for j in range(3):
    if s0<d0[j]:
      for k in range(2,j,-1):
        d0[k]=d0[k-1]
        c0[k]=c0[k-1]
      d0[j]=s0
      c0[j]=c
      break
  s0=0
  for i in range(C):
    s1+=colors1[i]*D[i][c]
  for j in range(3):
    if s1<d1[j]:
      for k in range(2,j,-1):
        d1[k]=d1[k-1]
        c1[k]=c1[k-1]
      d1[j]=s1
      c1[j]=c
      break
  s1=0
  for i in range(C):
    s2+=colors2[i]*D[i][c]
  for j in range(3):
    if s2<d2[j]:
      for k in range(2,j,-1):
        d2[k]=d2[k-1]
        c2[k]=c2[k-1]
      d2[j]=s2
      c2[j]=c
      break
  s2=0   
ans=10**20
for i in range(3):
  for j in range(3):
    for k in range(3):
      if c0[i]==c1[j] or c1[j]==c2[k] or c2[k]==c0[i]:
        pass
      else:
        if ans>d0[i]+d1[j]+d2[k]:
          ans=d0[i]+d1[j]+d2[k]
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
 
def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    CC = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
 
    cost = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for i in range(N):
            for j in range(N):
                cost[(i + j) % 3][c] += D[CC[i][j]][c]
 
    res = float("inf")
    color = [i for i in range(C)]
    for i, c in enumerate(list(itertools.permutations(color, 3))):
        tmp = 0
        for it in range(3):
            tmp += cost[it][c[it]]
        res = min(res, tmp)
 
    print(res)
 
main()

Submission status: Accepted

Solution code:
import itertools


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

    cost = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for i in range(N):
            for j in range(N):
                cost[(i + j) % 3][c] += D[CC[i][j]][c]

    res = float("inf")
    color = [i for i in range(C)]
    for i, c in enumerate(list(itertools.permutations(color, 3))):
        tmp = 0
        for it in range(3):
            tmp += cost[it][c[it]]
        res = min(res, tmp)

    print(res)

main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

list0 = [0 for _ in range(C)]
list1 = [0 for _ in range(C)]
list2 = [0 for _ in range(C)]


for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            list0[c[i][j]-1] += 1
        elif (i+j) % 3 == 1:
            list1[c[i][j]-1] += 1
        else:
            list2[c[i][j]-1] += 1

color = tuple(i for i in range(C))

ans = float('inf')
for c0, c1, c2 in permutations(color, 3):
    cost = 0
    for i in range(C):
        cost += D[i][c0] * list0[i]
        cost += D[i][c1] * list1[i]
        cost += D[i][c2] * list2[i]
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

n,c = li()
diff = [list(li()) for _ in range(c)]
init = [list(li_()) for _ in range(n)]

group = [Counter() for _ in range(3)]

for row in range(n):
    for col in range(n):
        group[(row+col)%3][init[row][col]] += 1
        
ans = 10**18

for c0 in range(c):
    cost = [0,0,0]
    for k,v in group[0].items():
        cost[0] += v*diff[k][c0]

        
    for c1 in range(c):
        if c0 == c1:
            continue
        
        cost[1] = 0
        
        for k,v in group[1].items():
            cost[1] += v*diff[k][c1]
            
        for c2 in range(c):
            if c2 == c0 or c2 == c1:
                continue
            
            cost[2] = 0
            
            for k,v in group[2].items():
                cost[2] += v*diff[k][c2]
                
            ans = min(ans, sum(cost))
            
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, C = ds_in()

DIFF = []
for _ in range(C):
    DIFF.append(ds_in())
DIFF = np.array(DIFF).T

c_list = []
for _ in range(N):
    c_list.append(ds_in())

mod_c = np.zeros((3, C))
for i in range(N):
    for j in range(N):
        if (i + j) % 3 == 0:
            mod_c[0, c_list[i][j] - 1] += 1
        elif (i + j) % 3 == 1:
            mod_c[1, c_list[i][j] - 1] += 1
        else:
            mod_c[2, c_list[i][j] - 1] += 1

# calculate all diff

diff0 = np.dot(DIFF, mod_c[0])
diff1 = np.dot(DIFF, mod_c[1])
diff2 = np.dot(DIFF, mod_c[2])

min_diff = 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
            min_diff = min(min_diff, diff0[i] + diff1[j] + diff2[k])

print(int(min_diff))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, C = map(int, input().split())
D = [[int(i) for i in input().split()] for c in range(C)]
Ini = [[int(i) for i in input().split()] for n in range(N)]
C0, C1, C2 = defaultdict(int), defaultdict(int), defaultdict(int)
D0, D1, D2 = [[0, d] for d in range(C)], [[0, d] for d in range(C)], [[0, d] for d in range(C)]
for i in range(N):
    for j in range(N):
        if (i+j+2)%3 == 0:
            C0[Ini[i][j] - 1] += 1
        elif (i+j+2)%3 == 1:
            C1[Ini[i][j] - 1] += 1
        else:
            C2[Ini[i][j] - 1] += 1

for i in range(C):
    for c in C0:
        D0[i][0] += D[c][i] * C0[c]
    for c in C1:
        D1[i][0] += D[c][i] * C1[c]
    for c in C2:
        D2[i][0] += D[c][i] * C2[c]

D0.sort()
D1.sort()
D2.sort()
Ans = float("inf")
for i in range(3):
    I = D0[i]
    for j in range(3):
        J = D1[j]
        for k in range(3):
            K = D2[k]
            if I[1] != J[1] and J[1] != K[1] and K[1] != I[1]:
                Ans = min(Ans, I[0] + J[0] + K[0])
print(Ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
C = [list(map(int, input().split())) for _ in range(n)]

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

costs = [[0]*c for _ in range(3)]
for i in range(3):
    for c_cur in range(c):
        for c_tar in range(c):
            costs[i][c_tar] += D[c_cur][c_tar]*colors[i][c_cur]

ans = 1000*500**2
for c0, c1, c2 in permutations(range(c), 3):
    diff = costs[0][c0] + costs[1][c1] + costs[2][c2]
    ans = min(ans, diff)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
C = [list(map(int, input().split())) for _ in range(n)]

colors = [[0]*c for _ in range(3)]
for i in range(n):
    for j in range(n):
        c_ij = C[i][j]-1
        index = (i+j)%3
        for col in range(c):
            colors[index][col] += D[c_ij][col]

ans = 1000*500**2
for c0, c1, c2 in permutations(range(c), 3):
    diff = colors[0][c0] + colors[1][c1] + colors[2][c2]
    ans = min(ans, diff)
print(ans)

Submission status: Accepted

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

color_num=[ [0]*(c+1) for i in range(3)]


for i in range(n):
    tmp=list(map(int,input().split()))
    for j in range(n):
        color_num[(i+j+2)%3][tmp[j]]+=1

ans=[]
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):
                tmp=0
                for m in range(1,c+1):
                    tmp+=color_num[0][m]*D[m][i] + color_num[1][m]*D[m][j] + color_num[2][m]*D[m][k]
                ans.append(tmp)

print(min(ans))