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 run(N, C, D, c):
    '''
    マス番号に応じて3色に塗る必要がある
    (i+j)%3が0, 1, 2それぞれに対して、何色が何個あるか計算しておく
    ある色に塗るコストを計算する
    0, 1, 2それぞれのC色のコストのパターンができる
    上記コストに対してC色から3色を選択する全パターンのうち最小のコストを求める
    '''
    color0 = {}
    color1 = {}
    color2 = {}
    for k in range(C):
        color0[k] = 0
        color1[k] = 0
        color2[k] = 0
    for i in range(N):
        for j in range(N):
            color = c[i][j] - 1
            if (i+j+2) % 3 == 0:
                color0[color] += 1
            elif (i+j+2) % 3 == 1:
                color1[color] += 1
            elif (i+j+2) % 3 == 2:
                color2[color] += 1
    cost0 = {}
    cost1 = {}
    cost2 = {}
    for k in range(C):
        cost0[k] = 0
        cost1[k] = 0
        cost2[k] = 0
        for i in range(C):
            cost = D[i][k]
            cost0[k] += cost * color0[i] 
            cost1[k] += cost * color1[i] 
            cost2[k] += cost * color2[i] 
    ret = max(cost0.values()) + max(cost1.values()) + max(cost2.values())
    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
                else:
                    ret = min(ret, cost0[i]+cost1[j]+cost2[k])
    return ret


def main():
    N, C = 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())))
    print(run(N, C, D, c))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations

N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
G = [list(map(int, input().split())) for i 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_0.append(G[i][j])
        if (i + j) % 3 == 1:
            mod_1.append(G[i][j])
        if (i + j) % 3 == 2:
            mod_2.append(G[i][j])

cost_0 = [sum([D[c - 1][color] for c in mod_0]) for color in range(C)]
cost_1 = [sum([D[c - 1][color] for c in mod_1]) for color in range(C)]
cost_2 = [sum([D[c - 1][color] for c in mod_2]) for color in range(C)]

ans = float('inf')
for p0, p1, p2 in permutations(range(C), 3):
    ans = min(ans, cost_0[p0] + cost_1[p1] + cost_2[p2])

print(ans)

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        x[(i+j)%3][c[i][j]-1]+=1
res=[]
for c1 in range(m):
    for c2 in range(m):
        for c3 in range(m):
            if c1==c2 or c2==c3 or c1==c3:
                pass
            else:
                ans=0
                for i in range(m):
                    ans+=x[0][i]*d[i][c1]
                for i in range(m):
                    ans+=x[1][i]*d[i][c2]
                for i in range(m):
                    ans+=x[2][i]*d[i][c3]
                res.append(ans)
print(min(res))

Submission status: Accepted

Solution code:
n,c = [int(i) for i in input().split()]
d = [[int(i) for i in input().split()]for i in range(c)]
#d[A][B] はAからBになるときの違和感
color = [[int(i) for i in input().split()]for i in range(n)]

devcol = [[0 for i in range(3)] for j in range(c)]
for l in range(n):
        for row in range(n):
            devcol[color[l][row]-1][(l+row)%3] += 1
Dsum = [[0 for i in range(3)] for j in range(c)]
for i in range(c):
    for j in range(c):
        for k in range(3):
            Dsum[i][k] += d[j][i]*devcol[j][k] 
D = Dsum[0][0]+Dsum[1][1]+Dsum[2][2]
for c0 in range (c):
    for c1 in range (c):
        if c1 == c0:
            continue
        for c2 in range (c):
            if c2 == c1 or c2 == c0:
                continue
            D = min(D,Dsum[c0][0]+Dsum[c1][1]+Dsum[c2][2])
#O(c^3)のつもり
print(D)

Submission status: Accepted

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

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

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


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

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

for i in range(n):
    for j in range(n):
        C[i][j] -= 1

cnt_color_by_r = [dict() for _ in range(3)]

for r in range(3):
    for clr in range(c):
        cnt_color_by_r[r][clr] = 0

for i in range(n):
    for j in range(n):
        cnt_color_by_r[(i + j) % 3][C[i][j]] += 1

costs = [[0 for _ in range(c)] for _ in range(3)]

for r in range(3):
    for after in range(c):
        cost = 0
        for before in range(c):
            cost += D[before][after] * cnt_color_by_r[r][before]
        costs[r][after] = cost

cost_r0 = list(sorted([(after, costs[0][after]) for after in range(c)], key=lambda x: x[1]))[:3]
cost_r1 = list(sorted([(after, costs[1][after]) for after in range(c)], key=lambda x: x[1]))[:3]
cost_r2 = list(sorted([(after, costs[2][after]) for after in range(c)], key=lambda x: x[1]))[:3]

ans = float('inf')
for c0, cost0 in cost_r0:
    for c1, cost1 in cost_r1:
        for c2, cost2 in cost_r2:
            if c0 != c1 and c1 != c2 and c2 != c0:
                ans = min(ans, cost0 + cost1 + cost2)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations

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

def e(conv):
    ret = 0
    for r in range(3):
        for i in range(C):
            ret += t[r][i]*D[i][conv[r]-1]

    return ret

ret = 10**10
for conv in permutations(range(1,C+1), 3):
    ret = min(ret, e(conv))

print(ret)

Submission status: Accepted

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

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

D_sum = [[0]*C for _ in range(3)]
for i in range(C):
    for j in range(C):
        for k in range(3):
            D_sum[k][j] += D[i][j] * c_sum[k][i]

ans = 1000*500*500
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
            else:
                ans = min(ans, D_sum[0][i]+D_sum[1][j]+D_sum[2][k])
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter

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

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

zero = []
one = []
two = []

for i, row in enumerate(mat_c):
    for j, col in enumerate(row):
        if (i+j+2) % 3 == 0:
            zero.append(col)
        elif (i+j+2) % 3 == 1:
            one.append(col)
        else:
            two.append(col)

zero_dict = dict(Counter(zero))
one_dict = dict(Counter(one))
two_dict = dict(Counter(two))
a = [zero_dict, one_dict, two_dict]


def make_color_patterns():
    color_pats = list(itertools.permutations(list(range(1, C + 1)), 3))
    return color_pats


def calc_D(i, col):
    aa = a[i]
    D = 0
    for k, v in aa.items():
        D += mat_D[k-1][col-1] * v
    return D


# print(mat_D, mat_c)

color_pats = make_color_patterns()

ans = float("inf")
for color_pat in color_pats:
    # print(color_pat)
    D0 = calc_D(0, color_pat[0])
    D0 = calc_D(0, color_pat[0])
    D1 = calc_D(1, color_pat[1])
    D2 = calc_D(2, color_pat[2])
    D = D0 + D1 + D2
    # print(D)
    ans = min(D, ans)

print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split()))for _ in range(c)]
l=[[i for i in[0]*c]for _ in range(3)]
for i in range(n):
  t=list(map(int,input().split()))
  for j in range(n):
    l[(i+j)%3][t[j]-1]+=1
a=10**18
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
      a=min(a,sum(d[x][i]*l[0][x]+d[x][j]*l[1][x]+d[x][k]*l[2][x]for x in range(c)))
print(a)

Submission status: Accepted

Solution code:
N, C = 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())))
ij = [[(i + j) % 3 for i in range(1, N + 1)] for j in range(1, N + 1)]
#print(ij)
color = [[0 for i in range(C)] for j in range(3)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        color[(i + j) % 3][c[i - 1][j - 1] - 1] += 1
#print(color)

cost = [[0 for i in range(C)] for j in range(3)]
for i in range(C): #(i + j) % 2 == 0
    cost[0][i] = 0
    for j in range(C):
        cost[0][i] += D[j][i] * color[0][j]
            
for i in range(C): #(i + j) % 2 == 1
    for j in range(C):
        cost[1][i] += D[j][i] * color[1][j]
                
for i in range(C): #(i + j) % 2 == 2
    for j in range(C):
        cost[2][i] += D[j][i] * color[2][j]

#print(cost)
minicost = 10000 * 500 * 500
for i in range(C):
    for j in range(C):
        if i != j:
            for k in range(C):
                if j != k and k != i:
                    if minicost > cost[0][i] + cost[1][j] + cost[2][k]:
                        minicost = cost[0][i] + cost[1][j] + cost[2][k]
print(minicost)

Submission status: Accepted

Solution code:
N, C = [int(i) for i in input().split(' ')]

dist = []

for _ in range(C):
    tmp = [int(x) for x in input().split(' ')]
    dist.append(tmp)

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

for i in range(1, N+1):
    for j, x in enumerate(input().split(' ')):
        j = j+1
        x= int(x)-1

        color_map[(i+j)%3][x] += 1

cost = float('inf')

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            tmp_cost = 0
            for i in range(C):
                tmp_cost += dist[i][c1] * color_map[0][i]
                tmp_cost += dist[i][c2] * color_map[1][i]
                tmp_cost += dist[i][c3] * color_map[2][i]
            
            cost = min(cost, tmp_cost)
if cost == float('inf'):
    cost = 0
print(cost)

Submission status: Accepted

Solution code:
n,c=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())))

#print(D)

C1=[]
C2=[]
C3=[]
for i in range(n):
    for j in range(n):
        f=(i+j)%3
        if f==0:
            C1.append(C[i][j])
        if f==1:
            C2.append(C[i][j])
        if f==2:
            C3.append(C[i][j])
        

miniwa=1000*500*500

#print(C3)
iwa1=[]
iwa2=[]
iwa3=[]

for cc in range(0,c):
    iwa1.append(sum(D[i-1][cc] for i in C1))
    iwa2.append(sum(D[i-1][cc] for i in C2))
    iwa3.append(sum(D[i-1][cc] for i in C3))

for c1 in range(0,c):
    for c2 in range(0,c):
        for c3 in range(0,c):
            if c1!=c2 and c2!=c3 and c3!=c1 :
                iwa=iwa1[c1]+iwa2[c2]+iwa3[c3]
                miniwa=min(miniwa,iwa)

print(miniwa)

Submission status: Accepted

Solution code:
def iin(): return int(input())
def nl(): return list(map(int, input().split()))
def ary(r, c, v): return [[v for _ in range(c)] for _ in range(r)]

N, C = nl()
d = [nl() for _ in range(C)]
c = [nl() for _ in range(N)]

color_count_by_r = []
for i in range(3):
    color_count_by_r.append(dict())
for i in range(N):
    for j in range(N):
        color_count_by_r[(i + j) % 3][c[i][j]] = color_count_by_r[(i + j) % 3].get(c[i][j], 0) + 1

ans = float('inf')
for c0 in range(1, C + 1):
    for c1 in range(1, C + 1):
        if c0 == c1:
            continue
        for c2 in range(1, C + 1):
            if c0 == c2 or c1 == c2:
                continue
            cost = 0
            for i in range(3):
                for j in range(1, C + 1):
                    next_color = [c0, c1, c2][i]
                    cost += color_count_by_r[i].get(j, 0) * d[j - 1][next_color - 1]
            ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())
atoz = [chr(i) for i in range(97,97+26)]

N,C = inpl()
Cost = [inpl() for i in range(C)]
Colors = [inpl() for i in range(N)]

nums_0 = [0]*(C+1)
nums_1 = [0]*(C+1)
nums_2 = [0]*(C+1)

for y in range(N):
	for x in range(N):
		if (x+y)%3 == 0:
			nums_0[Colors[y][x]] += 1
		elif (x+y)%3 == 1:
			nums_1[Colors[y][x]] += 1
		elif (x+y)%3 == 2:
			nums_2[Colors[y][x]] += 1

ans = INF
for c0 in range(1,C+1):
	for c1 in range(1,C+1):
		if c1 == c0: continue
		for c2 in range(1,C+1):
			if c2 == c1 or c2 == c0: continue
			tmp = 0
			for i in range(1,C+1):
				tmp += Cost[i-1][c0-1]*nums_0[i]
				tmp += Cost[i-1][c1-1]*nums_1[i]
				tmp += Cost[i-1][c2-1]*nums_2[i]
			ans = min(ans,tmp)

print(ans)

Submission status: Accepted

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

ans = float("inf")
for i in range(C):
    for j in range(C):
        if i!=j:
            for k in range(C):
                if i!=k and j!=k:
                    tmp = 0
                    for l in range(C):
                        tmp+=D[l][i]*c[0][l]
                    for l in range(C):
                        tmp+=D[l][j]*c[1][l]
                    for l in range(C):
                        tmp+=D[l][k]*c[2][l]
                    if tmp<ans:
                        ans=tmp

print(ans)

Submission status: Accepted

Solution code:
n, c = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(c)]
C = [[int(i) for i in input().split()] for j in range(n)]
 
X = [[0]*c for i in range(3)]
 
for i in range(n):
    for j in range(n):
        X[(i+j+2)%3][C[i][j]-1] += 1
 
cost = [[0]*c for i in range(3)]
 
for i in range(c):
    for j in range(c):
        cost[0][j] += X[0][i] * D[i][j]
        cost[1][j] += X[1][i] * D[i][j]
        cost[2][j] += X[2][i] * D[i][j]
 
ans = []
 
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                ans.append(cost[0][i] + cost[1][j] + cost[2][k])
 
print(min(ans))

Submission status: Accepted

Solution code:
import collections
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)]
c0 = []; c1 = []; c2 = []
for x in range(N):
    for y in range(N):
        if (x+y)%3 == 0:
            c0.append(c[x][y])
        elif (x+y)%3 == 1:
            c1.append(c[x][y])
        else:
            c2.append(c[x][y])
cnt0 = collections.Counter(c0)
cnt1 = collections.Counter(c1)
cnt2 = collections.Counter(c2)
m = N*N*1000
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                s = N*N*1000
            else:
                s = 0
                for n in range(C):
                  s += D[n][i]*cnt0[n+1] + D[n][j]*cnt1[n+1] + D[n][k]*cnt2[n+1]
            if s < m:
                m = s
print(m)

Submission status: Accepted

Solution code:
import itertools 
n,c = map(int,raw_input().split())
d = [map(int,raw_input().split()) for i in range(c)]
arr = [map(int,raw_input().split()) for i in range(n)]
coltable = [[0 for j in range(c)] for i in range(3)]

for i in range(n):
	for j in range(n):
		coltable[((i+1) + (j+1))%3][arr[i][j]-1] += 1

perm = list(itertools.permutations(range(c),3))

ans = float("inf")




for i in perm:
	point = 0

	for j in range(3):
		for k in range(c):
			point += d[k][i[j]] * coltable[j][k]


	ans = min(ans,point)

print ans

Submission status: Accepted

Solution code:
from itertools import permutations, product

N,C = map(int,input().split())
DM = [list(map(int, input().split())) for i in range(C)]

CM = [list(map(int, input().split())) for i in range(N)]

MODN = 3
# http://sonickun.hatenablog.com/entry/2014/06/13/132821
Cnum =  [[0 for i in range(C)] for j in range(MODN)]

# mod3に応じて、各色の個数をカウント
for i,j in product(range(N), range(N)):
  Cnum[(i+j)%MODN][CM[i][j] - 1] += 1

# mod3ごとの色番号をpermutationで全通り洗い出して、コスト全計算
ans = 1e9
for p,q,r in permutations(range(C), 3):
  cost = 0
  #print(p,q,r)
  for i in range(C):
    cost += Cnum[0][i] * DM[i][p] + Cnum[1][i] * DM[i][q] + Cnum[2][i] * DM[i][r]
  ans = min(ans, cost)
  
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

D=[0]
for i in range(C) :
	x=[0]+map( int, raw_input().split() )
	D.append(x)

c=[0]
for i in range(N) :
	x=[0]+map( int, raw_input().split() ) 
	c.append(x)

#S[mod 3][Color]
S= [ [ 0 for j in range(C+1) ] for i in range(3) ]

for color in range(1,C+1):
	for x in range(1,N+1):
		for y in range(1,N+1):
			mod=(x+y)%3
			S[mod][color]+=D[ c[x][y] ][color]		

ans=float("inf")
L=list(itertools.permutations(range(1,C+1),3))

for c1,c2,c3 in L:
	ans= min(ans, S[0][c1]+S[1][c2]+S[2][c3])

print ans

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import defaultdict

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

remains = {0: defaultdict(int), 1: defaultdict(int), 2: defaultdict(int)}
for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3][line[j]] += 1

INF = float('inf')

answer = INF
for choice in permutations(range(1, C+1), 3):
    _answer = 0
    for i, c in enumerate(choice):
        _answer += sum([D[r-1][c-1] * remains[i][r] for r in remains[i] if c != r])
    answer = min(answer, _answer)

print(answer)

Submission status: Accepted

Solution code:
from itertools import permutations
from collections import defaultdict

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

remains = {0: defaultdict(int), 1: defaultdict(int), 2: defaultdict(int)}
for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3][line[j]] += 1

INF = float('inf')

def recolor(x, y, count):
    return D[x-1][y-1] * count

answer = INF
for choice in permutations(range(1, C+1), 3):
    _answer = 0
    for i, c in enumerate(choice):
        _answer += sum([recolor(r, c, remains[i][r]) for r in remains[i] if c != r])
    answer = min(answer, _answer)

print(answer)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
 
D = []
c = []
 
for i in range(C):
    D.append(list(map(int,input().split())))
for i in range(N):
    c.append(list(map(int,input().split()))) 
 
c1 = []
c2 = []
c3 = []
 
from itertools import product
 
for i,j in product(range(N),repeat=2):
    if (i+j)%3 == 0:
        c1.append(c[i][j])
    elif (i+j)%3 == 1:
        c2.append(c[i][j])
    else:
        c3.append(c[i][j])
val=[]
cnt=[[],[],[]]
 
 
for j in range(C):
    cnt[0].append(c1.count(j+1))
    cnt[1].append(c2.count(j+1))
    cnt[2].append(c3.count(j+1))
 
for i in product(range(C),repeat=3):
    dif = 0
    if i[0]!=i[1] and i[1]!=i[2] and i[2]!=i[0]:
        for j in range(C):
            dif += D[j][i[0]] * cnt[0][j]
            dif += D[j][i[1]] * cnt[1][j]
            dif += D[j][i[2]] * cnt[2][j]
        val.append(dif)
 
print(min(val))

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)]
C = [list(map(int, input().split())) for _ in range(n)]

X = [[0] * c for i in range(3)]

for i, j in product(range(n), range(n)):
    # グリッドにある色を余りごとにカウント
    X[(i + j + 2) % 3][C[i][j] - 1] += 1

cost = [[0] * c for _ in range(3)]
for i, j in product(range(c), range(c)):
    # cost[0][k] -> 余りが0になる場所の色をkに変えるときのコスト
    cost[0][j] += X[0][i] * D[i][j]
    cost[1][j] += X[1][i] * D[i][j]
    cost[2][j] += X[2][i] * D[i][j]

ans = []
for s, t, u in permutations(range(c), r=3):
    ans.append(cost[0][s] + cost[1][t] + cost[2][u])
print(min(ans))

Submission status: Accepted

Solution code:
#%% D
from itertools import product, 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)]


X = [[0] * c for i in range(3)]

for i in range(n):
    for j in range(n):
        X[(i + j + 2) % 3][C[i][j] - 1] += 1

cost = [[0] * c for i in range(3)]

for i in range(c):
    for j in range(c):
        cost[0][j] += X[0][i] * D[i][j]
        cost[1][j] += X[1][i] * D[i][j]
        cost[2][j] += X[2][i] * D[i][j]

ans = []
for s, t, u in permutations(range(c), r=3):
    ans.append(cost[0][s] + cost[1][t] + cost[2][u])
print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np
buf = input().split()
N = int(buf[0])
C = int(buf[1])
D = np.zeros((C, C))
for i in range(C):
	buf = input().split()
	for j in range(C):
		D[i][j] = int(buf[j])

grid = np.zeros((3, C))
for i in range(N):
	buf = input().split()
	for j in range(N):
		groop = (i+1+j+1)%3
		bufcolor = int(buf[j])-1 
		grid[groop][bufcolor] += 1
#print(grid)

iwakan = np.zeros((3, C))
for groop in range(3):
	for color in range(C):
		iwakan[groop][color] = np.sum(grid[groop]*(D.T)[color])
#print(iwakan)

miniwakan = np.zeros((3, 3))
cminiwakan = np.zeros((3, 3))
for groop in range(3):
	buf = iwakan[groop]
	for best in range(3):
		mcolor = np.argmin(buf)
		miniwakan[groop][best] = buf[mcolor]
		cminiwakan[groop][best] = mcolor
		buf[mcolor] = np.max(buf)+1
#print(miniwakan)
#print(cminiwakan)
min = iwakan[0][0]+iwakan[1][1]+iwakan[2][2]
for i in range(3):
	for j in range(3):
		for k in range(3):
			bufmin = miniwakan[0][i] + miniwakan[1][j] + miniwakan[2][k]
			
			c0 = cminiwakan[0][i]
			c1 = cminiwakan[1][j]
			c2 = cminiwakan[2][k]
			#print(bufmin, c0, c1, c2)
			if((c0!=c1) and (c0!=c2) and (c1!=c2) and bufmin<min):
				min = bufmin
			#	print(min)

print(int(min))
					
			

# your code goes here

Submission status: Accepted

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

X = [[0]*c for i in range(3)]

for i in range(n):
    for j in range(n):
        X[(i+j+2)%3][C[i][j]-1] += 1

cost = [[0]*c for i in range(3)]

for i in range(c):
    for j in range(c):
        cost[0][j] += X[0][i] * D[i][j]
        cost[1][j] += X[1][i] * D[i][j]
        cost[2][j] += X[2][i] * D[i][j]

ans = []

for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                ans.append(cost[0][i] + cost[1][j] + cost[2][k])

print(min(ans))

Submission status: Accepted

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


mod3_1list = []
mod3_2list = []
mod3_0list = []
for i in range(N):
    for j in range(N):
        if (i+j+2) % 3 == 1:
            mod3_1list.append(M[i][j])
        if (i+j+2) % 3 == 2:
            mod3_2list.append(M[i][j])
        elif (i+j+2) % 3 == 0:
            mod3_0list.append(M[i][j])

mod3_0list = [mod3_0list.count(c) for c in range(1, C+1)]
mod3_1list = [mod3_1list.count(c) for c in range(1, C+1)]
mod3_2list = [mod3_2list.count(c) for c in range(1, C+1)]

ans = float("inf")
for c1 in range(1, C+1):
    for c2 in range(1, C+1):
        for c3 in range(1, C+1):
            if c1 != c2 and c2 != c3 and c1 != c3:
                mod3_0diff = [mod3_0list[c] * D[c][c1-1] for c in range(C)]
                mod3_1diff = [mod3_1list[c] * D[c][c2-1] for c in range(C)]
                mod3_2diff = [mod3_2list[c] * D[c][c3-1] for c in range(C)]
                ans = min(ans, sum(mod3_0diff) + sum(mod3_1diff) + sum(mod3_2diff))


print(ans)

Submission status: Accepted

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

D = []
for c in range(C):
    D.append([int(d) for d in input().split()])

Gmod = [[0 for i in range(C)] for i in range(3)]
for n in range(N):
    for m, g in enumerate(input().split()):
        Gmod[(n + m) % 3][int(g) - 1] += 1

K = []
for c0 in range(C):
    d0 = sum([Gmod[0][c] * D[c][c0] for c in range(C)])
    for c1 in [i for i in range(C) if not i == c0]:
        d1 = sum([Gmod[1][c] * D[c][c1] for c in range(C)])
        for c2 in [i for i in range(C) if (not i == c0) and (not i == c1)]:
            d2 = sum([Gmod[2][c] * D[c][c2] for c in range(C)])
            K.append(d0 + d1 + d2)

print(min(K))

Submission status: Accepted

Solution code:
import itertools
def m():
    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)]
    l = [[] for _ in range(3)]
    ans = [[] for _ in range(3)]
    for i in range(n):
        for j in range(n):
            l[(i+1+j+1) % 3].append(c[i][j])

    for k in range(3):
        for s in range(cn):
            cost = 0
            for p in l[k]:
                cost += d[p-1][s]
            ans[k].append((s,cost))

    for k in range(3):
        ans[k].sort(key=lambda x: x[1])

    result = 999999999
    for elem in itertools.permutations(range(3)):
        used = []
        tmp = 0
        for e in elem:
            i = 0
            while len(used) < 3:
                if ans[e][i][0] in used:
                    i += 1
                    continue
                tmp += ans[e][i][1]
                used.append(ans[e][i][0])
                break
        result = min(result, tmp)
    return result

print(m())

Submission status: Accepted

Solution code:
import numpy as np

n,c=map(int,input().split())
d=[]
for _ in range(c):
	d.append([int(i) for i in input().split()])
e=[]
for _ in range(n):
	e.append([int(i) for i in input().split()])
dd=np.matrix(d)

re=np.matrix([[0]*c for _ in range(3)])
for i in range(n):
	for j in range(n):
		re[(i+j)%3,e[i][j]-1]+=1

mul=np.dot(re,dd)
ind=np.argsort(mul)

ans=float('inf')
for i in range(3):
	for j in range(3):
		if ind[0,i]!=ind[1,j]:
			for k in range(3):
				if ind[0,i]!=ind[2,k] and ind[1,j]!=ind[2,k]:
					l=mul[0,ind[0,i]]+mul[1,ind[1,j]]+mul[2,ind[2,k]]
					if ans>l:
						ans=l
print(ans)

Submission status: Accepted

Solution code:
s=input().split()
n=int(s[0])
c=int(s[1])
d=[[0 for i in range(c+1)] for j in range(c+1)]
for i in range(c):
	s=input().split()
	for j in range(c):
		d[i+1][j+1]=int(s[j])
cnt=[[0 for i in range(c+1)],[0 for i in range(c+1)],[0 for i in range(c+1)]]
for i in range(n):
	s=input().split()
	for j in range(n):
		cnt[(i+j)%3][int(s[j])]+=1
		cnt[(i+j)%3][0]+=1
iwa=[[0 for i in range(c+1)],[0 for i in range(c+1)],[0 for i in range(c+1)]]
for i in range(1,c+1):
    for j in range(1,c+1):
        for k in range(3):
            iwa[k][i]+=d[j][i]*cnt[k][j]
m=10**9
for i in range(1,1+c):
    for j in range(1,1+c):
        for k in range(1,1+c):
            if i==j or j==k or k==i:
                continue
            m=min(m,iwa[0][i]+iwa[1][j]+iwa[2][k])
print(m)

Submission status: Accepted

Solution code:
from collections import Counter
N, C = map(int, input().split())
R = [[0]*C]*C
for i in range(C):
    *R[i], = map(int, input().split())
A = [0]*N
L0, L1, L2 = [], [], []
for i in range(N):
    *A, = map(int, input().split())
    for j in range(N):
        if (i+j+2)%3 == 0:
            L0 += [A[j]]
        elif (i+j+2)%3 == 1:
            L1 += [A[j]]
        else:
            L2 += [A[j]]
CL0 = Counter(L0)
CL1 = Counter(L1)
CL2 = Counter(L2)
K = 10**9
for i in range(1,C+1):
    for j in range(1,C+1):
        for k in range(1,C+1):
            if i == j or j == k or k == i:
                pass
            else:
                Y = 0
                for n in range(1,C+1):
                    Y += R[n-1][i-1]*CL0[n]
                for l in range(1,C+1):
                    Y += R[l-1][j-1]*CL1[l]
                for m in range(1,C+1):
                    Y += R[m-1][k-1]*CL2[m]
                K = min(K,Y)
    
print(K)