Problem:


Score : 400 points

Problem Statement

There is a grid with N rows and N columns of squares. Let (i,j) be the square at the i-th row from the top and the j-th column from the left.

These squares have to be painted in one of the C colors from Color 1 to Color C. Initially, (i,j) is painted in Color c_{i,j}.

We say the grid is a good grid when the following condition is met for all i,j,x,y satisfying 1 \leq i,j,x,y \leq N:

If (i+j) \% 3=(x+y) \% 3, the color of (i,j) and the color of (x,y) are the same.

If (i+j) \%  3 \neq (x+y) \% 3, the color of (i,j) and the color of (x,y) are different.

Here, X \% Y represents X modulo Y.

We will repaint zero or more squares so that the grid will be a good grid.

For a square, the wrongness when the color of the square is X before repainting and Y after repainting, is D_{X,Y}.

Find the minimum possible sum of the wrongness of all the squares.

Constraints

1 \leq N \leq 500

3 \leq C \leq 30

1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)

1 \leq c_{i,j} \leq C

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C
D_{1,1} ... D_{1,C}
:
D_{C,1} ... D_{C,C}
c_{1,1} ... c_{1,N}
:
c_{N,1} ... c_{N,N}

Output

If the minimum possible sum of the wrongness of all the squares is x, print x.

Sample Input 1

2 3
0 1 1
1 0 1
1 4 0
1 2
3 3

Sample Output 1

3

Repaint (1,1) to Color 2. The wrongness of (1,1) becomes D_{1,2}=1.

Repaint (1,2) to Color 3. The wrongness of (1,2) becomes D_{2,3}=1.

Repaint (2,2) to Color 1. The wrongness of (2,2) becomes D_{3,1}=1.

In this case, the sum of the wrongness of all the squares is 3.

Note that D_{i,j} \neq D_{j,i} is possible.

Sample Input 2

4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2

Sample Output 2

428



Sample input:
2 3
0 1 1
1 0 1
1 4 0
1 2
3 3


Sample output:
3

Submission status: Accepted

Solution code:
n,c = map(int,raw_input().split())

D = []
C = []

for a in range(c):
  D.append( map(int,raw_input().split()) )

for a in range(n):
  C.append( map(int,raw_input().split()) )

cs = [[] for j in range(3)]

for x in range(n):
  for y in range(n):
    cs[ (x+y) % 3 ].append(C[x][y])

c0 = [-1]
c1 = [-1]
c2 = [-1]

for x in range(1,c+1):
  buf = 0
  for y in cs[0]:
    buf += D[y-1][x-1]
  c0.append(buf)

for x in range(1,c+1):
  buf = 0
  for y in cs[1]:
    buf += D[y-1][x-1]
  c1.append(buf)

for x in range(1,c+1):
  buf = 0
  for y in cs[2]:
    buf += D[y-1][x-1]
  c2.append(buf)

ans = 10**100

for x in range(1,c+1):
  for y in range(1,c+1):
    if x == y:continue
    for z in range(1,c+1):
      if x == z or y == z:continue

      if ans > c0[x]+c1[y]+c2[z]:
        ans = c0[x]+c1[y]+c2[z]

print ans

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

import itertools
current_minimum = 1000 * 500 * 500 + 1
Z = []
Z.append([0]*C)
Z.append([0]*C)
Z.append([0]*C)
#print(Z)

for (i,j) in itertools.product(range(N),range(N)):
	cur_mod = ((i+1)+(j+1)) % 3
	cur_color = c[i][j]
	#print(cur_mod)
	#print(cur_color)
	Z[cur_mod][cur_color-1] += 1

current_minimum = 1000 * 500 * 500 + 1
for (c0,c1,c2) in itertools.permutations(range(C), 3):
	tmp = 0
	color = [c0,c1,c2]
	for cur_mod in range(3):
		target_color = color[cur_mod]
		for cur_color in range(C):
			tmp += Z[cur_mod][cur_color] * D[cur_color][target_color]
	if current_minimum >= tmp:
		current_minimum = tmp
print(current_minimum)

Submission status: Accepted

Solution code:
def main():
    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 = []
    for i in range(N):
        for j in range(N):
            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])
    c1_cost = [0 for _ in range(C)]
    c2_cost = [0 for _ in range(C)]
    c3_cost = [0 for _ in range(C)]
    for i in range(C):
        for cc in c1:
            c1_cost[i] += D[cc-1][i]
        for cc in c2:
            c2_cost[i] += D[cc-1][i]
        for cc in c3:
            c3_cost[i] += D[cc-1][i]
    cost = []
    for i in range(C):
        for j in range(C):
            if i!=j:
                for k in range(C):
                    if j!=k!=i:
                        cost.append(c1_cost[i]+c2_cost[j]+c3_cost[k])
    return min(cost)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N,C = map(int,input().split())
D=[[int(i) for i in input().split()] for j in range(C)]
co=[[int(i) for i in input().split()] for j in range(N)]
d0= defaultdict(int)
d1= defaultdict(int)
d2= defaultdict(int)
for i in range(N):
    for j in range(N):
        if (j+i) %3==0:
            d0[co[j][i]] +=1
        elif (j+i)%3==1:
            d1[co[j][i]] +=1
        else:
            d2[co[j][i]] +=1
A0=[]#i色に帰るのに必要な違和感
A1=[]
A2=[]
for i in range(C):
    iwa =0
    for s in d0.keys():
        iwa += D[s-1][i-1]*d0[s] 
    A0.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d1.keys():
        iwa += D[s-1][i-1]*d1[s] 
    A1.append([iwa,i])
for i in range(C):
    iwa =0
    for s in d2.keys():
        iwa += D[s-1][i-1]*d2[s] 
    A2.append([iwa,i])

A0.sort()
A1.sort()
A2.sort()
B=[[] for i in range(3)]
for i in range(3):
    B[0].append(A0[i])
for i in range(3):
    B[1].append(A1[i])
for i in range(3):
    B[2].append(A2[i])
ans =[]
for i in range(3):
    for j in range(3):
        for k in range(3):
            if B[0][i][1] ==B[1][j][1]:
                continue
            if B[0][i][1] ==B[2][k][1]:
                continue
            if B[1][j][1] ==B[2][k][1]:
                continue
            ans.append(B[0][i][0]+B[1][j][0]+B[2][k][0])
print(min(ans))

Submission status: Accepted

Solution code:
from itertools import product,permutations

N,C = map(int,input().split())
D = tuple(tuple(map(int,input().split())) for _ in range(C))
grid = tuple(tuple(map(int,input().split())) for _ in range(N))

cnt = [[0]*C for _ in range(3)]
for x,y in product(range(N),range(N)):
  cnt[(x+y)%3][grid[x][y]-1] += 1

print(min(sum(n*D[i][j] for s,j in zip(range(3),p) for i,n in enumerate(cnt[s])) for p in permutations(range(C), r=3)))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
line1 = [0]*C
line2 = [0]*C
line0 = [0]*C
for i in range(N):
  c = list(map(int, input().split()))
  for j in range(N):
    if (i+j)%3 == 0:
      line0[c[j]-1] +=+1
    if (i+j)%3 == 1:
      line1[c[j]-1] +=+1
    if (i+j)%3 == 2:
      line2[c[j]-1] +=+1
ans = float("inf")
#line0をi+1に、1をj+1に, 2をk+1にそろえよう
#print(line0,line1,line2)
for i in range(C):
  for j in range(C):
    if j !=i :
      for k in range(C):
        if k !=i and k!=j: 
#          print(i,j,k)
          curr = 0
          for l in range(C):
            curr += line0[l]*D[l][i]
            curr += line1[l]*D[l][j]
            curr += line2[l]*D[l][k]
#          print(curr)
          ans = min(ans, curr)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import permutations


n, c = map(int, input().split())

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

dd = np.array(dd)
cc = np.array(cc)

mod_list = np.zeros((3, c), dtype=np.int)

for i in range(n):
  for j in range(n):
    mod_list[(i+j)%3, cc[i,j]-1] += 1

iwakan_list = mod_list.dot(dd)
  
x = float('inf')
for i, j, k in permutations(range(c), 3):
  x = min(x, iwakan_list[0, i] + iwakan_list[1, j] + iwakan_list[2, k])
print(x)

Submission status: Accepted

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

xs = [[], [], []]

for i, row in enumerate(c):
    for j, x in enumerate(row):
        xs[(i + j) % 3].append(x)

cs = [[sum(D[x][j] for x in xs[i]) for j in range(C)] for i in range(3)]

result = 1000000000000000000000000

for c1 in range(C):
    for c2 in range(C):
        if c2 == c1:
            continue
        for c3 in range(C):
            if c3 == c1 or c3 == c2:
                continue
            r = cs[0][c1] + cs[1][c2] + cs[2][c3]
            result = min(result, r)
    
print(result)

Submission status: Accepted

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

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

for x in range(N):
	for y in range(N):
		Color[(x+y+2)%3][c[x][y]-1] += 1

ans = 1145141919810
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
			tmp = 0
			for x in range(3):
				for y in range(C):
					if x == 0:
						tmp += Color[x][y]*D[y][i]
					elif x == 1:
						tmp += Color[x][y]*D[y][j]
					else:
						tmp += Color[x][y]*D[y][k]
			ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product,permutations

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

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

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

# grid survey
cnt = [[0]*C for _ in range(3)]

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

def it():
  for p in permutations(range(C),r=3):
    yield sum(n*D[i][j] for s,j in zip(range(3),p) for i,n in enumerate(cnt[s]))

print(min(it()))

Submission status: Accepted

Solution code:
from itertools import permutations

n, c = [int(_) for _ in raw_input().split()]
d = [[int(_) for _ in raw_input().split()] for __ in xrange(c)]
st = [[0] * c for _ in range(3)]
for y in xrange(n):
    for x, g in enumerate(raw_input().split()):
        g = int(g) - 1
        st[(x + y) % 3][g] += 1


ds = [[
    sum(st[m3][oldc] * d[oldc][newc] for oldc in xrange(c))
    for newc in xrange(c)] for m3 in range(3)]

p = None
for c1, c2, c3 in permutations(range(c), 3):
    np = ds[0][c1] + ds[1][c2] + ds[2][c3]
    p = np if p is None else min(np, p)

print p

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

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

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

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


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations
from collections import Counter
def inpl(): return list(map(int, input().split()))
N, C = inpl()

D = [inpl() for _ in range(C)]

G = [Counter() for _ in range(3)]
for i in range(1, N+1):
    for j, c in enumerate(inpl(), start=1):
        G[(i+j)%3][c-1] += 1

ans = 10**9
for p, q, r in permutations(range(C), 3):
    tmp = 0
    for c in range(C):
        tmp += (D[c][p] * G[0][c]
              + D[c][q] * G[1][c]
              + D[c][r] * G[2][c])
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
c, d = [0] * n, [0] * k
for i in range(k): d[i] = [int(x) for x in input().split()]
for i in range(n): c[i] = [int(x) - 1 for x in input().split()]
z = {}
def f(k, m):
    if (k, m) in z: return z[(k, m)]
    s = 0
    for i in range(n):
        for j in range(n):
            if (i + j) % 3 == m:
                s += d[c[i][j]][k]
    z[(k, m)] = s
    return s
def g(i, s):
    if i == 3: return 0
    m = None
    for l in range(k):
        if s[l]: continue
        s[l] = True
        r = g(i + 1, s)
        s[l] = False
        if r is None: continue
        r += f(l, i)
        if m is None or r < m: m = r
    return m
print(g(0, [False] * k))

Submission status: Accepted

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

def calc(choice):
    ans = 0
    for i,v in zip(range(3),choice):
        for ind, cnt in enumerate(colors[i]):
            ans += cnt * D[ind][v]
    return ans
def dfs(lst, depth):
    ret = []
    if depth == 3:
        return calc(lst)
    for v in range(C):
        if v not in lst:
            lst.append(v)
            ret.append(dfs(lst, depth + 1))
            lst.pop()
    return min(ret)
print(dfs([], 0))

Submission status: Accepted

Solution code:
# 1. 入出力 (二次元配列)

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

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

ans = 1 << 60
info = [ [0 for j in range(C)] for i in range(3) ]

for i in range(N):
    for j in range(N):
        mod = (i + j) % 3
        info[mod][ col[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

            temp = 0
            lst = [i, j, k]

            for x in range(3):
                for y in range(C):
                    temp += D[y][ lst[x] ] * info[x][y]

            ans = min(ans, temp)
            # print(lst, temp)

print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
c = [list(map(int, input().split())) for i in range(N)]
col = [[0]*C for i in range(3)]
for i in range(N):
    ci = c[i]
    for j in range(N):
        cc = col[(i+j)%3]
        dd = D[ci[j]-1]
        for k in range(C):
            cc[k] += dd[k]
ans = 10**18
c0 = col[0]
c1 = col[1]
c2 = col[2]
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, c0[i] + c1[j] + c2[k])
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,c = LI()
    d = [LI() for _ in range(c)]
    e = [LI() for _ in range(n)]
    a = [[0]*c for _ in range(3)]
    for i in range(n):
        for j in range(n):
            t = (i+j) % 3
            for k in range(c):
                a[t][k] += d[e[i][j]-1][k]
    r = 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
                tr = a[0][i] + a[1][j] + a[2][k]
                if r > tr:
                    r = tr

    return r


print(main())

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

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

ans = 10 ** 9
for color in permutations(range(c), 3):
    tmp = 0
    for tgt, cnt in zip(color, dcnt):
        tmp += sum(d[i][tgt] * cnt[i] for i in range(c))
    ans = min(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    n, c = map(int, input().split())
    d = [list(map(int, input().split())) for _ in range(c)]

    
    # if I can change the color of the same square many times
    # Warshall-Floyd algorithm
    for k in range(c):
        for i in range(c):
            for j in range(c):
                if d[i][j] > d[i] + d[j]:
                    d[i][j] = d[i][j]
    

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

    counters = [[0] * c for _ in range(3)]
    for i in range(n):
        for j in range(n):
            counters[(i+j) % 3][color[i][j] - 1] += 1
    
    # full search
    cost = []
    for group in counters:
        l = []
        for i in range(c):
            num = 0
            for j in range(c):
                num += d[j][i] * group[j]
            l.append((num, i))
        l.sort()
        cost.append(l[c-3:])

    ans = 10 ** 9
    for i in range(3):
        for j in range(3):
            for k in range(3):
                if cost[0][i][1] != cost[1][j][1] and cost[1][j][1] != cost[2][k][1] and cost[2][k][1] != cost[0][i][1]:
                    if ans > cost[0][i][0] + cost[1][j][0] + cost[2][k][0]:
                        ans = cost[0][i][0] + cost[1][j][0] + cost[2][k][0]
    
    print(ans)

main()

Submission status: Runtime Error

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

from itertools import product

N, C = list(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)]

colors = [[0]*C for i in range(3)]
for i in range(N):
    tmp = list(map(int, input().split()))
    for j, color in enumerate(tmp):
        num = ((i+1) + (j+1)) % 3
        colors[num][color-1] += 1
# print(colors)

data = [[0]*C for i in range(3)]


for i in range(3):
    # color[i]
    for j in range(C):
        for k in range(C):
            data[i][k] += colors[i][j] * D[j][k]
# print(data)

ans = 10**10
for iter_ in product([0, 1, 2], repeat=C):
    if len(set(iter_)) != 3:
        continue
    tmp = []
    for i, j in enumerate(iter_):
        tmp.append(data[i][j])
    ans = min(ans, sum(tmp))
print(ans)

Submission status: Runtime Error

Solution code:
from  itertools import combinations
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)]
a=[[0]*C for _ in range(3)]
for i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in combinations(range(C),3):
	tmp=0
	for i in range(3):
		for j in range(30):
			tmp+=a[i][j]*d[j][v[i]]
	ans=min(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
from  itertools import combinations
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)]
a=[[0]*C for _ in range(3)]
for i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in combinations(range(C),3):
	tmp=0
	for i in range(3):
		for j in range(30):
			tmp+=a[i][j]*c[j][v[i]]
	ans=min(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
from  itertools import combinations
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)]
a=[[0]*C for _ in range(3)]
for i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in combinations(C,3):
	tmp=0
	for i in range(3):
		for j in range(30):
			tmp+=a[i][j]*c[j][v[i]]
	ans=min(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
from  itertools import combinations
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)]
a=[[0]*c for _ in range(3)]
for i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in combinations(c,3):
	tmp=0
	for i in range(3):
		for j in range(30):
			tmp+=a[i][j]*c[j][v[i]]
	ans=min(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
# D - Good Grid

from collections import defaultdict
import itertools

N, C = map(int, input().split())
D = [[0] * C for _ in range(C)]
for i in range(C):
    D[i] = list(int(d) for d in input().split())

# MOD3の世界で0,1,2ごとに、最初の値の数をカウントしておく
dict_c = [defaultdict(int) for _ in range(3)]
for i in range(N):
    c = list(int(x) for x in input().split())
    for j in range(N):
        dict_c[(i+j)%3][c[j]-1] += 1

# ここからは全探索。
# 0, 1, 2の各配列に対して、全ての色を試す(C**3)
list_C = list(range(C))
ans = 10**18
for (p, q, r) in itertools.permutations(list_C):
    tmp = 0
    for i, j in enumerate((p, q, r)):
        for m, n in dict_c[i].items():
            tmp += D[m][j] * n
    ans = min(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
# D - Good Grid

from collections import defaultdict
import itertools

N, C = map(int, input().split())
D = [[0] * C for _ in range(C)]
for i in range(C):
    D[i] = list(int(d) for d in input().split())

# MOD3の世界で0,1,2ごとに、最初の値の数をカウントしておく
dict_c = [defaultdict(int) for _ in range(3)]
for i in range(N):
    c = list(int(x) for x in input().split())
    for j in range(N):
        dict_c[(i+j)%3][c[j]-1] += 1
#print(D)
#print(dict_c)

# ここからは全探索。
# 0, 1, 2の各配列に対して、全ての色を試す(C**3)
list_C = list(range(C))
ans = 10**18
for (p, q, r) in itertools.permutations(list_C):
    tmp = 0
    for i, j in enumerate((p, q, r)):
        #print(p, q, r)
        for i, k in dict_c[i].items():
            #print(i, j, k)
            #print(D[i][j])
            tmp += D[i][j] * k
    #print(tmp)
    ans = min(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
N,C=map(int,input().split())
D=[list(map(int,input().split())) for i in range(C)]
A=[list(map(int,input().split())) for i in range(N)]
X=[[0]*C for i in range(3)]
for c in range(C):
  for i in range(N):
    for j in range(N):
      X[(i+j)%3][c]+=D[A[i][j]][c]
P=10**20
for i in range(C):
  for j in range(C):
    for k in range(C):
      if len(set([i,j,k]))==3:
        P=min(P,X[0][i]+X[1][j]+X[2][k])
print(P)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, C = mi()
D = li2(C)
S = li2(N)

table = dp2(0, 3, C)
'''
#for num in range(3):
    #for start in range(num, N, 3):
        for color in range(C):
            i = 0
            j = start
            print(i, j)
            while True:
                table[num][color] += D[S[i][j]-1][color]
                if j < 1 or i >= N:
                    break
                j -= 1
                i += 1
'''
for i in range(N):
    for j in range(N):
        for color in range(C):
            table[(i+j)%3][color] += D[S[i][j]-1][color]

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, table[0][i] + table[1][j] + table[2][k])

print(ans)

Submission status: Runtime Error

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

dct={}
for x in range(n):
  for y in range(n):
    for ci in range(nc):
      if (ci,(x+y)%3) in dct:
        dct[(ci,(x+y)%3)]+=d[c[x][y]-1][ci]
      else:
        dct[(ci,(x+y)%3)]=d[c[x][y]-1][ci]

def func(x,y,z): #(i+j)%=0をxに、=1をyに、=2をzに塗るときの違和感
  ret=dct[(x,0)]+dct[(y,1)]+dct[(z,2)]
  return ret
ans=float('inf')
for x in range(nc):
  for y in range(nc):
    if x==y:continue
    for z in range(nc):
      if x==z or z==y:continue
      ans=min(ans,func(x,y,z))
print(ans)
#print(dct)

Submission status: Runtime Error

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

discomforts = [[0]*(N+1)]
for _ in range(C):
    discomforts.append([0,*map(int,input().split())])
print(discomforts)
grid = [[0]*(N+1)]
for _ in range(N):
    grid.append([0,*map(int,input().split())])

color_counts = [[0]*(C+1) for i in range(3)]

for i in range(1,N+1):
    for j in range(1,N+1):
        color_counts[(i+j)%3][grid[i][j]] += 1

ans = float('inf')
for c0 in range(1,C+1):
    for c1 in range(1,C+1):
        for c2 in range(1,C+1):
            if c0 != c1 and c1 != c2 and c2 != c0:
                total = 0
                for i in range(1,C+1):
                    total += discomforts[i][c0]*color_counts[0][i]
                    total += discomforts[i][c1]*color_counts[1][i]
                    total += discomforts[i][c2]*color_counts[2][i]
                ans = min(ans,total)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

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

for i in range(N):
    for j in range(N):
        cij = c[i][j]
        a = (i + j + 2) % 3
        for k in range(C):
            memo[a][k] += d[cij-1][k]

ans = 25000000


for c1, c2, c3 in itertools.permutations(range(C), 3):
    ans = min(ans, memo[c1][0] + memo[c2][1] + memo[c3][2])

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

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

for i in range(N):
    for j in range(N):
        cij = c[i][j]
        a = (i + j + 2) % 3
        for k in range(C):
            memo[a][k] += d[cij-1][k]

ans = 25000000


for c1, c2, c3 in itertools.permutations(range(C), 3):
    ans = min(ans, memo[c1][0] + memo[c2][1] + memo[c3][2])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

mod_0=defaultdict(int)
mod_1=defaultdict(int)
mod_2=defaultdict(int)

for i in range(N):
    for j in range(N):
        n=(i+j+2)%3
        if n==0:
            mod_0[grid[i][j]]+=1
        elif n==1:
            mod_1[grid[i][j]]+=1
        else:
            mod_2[grid[i][j]]+=1

ans=float("inf")
for i in range(C):
    for j in range(C):
        if i==j:
            continue
        for k in range(C):
            if k in [i,j]:
                continue

            total
            for prev,cnt in mod_0.items():
                total+=D[prev-1][i]*cnt
            for prev,cnt in mod_1.items():
                total+=D[prev-1][j]*cnt
            for prev,cnt in mod_2.items():
                total+=D[prev-1][k]*cnt
            
            ans=min(ans,total)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N, Ma, Mb = map(int, input().split())
    yakuhin = []
    sa = 0
    sb = 0
    for i in range(N):
        yakuhin.append(list(map(int, input().split())))
        sa += yakuhin[i][0]
        sb += yakuhin[i][1]
    
    INF = 10**15
    DP = [[[INF for _ in range(sb+1)] for _ in range(sa+1)] for _ in range(N+1)]
    
    for i in range(N):
        DP[i][0][0] = 0
    
    for i in range(N):
        for j in range(sa+1):
            for k in range(sb+1):
                if(j >= yakuhin[i][0] and k >= yakuhin[i][1]):
                    DP[i+1][j][k] = min(DP[i][j][k], DP[i][j-yakuhin[i][0]][k-yakuhin[i][1]]+yakuhin[i][2])
                else:
                    DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k])
        
    ans = INF
    for i in range(1, N):
        for j in range(1, sa+1):
            for k in range(1, sb+1):
                if(j*Mb == k*Ma):
                    ans = min(ans, DP[i][j][k])    
        
    print(ans if ans != INF else -1)
    
main()

Submission status: Runtime Error

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

ans = float("inf")

for c0 in range(c):
  for c1 in range(c):
    if c0 == c1: continue
    for c2 in range(c):
      if c0 == c2 or c1 == c2: continue
      tmp = 0
      c = [c0,c1,c2]
      for y in range(n):
        for x in range(n):
          if lc[y][x] != c[(y+x)%3]: tmp += d[lc[y][x]][c[(y+x)%3]]
      ans = min(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations, combinations

n, c = map(int, sys.stdin.readline().split())
d = [[int(x) for x in sys.stdin.readline().split()] for _ in range(c)]
grid = [[int(x) - 1 for x in sys.stdin.readline().split()] for _ in range(n)]

cost = [[0] * 3 for _ in range(c)]
for i in range(n):
  for j in range(n):
    k = (i + j) % 3
    for l in range(c):
      cost[k][l] += d[grid[i][j]][l]
  
def main():
  res = []
  for comb in combinations(range(c), 3):
    for i, j, k in permutations(comb):
      res.append(cost[0][i] + cost[1][j] + cost[2][k])
  print(min(res))

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

n, c = map(int, sys.stdin.readline().split())
d = [[int(x) for x in sys.stdin.readline().split()] for _ in range(c)]
grid = [[int(x) - 1 for x in sys.stdin.readline().split()] for _ in range(n)]

cost = [[0] * 3 for _ in range(c)]
for i in range(n):
  for j in range(n):
    k = (i + j) % 3
    for l in range(c):
      cost[k][l] += d[grid[i][j]][l]
  
def main():
  res = []
  for i, j, k in permutations(range(c), 3):
    res.append(cost[0][i] + cost[1][j] + cost[2][k])
  print(min(res))

if __name__ == '__main__':
  main()