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 = [int(x) for x in input().split()]
D = [[int(x) for x in input().split()]for _ in range(C)]
C_grid = [[int(x) for x in input().split()] for _ in range(N)]
li=[[0]*C for _ in range(3)]
for i,s in enumerate(C_grid):
    for j,c in enumerate(s):
        li[(i+j)%3][c-1] += 1
ans = float('inf')
for x in range(C):
    for y in range(C):
        for z in range(C):
            diff = 0
            if(x==y or y==z or x==z):
                continue
            for i in range(C):
                diff += li[0][i]*D[i][x]
                diff += li[1][i]*D[i][y]
                diff += li[2][i]*D[i][z]
            ans = min(diff,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

#受け取り、初期化
N, C = getlist()
D = []
x0 = defaultdict(int)
x1 = defaultdict(int)
x2 = defaultdict(int)
for i in range(C):
	d = getlist()
	D.append(d)
for i in range(N):
	c = getlist()
	for j in range(N):
		if (i + j) % 3 == 0:
			x0[c[j]] += 1
		elif (i + j) % 3 == 1:
			x1[c[j]] += 1
		else:
			x2[c[j]] += 1

#D処理
cost0 = [0] * (C)
cost1 = [0] * (C)
cost2 = [0] * (C)
for i in range(C):
	for j in x0:
		cost0[i] += D[j - 1][i] * x0[j]
for i in range(C):
	for j in x1:
		cost1[i] += D[j - 1][i] * x1[j]
for i in range(C):
	for j in x2:
		cost2[i] += D[j - 1][i] * x2[j]

#最小値計算
ans = float("inf")
for i in range(C):
	for j in range(C):
		for k in range(C):
			val = cost0[i] + cost1[j] + cost2[k]
			if i != j and j != k and k != i:
				ans = min(ans, val)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,C = inpl()
d = []
c = []
for i in range(C):
    d.append(inpl())
for i in range(n):
    c.append(inpl())
d0 = defaultdict(int)
d1 = defaultdict(int)
d2 = defaultdict(int)
dd = [d0,d1,d2]
for y in range(n):
    for x in range(n):
        t = (x+y+2) % 3 
        dd[t][c[x][y]] += 1
# print(dd)
res = [[] for i in range(3)]
for i in range(C):
    for j in range(3):
        tmp = 0
        for key in dd[j].keys():
            tmp += d[key-1][i] * dd[j][key]
        res[j].append([i,tmp])   
for i in range(3):
    res[i].sort(key=lambda x:x[1])
# print(res)
ans = mod
for i in range(3):
    for j in range(3):
        for k in range(3):
            if res[0][i][0] == res[1][j][0] or res[0][i][0] == res[2][k][0] or res[2][k][0] == res[1][j][0]:
                continue
            ans = min(res[0][i][1]+res[1][j][1]+res[2][k][1], ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,C = inpl()
d = []
c = []
for i in range(C):
    d.append(inpl())
for i in range(n):
    c.append(inpl())
d0 = defaultdict(int)
d1 = defaultdict(int)
d2 = defaultdict(int)
for y in range(n):
    for x in range(n):
        if (x+y+2) % 3 == 0:
            d0[c[x][y]] += 1
        elif (x+y+2) % 3 == 1:
            d1[c[x][y]] += 1
        else:
            d2[c[x][y]] += 1
# print(d0)
# print(d1)
# print(d2)
res0 = []
res1 = []
res2 = []
for i in range(C):
    tmp = 0
    for key in d0.keys():
        tmp += d[key-1][i] * d0[key]
    res0.append([i,tmp])
    tmp = 0
    for key in d1.keys():
        tmp += d[key-1][i] * d1[key]
    res1.append([i,tmp])
    tmp = 0
    for key in d2.keys():
        tmp += d[key-1][i] * d2[key]
    res2.append([i,tmp])
res0.sort(key=lambda x:x[1])
res1.sort(key=lambda x:x[1])
res2.sort(key=lambda x:x[1])
# print(res0)
# print(res1)
# print(res2)
ans = mod
for i in range(3):
    for j in range(3):
        for k in range(3):
            if res0[i][0] == res1[j][0] or res0[i][0] == res2[k][0] or res2[k][0] == res1[j][0]:
                continue
            ans = min(res0[i][1]+res1[j][1]+res2[k][1], ans)
print(ans)

Submission status: Accepted

Solution code:
N,C =[int(x) for x in input().split()]
D = [[int(x) for x in input().split()] for _ in range(C)]
c = [[int(x) for x in input().split()] for _ in range(N)]
c1 = []
c2 = []
c3 = []
for i in range(1,N+1):
  for j in range(1,N+1):
    if (i+j)%3==0:
      c1.append(c[i-1][j-1])
    elif (i+j)%3==1:
      c2.append(c[i-1][j-1])
    elif (i+j)%3==2:
      c3.append(c[i-1][j-1])
su = 0
ans = 100000000000000
import collections as col
c1 = col.Counter(c1)
c2 = col.Counter(c2)
c3 = col.Counter(c3)
#print(c1,c2,c3)
for i in range(C):
  for j in range(i+1,C):
    for k in range(j+1,C):
      for a,b,c in [[i,j,k],[j,i,k],[k,j,i],[i,k,j],[k,i,j],[j,k,i]]:
        su = 0
        for l in range(1,C+1):
          #print(c1[l],c2[l],c3[l])
          su += D[l-1][a]*c1[l]+D[l-1][b]*c2[l]+D[l-1][c]*c3[l]
        ans = min(ans,su)
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)]


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

for i in range(N):
    for j in range(N):
        idx = (i+j)%3
        colornum[idx][c[i][j]-1] += 1
        
        
colors = list(range(C))
import itertools 

ans = 10**9+7
for v in itertools.permutations(colors,3):
    val = 0

    for i in range(3):
        x = v[i]
        for j in range(C):
            if x == j:continue
            val += colornum[i][j] * D[j][x]
            
    ans = min(ans,val)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

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

N,C = II()
D = []
for i in range(C):
    D.append(III())
c = []
for i in range(N):
    c.append(III())

d1 = []
d2 = []
d3 = []
for i in range(N):
    for j in range(N):
        if (i+j)%3==0:
            d1.append(c[i][j])
        elif (i+j)%3==1:
            d2.append(c[i][j])
        else:
            d3.append(c[i][j])

d1val = []
d2val = []
d3val = []

for cl in range(C):
    temp1 = 0
    temp2 = 0
    temp3 = 0
    for dcl in d1:
        temp1 += D[dcl-1][cl]
    for dcl in d2:
        temp2 += D[dcl-1][cl]
    for dcl in d3:
        temp3 += D[dcl-1][cl]
    d1val.append(temp1)
    d2val.append(temp2)
    d3val.append(temp3)

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
            else:
                temp = d1val[i]+d2val[j]+d3val[k]
                if temp<ans:
                    ans = temp

print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
arrd=[list(map(int,input().split())) for i in range(c)]
arrc=[list(map(int,input().split())) for i in range(n)]
field = [[0,0,0] for _ in range(c+1)]
ans = 10**9

for i in range(n):
  for j in range(n):
    field[arrc[i][j]][(i+j)%3] += 1
    
for p in range(1, c+1):
  for q in range(1, c+1):
    for r in range(1, c+1):
      if q != p:
        if r != p and r != q:
          tmp = 0
          for i in range(1, c+1):
            tmp += field[i][0]*arrd[i-1][p-1]
            tmp += field[i][1]*arrd[i-1][q-1]
            tmp += field[i][2]*arrd[i-1][r-1]
          ans = min(tmp, ans)
          
print(ans)

Submission status: Accepted

Solution code:
import collections

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

    if N == 1: return 0

    color = collections.defaultdict(dict)
    for i in range(N):
        for j in range(N):
            c = grid[i][j]
            k = (i+j+2) % 3
            color[k][c] = color[k].get(c, 0) + 1

    cost = []
    for k in color:
        temp = []
        for c1 in range(1, C+1):
            v = 0
            for c2 in color[k]:
                v += D[c2-1][c1-1] * color[k][c2]
            temp.append(v)
        cost.append(temp)

    # print(cost)
    # print(C)
    ans = float('inf')
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 != c2 and c2 != c3 and c3 != c1:
                    ans = min(ans, cost[0][c1]+cost[1][c2]+cost[2][c3])
    return ans


if __name__ == '__main__':
    print(main())

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

    cost = [[0] * C for j in range(3)]
    # 前処理
    for k in range(C):
        for i in range(N):
            for j in range(N):
                cost[(i+j)%3][k] += D[c[i][j]-1][k]

    # 全探索
    ans = float('inf')
    for i in range(C):
        for j in range(C):
            for k in range(C):
                if i != j and j != k and k != i:
                    ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])

    print(ans)





main()

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

mod = [[], [], []]

for i in range(N):
    for j in range(N):
        mod[(i+j)%3].append(c[i][j])

from collections import Counter

c = []
for i in range(3):
    c.append(Counter(mod[i]))

ans = float("inf")
for c_i in range(C):
    for c_j in range(C):
        if c_j == c_i:
            continue
        for c_k in range(C):
            if c_k == c_i or c_k == c_j:
                continue
            li = [c_i, c_j, c_k]
            sm = 0
            for i in range(3):
                counter = c[i]
                for k, v in counter.items():
                    sm += d[k-1][li[i]] * v

            ans = min(ans, sm)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, C = map(int, input().split())
D = []
for i in range(C):
  Ds = list(map(int, input().split()))
  D.append(Ds)
c = []
for i in range(N):
  cs = list(map(int, input().split()))
  cs = [c-1 for c in cs]
  c.append(cs)
ns = [[0]*C for i in range(3)]
for i in range(N):
  for j in range(N):
    ns[(i+j)%3][c[i][j]] += 1
#print(ns)
rs = []
for c0, c1, c2 in itertools.permutations(range(C), 3):
  r = 0
  for i in range(C):
    r += D[i][c0]*ns[0][i]
    r += D[i][c1]*ns[1][i]
    r += D[i][c2]*ns[2][i]
  rs.append(r)
r = min(rs)
print(r)

Submission status: Accepted

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

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

#print(colordata)

ans = 10**30

for color1 in range(C):
    for color2 in range(C):
        if color2 == color1:continue
        for color3 in range(C):
            if color1 == color3 or color2 == color3:continue
            now = 0
            for i in range(C):
                now += data[i][color1]*colordata[0][i]
            for i in range(C):
                now += data[i][color2]*colordata[1][i]
            for i in range(C):
                now += data[i][color3]*colordata[2][i]
            ans = min(ans,now)

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)]
r = [[(i + j + 2) % 3 for j in range(N)] for i in range(N)]
c0 = []
c1 = []
c2 = []
ans = 1000 * 500 * 500

for i in range(N):
    for j in range(N):
        if r[i][j] == 0:
            c0.append(c[i][j])
        elif r[i][j] == 1:
            c1.append(c[i][j])
        else:
            c2.append(c[i][j])

d0 = []

for i in range(C):
    d = 0
    for j in c0:
        d += D[j - 1][i]
    d0.append(d)

d1 = []
for i in range(C):
    d = 0
    for j in c1:
        d += D[j - 1][i]
    d1.append(d)

d2 = []
for i in range(C):
    d = 0
    for j in c2:
        d += D[j - 1][i]
    d2.append(d)

for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                ans = min(ans, d0[i] + d1[j] + d2[k])

print(ans)

Submission status: Accepted

Solution code:
def main():
    import itertools
    import sys
    input = sys.stdin.readline
    
    from collections import defaultdict
    
    N,C = map(int,input().split())
    
    D = [list(map(int,input().split())) for i in range(C)]
    c = [list(map(int,input().split())) for i in range(N)]
    
    ans = float("inf")
    zero = defaultdict(int)
    one = defaultdict(int)
    two = defaultdict(int)
    
    for i in range(N):
        for j in range(N):
            if (i+j)%3 == 0:
                zero[c[i][j]] += 1
            if (i+j)%3 == 1:
                one[c[i][j]] += 1
            if (i+j)%3 == 2:
                two[c[i][j]] += 1
    
    L = [i for i in range(1,C+1)]
    for i, j, k in itertools.permutations(L, 3):
        tmp = 0
        for l in range(1,C+1):
            tmp += D[l-1][i-1]*zero[l] + D[l-1][j-1]*one[l] + D[l-1][k-1]*two[l]
        if tmp < ans:
             ans = tmp
    print(ans)
    
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, C = LI()
    D = [[] for _ in range(C)]
    for i in range(C):
        D[i] = LI()
    color = [[] for _ in range(N)]
    for i in range(N):
        color[i] = LI()

    # まず各 mod の色の数を調べる。
    counters = [[0 for _ in range(C+1)] for _ in range(3)]
    for i in range(N):
        for j in range(N):
            counters[(i+j)%3][color[i][j]] += 1
    # print(counters)

    sums = [sum(i) for i in counters]

    # 各 mod について、各色を選んだときの違和感を計算する。
    import itertools
    def takemin(variable, val): variable = min(variable, val)
    iwakan = INF
    for selected_cols in itertools.permutations(range(1,C+1), 3):  # 30**3
        sum_ = 0
        for to_, counter  in zip(selected_cols, counters):  # 3
            for from_, num in enumerate(counter):  # 30
                if from_ == 0: continue
                sum_ += D[from_-1][to_-1] * num
        iwakan = min(iwakan, sum_)
    print(iwakan)

main()

Submission status: Accepted

Solution code:
import itertools
n,c=map(int,input().split())
ld=[list(map(int,input().split())) for i in range(c)]
lc=[list(map(int,input().split())) for i in range(n)]
ct=[[0 for i in range(c)] for i in range(3)]
for i in range(n):
  for j in range(n):
    ct[(i+j+2)%3][lc[i][j]-1]+=1
L=list(itertools.permutations([i for i in range(c)],3))
ans=[]
for i in range(len(L)):
  ct2=0
  for j in range(3):
    for k in range(c):
      ct2+=ld[k][L[i][j]]*ct[j][k]
  ans.append(ct2)
print(min(ans))

Submission status: Accepted

Solution code:
import itertools

n, c = [ int(v) for v in input().split() ]
d_list = [ [ int(v) for v in input().split() ] for i in range(c) ]
c_list = [ [ int(v)-1 for v in input().split() ] for i in range(n) ]
change_list = [ [0,0,0] for i in range(c) ]

for k in range(c):
    x, y, z = 0, 0, 0
    for i in range(n):
        for j in range(n):
            if (i + j) % 3 == 0:
                x += d_list[c_list[i][j]][k]
            elif (i + j) % 3 == 1:
                y += d_list[c_list[i][j]][k]
            elif (i + j) % 3 == 2:
                z += d_list[c_list[i][j]][k]
    change_list[k] = [x, y, z]

ans = 10**9
for i in itertools.permutations(range(c),3):
    x, y, z = i
    ans = min(ans, change_list[x][0] + change_list[y][1] + change_list[z][2])
print(ans)

Submission status: Accepted

Solution code:
#D問題
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)]
for i in range(N):
    for j in range(N):
        c[i][j]-=1
    

mod3 = [[0 for i in range(C)] for j in range(3)]
for i in range(N):
    for j in range(N):
        mod3[(i+j)%3][c[i][j]]+=1
        
c3 = [[0 for i in range(C)] for j in range(3)]
for i in range(3):
    for j in range(C):
        kari = 0
        for k in range(C):#kからjへ
            kari+=mod3[i][k]*D[k][j]
        c3[i][j] = kari
        
inf = float("inf")
MIN = inf

for i in range(C):
    C1 = c3[0][i]
    for j in range(C):
        if j != i:
            C2 = c3[1][j]
            for k in range(C):
                if k != i and k != j:
                    C3 = c3[2][k]
                    MIN = min(MIN,C1+C2+C3)
                    #print(C1,C2,C3)
                
if MIN != inf:
    print(MIN)
else:
    print(0)

Submission status: Accepted

Solution code:
import collections
import itertools


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

Ds = []

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


grid = []
for i in range(N):
    grid.append(list(map(int,input().split(" "))))
color_gird_count = [[0 for _ in range(C + 1)] for _ in range(3)]

for i in range(N):
    for j in range(N):
        c = grid[i][j]
        amari = (i + j + 2) % 3
        color_gird_count[amari][c] += 1
col_val = itertools.permutations(range(1,C + 1),3)
ans = 10** 23
for col in col_val: # 塗り替える色
    cot = 0
    for i in range(3):
        for from_c in range(0,C):
           cot += color_gird_count[i][from_c + 1] * Ds[from_c ][col[i] -1 ]
    ans = min(ans,cot)

print(ans)

Submission status: Accepted

Solution code:

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

D = []

for i in range(C):

    d = list(map(int,input().split()))

    D.append(d)

c = []

for i in range(N):

    cc = list(map(int,input().split()))
    c.append(cc)


lis1 = []
lis2 = []
lis3 = []

for c1 in range(C):

    c1 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 0 and c[i][j] != c1:

                now += D[c[i][j]-1][c1-1]

    lis1.append(now)


for c2 in range(C):

    c2 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 1 and c[i][j] != c2:

                now += D[c[i][j]-1][c2-1]

    lis2.append(now)


for c3 in range(C):

    c3 += 1

    now = 0

    for i in range(N):

        for j in range(N):

            if (i + j) % 3 == 2 and c[i][j] != c3:

                now += D[c[i][j]-1][c3-1]

    lis3.append(now)


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,lis1[i] + lis2[j] + lis3[k])

print (ans)

Submission status: Accepted

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

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)]
    mod_0 = [0 for _ in range(C)]
    mod_1 = [0 for _ in range(C)]
    mod_2 = [0 for _ in range(C)]
    for i in range(N):
        for j in range(N):
            if (i+j)%3 == 0:
                mod_2[c[i][j]-1] += 1
            if (i+j)%3 == 1:
                mod_0[c[i][j]-1] += 1
            if (i+j)%3 == 2:
                mod_1[c[i][j]-1] += 1
    INF = 10**10
    ans = 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,sum(mod_0[n]*D[n][i] for n in range(C))+\
                              sum(mod_1[n]*D[n][j] for n in range(C))+\
                              sum(mod_2[n]*D[n][k] for n in range(C)))
    print(ans)

if __name__ == "__main__":
    main()

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)]
    mod_0 = [0 for _ in range(C)]
    mod_1 = [0 for _ in range(C)]
    mod_2 = [0 for _ in range(C)]
    for i in range(N):
        for j in range(N):
            if (i+j)%3 == 0:
                mod_2[c[i][j]-1] += 1
            if (i+j)%3 == 1:
                mod_0[c[i][j]-1] += 1
            if (i+j)%3 == 2:
                mod_1[c[i][j]-1] += 1
    INF = 10**10
    ans = 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,sum(mod_0[n]*D[n][i] for n in range(C))+\
                              sum(mod_1[n]*D[n][j] for n in range(C))+\
                              sum(mod_2[n]*D[n][k] for n in range(C)))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import permutations

N, C = map(int, input().split())
D2d = np.array([list(map(int, input().split())) for _ in range(C)])
c2d = [list(map(int, input().split())) for _ in range(N)]

colors = [np.array([0 for _ in range(C)]) for i in range(3)]
for i in range(N) :
    for j in range(N) :
        colors[(i+j)%3][c2d[i][j]-1] += 1

ans = np.inf
for c0, c1, c2 in permutations(range(C), 3) :
    a = np.sum(D2d[:, c0]*colors[0]\
              +D2d[:, c1]*colors[1]\
              +D2d[:, c2]*colors[2])
    if a < ans :
        ans = a
print(ans)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
D=[list(map(int,input().split())) for _ in [0]*C]
c=[list(map(int,input().split())) for _ in [0]*N]
t=[[0]*C for _ in [0]*3]
for i in range(N):
    for j in range(N):
        t[(i+j)%3][c[i][j]-1]+=1
s=float('inf')
for i in range(C):
    for j in range(C):
        if j==i:continue
        for k in range(C):
            if k==i or k==j:continue
            s=min(s,sum(t[0][n]*D[n][i] for n in range(C))\
                   +sum(t[1][n]*D[n][j] for n in range(C))\
                   +sum(t[2][n]*D[n][k] for n in range(C)))
print(s)

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

def main():
    state = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for w in range(N):
            for h in range(N):
                cost = D[grid[h][w]-1][c]
                state[(h+w)%3][c] += cost

    for c1 in range(C):
        for c2 in range(C):
            if c1 == c2:
                continue
            for c3 in range(C):
                if c3 == c1 or c3 == c2:
                    continue
                cost = state[0][c1] + state[1][c2] + state[2][c3]
                if c1 == 0 and c2 == 1 and c3 == 2:
                    ans = cost
                    continue
                ans = min(cost, ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int, C: int, D: "List[List[int]]", c: "List[List[int]]"):
    """
    (x+y)%3が等しければ色も等しいので良いグリッドには色は3色しかない。
    これを利用して30C3種類全探索。
    """
    t = [[0 for _ in range(30)] for _ in range(3)]
    for i in range(N):
        for j in range(N):
            t[(i+j)%3][c[i][j]-1] += 1

    res = 1 << 30
    for i in range(C):
        for j in range(C):
            if i != j:
                for k in range(C):
                    if i != k and j != k:
                        tt = 0
                        for l in range(C):
                            tt += D[l][i] * t[0][l]
                        for l in range(C):
                            tt += D[l][j] * t[1][l]
                        for l in range(C):
                            tt += D[l][k] * t[2][l]
                        if tt < res:
                            res = tt
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import numpy as np
N, C = map(int,input().split())
D = np.array(list(list(map(int,input().split()))for i in range(C)))
c = list(list(map(int,input().split()))for i in range(N))
A = [np.array([0]*C) for i in range(3)]
for i in range(N):
    for j in range(N):
        A[(i+j)%3][c[i][j]-1] += 1
H = [[[(A[j]*D[:,i]).sum(),i] for i in range(C)] for j in range(3)]
X = [[]for i in range(3)]
for i in range(3):
    X[i] = sorted(H[i])[:3]
ans = float('inf')
for a,i in X[0]:
    for b,j in X[1]:
        for c,k in X[2]:
            if i != j != k != i:
                ans = min(ans,a+b+c)
print(ans)

Submission status: Accepted

Solution code:
# グリッドのセルは mod 3 で 3グループ（あまりが0, 1, 2）にわけられる。
# C の上限が 30 と小さいので色分けはせいぜい 24360 パターンしかない
# これらのパターンについて違和感を計算するが
# 愚直にやると少し遅い O(C^3 * N^2)
# C が小さいことを利用して、出現した色の数をカウンタで保持すると、C^3 * C になるので間に合う
# →解説も同様

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

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

from collections import Counter
groups = [Counter(), Counter(), Counter()]
for x in range(N):
    for y in range(N):
        groups[(x + y) % 3][grid[x][y]] += 1

# N <= 500
# Choose(N, 3) = 500 * 500 * 500 / 6
from itertools import permutations
import sys
m = 500 * 500 * 2000
for c1, c2, c3 in permutations(list(range(0, C)), 3):
    score = sum(D[c-1][c1] *cnt for c, cnt in groups[0].items())
    score += sum(D[c-1][c2] *cnt for c, cnt in groups[1].items())
    score += sum(D[c-1][c3] *cnt for c, cnt in groups[2].items())
    m = min(m, score)

print(m)

Submission status: Accepted

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

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

from collections import Counter
groups = [Counter(), Counter(), Counter()]
for x in range(N):
    for y in range(N):
        groups[(x + y) % 3][grid[x][y]] += 1

# N <= 500
# Choose(N, 3) = 500 * 500 * 500 / 6
from itertools import permutations
import sys
m = 500 * 500 * 2000
for c1, c2, c3 in permutations(list(range(0, C)), 3):
    score = sum(D[c-1][c1] *cnt for c, cnt in groups[0].items())
    score += sum(D[c-1][c2] *cnt for c, cnt in groups[1].items())
    score += sum(D[c-1][c3] *cnt for c, cnt in groups[2].items())
    m = min(m, score)

print(m)

Submission status: Accepted

Solution code:
INF = 10**18

def choice(c):
    for i in range(c):
        for j in range(c):
            if i == j:
                continue
            for k in range(c):
                if (i != k) and (j != k):
                    yield i,j,k

def solve(n, c, D, C):
    P = [{},{},{}]
    for y in range(n):
        for x in range(n):
            i = (x+y) % 3
            k = C[y][x] - 1
            if not k in P[i]:
                P[i][k] = 0
            P[i][k] += 1
    best = INF
    for v in choice(c):
        cur = 0
        for i in range(3):
            t = v[i]
            for s, num in P[i].items():
                cur += D[s][t] * num
        best = min(best, cur)
    return best

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)]
print(solve(n, c, D, C))