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:
import numpy as np
import itertools
import sys
input = sys.stdin.readline  #文字列入力では注意！

N,C = map(int,input().split())
D = np.array([list(map(int,input().split()))for _ in range(C)], dtype=np.int64)
c = np.array([list(map(int,input().split()))for _ in range(N)], dtype=np.int64)
c0 = np.zeros(C)
c1 = np.zeros(C)
c2 = np.zeros(C)
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            c0[c[i,j]-1] += 1
        if (i+j)%3 == 1:
            c1[c[i,j]-1] += 1
        if (i+j)%3 == 2:
            c2[c[i,j]-1] += 1
# c0~2はXの情報
lis = itertools.permutations([i for i in range(C)],3)
ans = float("inf")
for l0,l1,l2 in lis:    # l0~2はYの情報
    tmp = np.sum(D[:,l0]*c0+D[:,l1]*c1+D[:,l2]*c2, dtype=np.int64)
    ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np 
from itertools import permutations

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, C = I[:2]
cost = I[2:2+C**2].reshape(C, C)
color = I[2+C**2:].reshape(n, n) - 1

def main():
    mod_3 = (np.arange(1, n+1)[:, None] + np.arange(1, n+1)) % 3
    c0 = np.bincount(color[mod_3 == 0], minlength=C)
    c1 = np.bincount(color[mod_3 == 1], minlength=C)
    c2 = np.bincount(color[mod_3 == 2], minlength=C)

    r = np.arange(C)
    s0 = np.sum(cost[:, r] * c0[:, None], axis=0)
    s1 = np.sum(cost[:, r] * c1[:, None], axis=0)
    s2 = np.sum(cost[:, r] * c2[:, None], axis=0)

    ans = float('inf')
    for i, j, k in permutations(range(C), 3):
        res = s0[i] + s1[j] + s2[k]
        ans = min(ans, res)
    return ans

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

Submission status: Accepted

Solution code:
import sys
import numpy as np 
from itertools import permutations

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, C = I[:2]
cost = I[2:2+C**2].reshape(C, C)
color = I[2+C**2:].reshape(n, n) - 1

def main():
    mod_3 = (np.arange(1, n+1)[:, None] + np.arange(1, n+1)) % 3
    c0 = np.bincount(color[mod_3 == 0], minlength=C)
    c1 = np.bincount(color[mod_3 == 1], minlength=C)
    c2 = np.bincount(color[mod_3 == 2], minlength=C)

    ans = float('inf')
    for i, j, k in permutations(range(C), 3):
        res = np.sum(c0 * cost[:, i])
        res += np.sum(c1 * cost[:, j])
        res += np.sum(c2 * cost[:, k])
        ans = min(ans, res)
    return ans

if __name__ == '__main__':
    ans = main()
    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)]
cd=[[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        cd[(i+j)%3].append(c[i][j]-1)
cost=[[0]*C for _ in range(3)]
for i in range(3):
    for j in range(C):
        for x in cd[i]:
            cost[i][j]+=D[x][j]
#print(cost)
from itertools import product
import pprint
A=list(product(range(C),repeat=3))
#print(A)
ans=float("inf")
for a in A:
    if a[0]==a[1] or a[1]==a[2] or a[2]==a[0]:
        continue
    cnt=0
    for i in range(3):
        cnt+=cost[i][a[i]]
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

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

Data2 = [{},{},{}]

for h in range(N):
    for w in range(N):
        c = Data[h][w]
        m = (h + w) % 3
        if not c in Data2[m]:
            Data2[m][c] = 0 
        Data2[m][c]+=1

ans = 10**20
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 = 0
            for k,v in Data2[0].items():
                tmp += (Color[k-1][c1-1]*v)
            for k,v in Data2[1].items():
                tmp += (Color[k-1][c2-1]*v)
            for k,v in Data2[2].items():
                tmp += (Color[k-1][c3-1]*v)
            ans = min(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

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

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

ans = N * N * 1000 + 10
for color in permutations(range(C), 3):
    dis = 0
    for i in range(3):
        for j in range(C):
            d = D[j][color[i]]
            num = cnt[i][j]
            dis += d * num

    ans = min(ans, dis)

print(ans)

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    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)]

    mode={0:{i:0 for i in range(C)},1:{i:0 for i in range(C)},2:{i:0 for i in range(C)}}

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

    ans=1e10

    for i in range(C):
        for j in range(C):
            if i!=j:
                for k in range(C):
                    if i!=k and j!=k:
                        temp=0
                        for l in range(C):
                            temp+=D[l][i]*mode[0][l]
                            temp+=D[l][j]*mode[1][l]
                            temp+=D[l][k]*mode[2][l]
                        ans=min(ans,temp)

    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
a = [list(map(int, input().split())) for _ in range(n)]
zer, one, two = Counter(), Counter(), Counter()
for i, l in enumerate(a):
	for j, x in enumerate(l):
		x -= 1
		if (i + j) % 3 == 0:
			zer[x] += 1
		elif (i + j) % 3 == 1:
			one[x] += 1
		else:
			two[x] += 1
ans = 1 << 30
for f in range(c):
	for s in range(c):
		if f == s:
			continue
		for t in range(c):
			if f == t or s == t:
				continue
			cand = sum(d[k][f] * v for k, v in zer.items()) + sum(d[k][s] * v for k, v in one.items()) + sum(d[k][t] * v for k, v in two.items())
			if ans > cand:
				ans = cand
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import combinations, permutations

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

N, C = MAP()
table = build_grid(C, C, 0, int)
grid = build_grid(N, N, 0, int)

# mod3=0,1,2と色毎で数を集計
cnts = list2d(3, C, 0)
for i in range(N):
    for j in range(N):
        c = grid[i][j] - 1
        cnts[(i+j)%3][c] += 1

# 全色から3色選んで、0,1,2どこに使うかを全通り試す
ans = INF
for comb in combinations(range(C), 3):
    for perm in permutations(comb):
        sm = 0
        for i, to in enumerate(perm):
            for frm in range(C):
                cnt = cnts[i][frm]
                sm += table[frm][to] * cnt
        ans = min(ans, sm)
print(ans)

Submission status: Accepted

Solution code:
def main():
    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)]
    base = [[((i+1)+(j+1)) % 3 for j in range(N)] for i in range(N)]
    d = [{i: 0 for i in range(1, C + 1)} for j in range(3)]
    for i in range(N):
        for j in range(N):
            d[base[i][j]][c[i][j]] += 1

    ans = 1 << 60
    from itertools import combinations, permutations
    for comb in combinations(range(1, C+1), 3):
        for p in permutations(comb):
            cur = 0
            for i in range(3):
                for k, v in d[i].items():
                    cur += D[k-1][p[i]-1] * v
            ans = min(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,C=MI()
    D=LLIN(C)
    c=LLIN(N)
    group = [defaultdict(int) for _ in range(3)]
    for i in range(N):
        for j in range(N):
            col = c[i][j]-1
            group[(i+j)%3][col]+=1
    
    ans = inf
    Colors = [i for i in range(C)]
    for it in permutations(Colors,r=3):
        tmp = 0
        for i,col in enumerate(it):
            for col_ori,num in group[i].items():
                tmp += D[col_ori][col]*num

        ans = min(ans, tmp)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

for cc in range(C):
  for i in range(N):
    for j in range(N):
      cost[(i+j)%3][cc] += D[c[i][j]-1][cc]
#print(cost)

answer = []
comb =[i for i in range(C)]
for v in itertools.permutations(comb, 3):
  answer.append(sum([cost[j][v[j]] for j in range(3)]))
print(min(answer))

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

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

dic = [defaultdict(int) for _ in range(3)]

for i in range(n):
    for j in range(n):
        dist = (i+j) % 3
        num = C[i][j] - 1
        dic[dist][num] += 1


value = [[] for _ in range(3)]
for distance in range(3):
    count_dic = dic[distance]
    for color in range(c):
        res = 0
        for num, count in count_dic.items():
            point = D[num][color] * count
            res += point

        value[distance].append([res, color])

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

A = value[0][:3]
B = value[1][:3]
C = value[2][:3]

ans = 10**9
patterns = itertools.product(A, B, C)
for pattern in patterns:
    (v1, color1), (v2, color2), (v3, color3) = pattern
    check = {color1, color2, color3}
    if len(check) != 3:
        continue
    ans = min(ans, v1+v2+v3)

print(ans)

Submission status: Accepted

Solution code:
import collections
import itertools

def solve():
    N,C = map(int, input().split())
    transform = [list(map(int, input().split())) for _ in range(C)]
    counter = [[0]*C, [0]*C, [0]*C]
    for i in range(N):
        S = list(map(int, input().split()))
        # print(S)
        # print(S[0::3],S[1::3],S[2::3])
        for j in S[0::3]: counter[i%3][j-1] += 1
        for j in S[1::3]: counter[(i+1)%3][j-1] += 1
        for j in S[2::3]: counter[(i+2)%3][j-1] += 1 
    
    trans_0 = [sum( transform[j][i]*counter[0][j] for j in range(C) ) for i in range(C)]
    trans_1 = [sum( transform[j][i]*counter[1][j] for j in range(C) ) for i in range(C)]
    trans_2 = [sum( transform[j][i]*counter[2][j] for j in range(C) ) for i in range(C)]
    # print(counter)
    # print(trans_0,trans_1,trans_2)
    ret = min([trans_0[i]+trans_1[j]+trans_2[k] for (i,j,k) in itertools.product(range(C),repeat = 3)
               if i != j and j != k and k != i])
    # print(all_combination)
    print(ret)
    
solve()

Submission status: Accepted

Solution code:
n,c1 = map(int, input().split())
d = []
c = []
for i in range(c1):
    di = list(map(int, input().split( )))
    d.append(di)


for i in range(n):
    ci = list(map(int, input().split( )))
    c.append(ci)
    for j in range(n):
        c[i][j]-=1

"""
for cij in range(n):
        cij-=1
だとリストの内容は変化しない
"""

cost_c = [[0]*c1 for i in range(3)]

for t in range(n*n):
    i = t//n
    j = t%n
    md = (i+j)%3
    for cy in range(c1):
        try:
            cx = c[i][j]
            cost = d[cx][cy]
            cost_c[md][cy]+= cost
        except:
            print(d,cx,cy)
ans = 10**10
for x in range(c1):
    for y in range(c1):
        if x==y:
            continue
        for z in range(c1):
            if x==z or y==z:
                continue
            ans = min(ans, cost_c[0][x]+cost_c[1][y]+cost_c[2][z])
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

def main():
    N, C = map(int, input().split())
    D = list(list(map(int, input().split())) for _ in range(C))
    c = list(list(map(int, input().split())) for _ in range(N))
    cost = [[0] * (C + 5) for _ in range(3)]

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

    ans = float('inf')

    for a, b, c in permutations(range(1,C+1), 3):
        tmp = cost[0][a] + cost[1][b] + cost[2][c]
        ans = min(tmp, ans)

    print(ans)


    







if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

c = [0 for i in range(n)]
for i in range(n):
    c_xy =  list(map(int,input().split()))
    c[i] = c_xy

li0 = [0 for i in range(C)]
li1 = [0 for i in range(C)]
li2 = [0 for i in range(C)]

for i in range(n):
    for j in range(n):
        a=i+1
        b=j+1
        if (a+b)%3==0:
            li0[c[i][j]-1] += 1
        elif (a+b)%3==1:
            li1[c[i][j]-1] += 1
        elif (a+b)%3==2:
            li2[c[i][j]-1] += 1

ans = (10**3)*500*500


for c0 in range(C):
    for c1 in range(C):
        for c2 in range(C):
            cst = 0
            if (c0==c1) or (c1==c2) or (c2==c0):
                continue

            for i in range(C):
                cst += d[i][c0]*li0[i]
                cst += d[i][c1]*li1[i]
                cst += d[i][c2]*li2[i]
            ans = min(ans,cst)

print(ans)

Submission status: Accepted

Solution code:
n,d=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(d)]
cost=[[0]*d for _ in range(3)]
c=[list(map(int,input().split())) for _ in range(n)]
for i in range(n):
    for j in range(n):
        cost[(i+j)%3][c[i][j]-1]+=1
import itertools
ans=10**18
s=0
for p in itertools.permutations(range(1,d+1),3):
    for i in range(3):
        for j in range(d):
            s+=D[j][p[i]-1]*cost[i][j]
    if s<ans:
        ans=s    
    s=0
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations
n, c = [int(i) for i in sys.stdin.readline().split()]
D = dict()
C = dict()
MOD_dict = {i : [0 for j in range(30)] for i in range(3)}
INF = 10 ** 18
for i in range(c):
    inp = [int(i) for i in sys.stdin.readline().split()]
    D[i] = inp
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    C[i] = inp
    for j, k in enumerate(inp):
        MOD_dict[(i+j) % 3][k] += 1
best = INF
for perm in permutations(range(c), 3):
    cost = 0
    for i in range(c):
        cost += MOD_dict[0][i] * D[i][perm[0]] +  MOD_dict[1][i] * D[i][perm[1]] + \
                MOD_dict[2][i] * D[i][perm[2]]
    best = min(cost, best)
print(best)

Submission status: Accepted

Solution code:
from collections import Counter
N,C=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(C)]
Grid=[[] for _ in range(3)]
for i in range(N):
  c=list(map(int,input().split()))
  for j in range(N):
    Grid[(i+j)%3].append(c[j])

for i in range(3):
  Grid[i]=Counter(Grid[i])

ans=float("inf")
for i in range(1,C+1):  
  for j in range(1,C+1):
    for k in range(1,C+1):
      if i!=j and j!=k and k!=i:
        an=0
        for g1 in Grid[0]:
          an+=D[g1-1][i-1]*Grid[0][g1]
        for g2 in Grid[1]:
          an+=D[g2-1][j-1]*Grid[1][g2]
        for g3 in Grid[2]:
          an+=D[g3-1][k-1]*Grid[2][g3]
        ans=min(ans,an)
        
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)]

G1 = [0]*C
G2 = [0]*C
G3 = [0]*C
a = int(0)

for i in range(N):
    for j in range(N):
        if (i + j) % 3 ==2:
            G1[c[i][j]-1] += 1
        elif (i + j) % 3 == 0:
            G2[c[i][j]-1] += 1
        else:
            G3[c[i][j]-1] += 1
ans_candi = []


for i1 in range(C):
    for i2 in range(C):
        for i3 in range(C):
            t = int(0)
            if i1!=i2 and i2!=i3 and i3!=i1:
                for j in range(C):
                    t += D[j][i1]*G1[j]
                for j in range(C):
                    t += D[j][i2]*G2[j]
                for j in range(C):
                    t += D[j][i3]*G3[j]
                ans_candi.append(t)

print(min(ans_candi))

Submission status: Accepted

Solution code:
from itertools import permutations
N, C = map(int, input().split())

d = [[0]*C for i in range(C)]
for i in range(C):
  d[i] = [int(c) for c in input().split()]

grid = [[0]*C for i in range(3)]
for i in range(N):
  inf = [int(c)-1 for c in input().split()]
  for j in range(N):
    x = (j+i+2)%3
    g = inf[j]
    grid[x][g] += 1

record = [[0]*C for i in range(3)]
for i in range(3):
  for j in range(C):
    m = 0
    for h in range(C):
      m += grid[i][h]*d[h][j]
    record[i][j] = m

ans = 10**9
seq = range(C)
for i,j,h in permutations(seq,3):
  m = record[0][i]+record[1][j]+record[2][h]
  if m<ans:
    ans = m
    
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)]
ans0=[0]
ans1=[0]
ans2=[0]
for k in range(1,m+1):
    a0=0
    a1=0
    a2=0
    for i in range(n):
        for j in range(n):
            if (i+j+2)%3==0:
                a0+=d[c[i][j]-1][k-1]
            elif (i+j+2)%3==1:
                a1+=d[c[i][j]-1][k-1]
            else:
                a2+=d[c[i][j]-1][k-1]
    ans0.append(a0)
    ans1.append(a1)
    ans2.append(a2)
ans=float("inf")
import itertools
for x,y,z in itertools.permutations(range(1,m+1),3):
    ans=min(ans,ans0[x]+ans1[y]+ans2[z])

print(ans)

Submission status: Accepted

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

d=[[0 for x in range(C)] for y in range(3)]
for i in range(N):
  for j in range(N):
    d[(i+j)%3][c[i][j]]+=1

a=10**9
for c0 in range(C):
  for c1 in range(C):
    for c2 in range(C):
      if c0!=c1 and c1!=c2 and c0!=c2:
        a=min(a,sum([d[0][c]*D[c][c0]+d[1][c]*D[c][c1]+d[2][c]*D[c][c2] for c in range(C)]))
print(a)

Submission status: Accepted

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

d=[[0 for x in range(C)] for y in range(3)]
for i in range(N):
  for j in range(N):
    d[(i+j)%3][c[i][j]] += 1

a=10**9
for c0 in range(C):
  for c1 in range(C):
    for c2 in range(C):
      if c0==c1 or c1==c2 or c0==c2:
        continue
      s=0
      for c in range(C):
        s += d[0][c]*D[c][c0]+d[1][c]*D[c][c1]+d[2][c]*D[c][c2]
      a=min(a,s)
print(a)

Submission status: Accepted

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

d=[[0 for x in range(C)] for y in range(3)]
for i in range(N):
  for j in range(N):
    d[(i+j)%3][c[i][j]] += 1

a=10**9
for c0 in range(C):
  for c1 in range(c0+1,C):
    for c2 in range(c1+1,C):
      s1,s2,s3,s4,s5,s6=0,0,0,0,0,0
      for c in range(C):
        s1 += d[0][c]*D[c][c0]+d[1][c]*D[c][c1]+d[2][c]*D[c][c2]
        s2 += d[0][c]*D[c][c0]+d[1][c]*D[c][c2]+d[2][c]*D[c][c1]
        s3 += d[0][c]*D[c][c1]+d[1][c]*D[c][c0]+d[2][c]*D[c][c2]
        s4 += d[0][c]*D[c][c1]+d[1][c]*D[c][c2]+d[2][c]*D[c][c0]
        s5 += d[0][c]*D[c][c2]+d[1][c]*D[c][c0]+d[2][c]*D[c][c1]
        s6 += d[0][c]*D[c][c2]+d[1][c]*D[c][c1]+d[2][c]*D[c][c0]
      a=min(a,s1,s2,s3,s4,s5,s6)
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())))
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
p=[[0 for j in range(c)] for i in range(3)]
for i in range(n):
    for j in range(n):
        p[(i+1+j+1)%3][l[i][j]-1]+=1
ans=10**10
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i!=j and i!=k and j!=k:
                t=0
                for x in range(c):
                    t+=d[x][i]*p[0][x]
                    t+=d[x][j]*p[1][x]
                    t+=d[x][k]*p[2][x]
                ans=min(ans,t)
print(ans)

Submission status: Accepted

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

dll = []
for _ in range(c):
    dl = list(map(int,input().split()))
    dll.append(dl)

cll = []
for _ in range(n):
    cl = list(map(int,input().split()))
    cll.append(cl)


d_sum = [[0 for i in range(c)] for j in range(3)]

for i in range(c):
    for j in range(n):
        for k in range(n):
            d_sum[(j+k) % 3][i] += dll[cll[j][k]-1][i]

import itertools
c_set = [i for i in range(c)]
c_list = list(itertools.permutations(c_set, 3)) 

ans = float("inf")  
for c1, c2, c3 in c_list:
    tmp = d_sum[0][c1] + d_sum[1][c2] + d_sum[2][c3]
    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    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)]
    t = [[0]*C for i in range(3)]
    ans = float("inf")
    for i in range(N):
        for j in range(N):
            t[(i+j)%3][c[i][j]-1] += 1
    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]+D[l][j]*t[1][l]+D[l][k]*t[2][l]
                        ans = min(ans,tt)
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,c=map(int,input().split())
    D=[list(map(int,input().split())) for _ in range(c)]
    grid=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
    C=[[0]*c for _ in range(3)]

    # grid の色の集計をしておく (O(n^2))
    from itertools import product
    for i,j in product(range(n),repeat=2):
        col=grid[i][j]
        C[(i+j)%3][col]+=1

    # 3つそれぞれをどの色に変更するかを決めてスコアを計算する (O(c^4))
    ans=INF
    for u,v,w in product(range(c),repeat=3):
        if(u==v or v==w or w==u): continue
        score=0
        for col in range(c):
            score+=C[0][col]*D[col][u]
            score+=C[1][col]*D[col][v]
            score+=C[2][col]*D[col][w]
        ans=min(ans,score)

    print(ans)
resolve()

Submission status: Accepted

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

def solve(N: int, C: int, D: "List[List[int]]", c: "List[List[int]]"):
    answer = 10**9

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


    for i in range(1,N+1):
        for j  in range(1,N+1):
            cost[(i+j)%3][c[i-1][j-1]-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
                a = 0
                for index in range(C):
                    a += cost[0][index]*D[index][i]
                    a += cost[1][index]*D[index][j]
                    a += cost[2][index]*D[index][k]
                
                answer = min(a,answer)

    print(answer)
    return


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 collections
INF = 10**10
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)]
lc= [[],[],[]]
for i in range(N):
    for j in range(N):
        lc[(i+j) % 3].append(c[i][j])
clc = [collections.Counter(lc[i]) for i in range(3)]

def iwakan(clist,color):
    global C
    ret = 0
    for i in range(C):
        ret += clist[i+1] * d[i][color]
    return ret

res = 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
            res = min(res,iwakan(clc[0],i)+iwakan(clc[1],j)+iwakan(clc[2],k))

print(res)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[]
for i in range(c):
  d.append(list(map(int,input().split())))
col=[]
for i in range(n):
  col.append(list(map(int,input().split())))
lc1=[]
lc2=[]
lc3=[]
for i in range(c):
  ccount1=0
  ccount2=0
  ccount3=0
  for j in range(n):
    for k in range(n):
      if (j+k)%3==0:
        ccount1+=d[col[j][k]-1][i]
      elif (j+k)%3==1:
        ccount2+=d[col[j][k]-1][i]
      else:
        ccount3+=d[col[j][k]-1][i]
  lc1.append(ccount1)
  lc2.append(ccount2)
  lc3.append(ccount3)
min=10**10
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i==j or j==k or i==k:
        pass
      else:
        if min>lc1[i]+lc2[j]+lc3[k]:
          min=lc1[i]+lc2[j]+lc3[k]
print(min)