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 sys
# sys.setrecursionlimit(100000)
from collections import Counter


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, c = input_int_list()
    grid = []
    discomfort = []

    for _ in range(c):
        discomfort.append(input_int_list())

    for _ in range(n):
        grid.append(input_int_list())

    c0 = []
    c1 = []
    c2 = []

    # 色を揃えるマスを1次配列に振り分け
    for i in range(n):
        for j in range(n):
            if (i + j + 2) % 3 == 0:
                c0.append(grid[i][j])
            elif (i + j + 2) % 3 == 1:
                c1.append(grid[i][j])
            else:
                c2.append(grid[i][j])

    # それぞれを集計
    c0 = Counter(c0)
    c1 = Counter(c1)
    c2 = Counter(c2)

    ans = float("inf")

    # 塗り分けを全パターン試す
    for x in range(1, c + 1):
        for y in range(1, c + 1):
            for z in range(1, c + 1):
                if x == y or y == z or z == x:
                    continue
                tmp = 0
                for k, v in c0.items():
                    if k == x:
                        continue
                    else:
                        tmp += discomfort[k - 1][x - 1] * v

                for k, v in c1.items():
                    if k == y:
                        continue
                    else:
                        tmp += discomfort[k - 1][y - 1] * v

                for k, v in c2.items():
                    if k == z:
                        continue
                    else:
                        tmp += discomfort[k - 1][z - 1] * v

                ans = min(ans, tmp)

    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import permutations
N,Col = map(int,input().split())
D = [[0 for _ in range(Col+1)]]
for _ in range(Col):
    d = list(map(int,input().split()))
    d.insert(0,0)
    D.append(d)
A = [list(map(int,input().split())) for _ in range(N)]
C = {0:{},1:{},2:{}}
for i in range(N):
    for j in range(N):
        c = (i+j)%3
        a = A[i][j]
        if a not in C[c]:
            C[c][a] = 0
        C[c][a] += 1
dmin = 10**10
for x in permutations(range(1,Col+1),3):
    cnt0 = 0
    for c in C[0]:
        cnt0 += C[0][c]*D[c][x[0]]
    cnt1 = 0
    for c in C[1]:
        cnt1 += C[1][c]*D[c][x[1]]
    cnt2 = 0
    for c in C[2]:
        cnt2 += C[2][c]*D[c][x[2]]
    dmin = min(dmin,cnt0+cnt1+cnt2)
print(dmin)

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, l in enumerate(C):
    l = [x-1 for x in l]
    C[i] = l

X = [[0]*c for _ in range(3)]
for i in range(n):
    for j in range(n):
        r = (i+j)%3
        for k in range(c):
            X[r][k] += D[C[i][j]][k]
import itertools
ans = 10**18
for p in itertools.permutations(range(c), 3):
    temp = 0
    for i in range(3):
        temp += X[i][p[i]]
    ans = min(temp, ans)
print(ans)

Submission status: Accepted

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][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][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 = []
        # from j to i
        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[: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: Accepted

Solution code:
# -*- coding: utf-8 -*-
#D - Good Grid
import sys 
from itertools import permutations
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,C = map(int,readline().split())
D = []
for _ in range(C):
    row = list(map(int,readline().split()))
    D.append(row)
data = []
for _ in range(N):
    row = list(map(int,readline().split()))
    data.append(row)

INF = 10**31
ans = INF
X = defaultdict(int)
Y = defaultdict(int)
Z = defaultdict(int)

for i in range(N):
    for j in range(N):
        pre_c = data[i][j]-1
        if (i+j) % 3 == 0:
            X[pre_c] += 1   
        elif (i+j) % 3 == 1:
            Y[pre_c] += 1
        else:
            Z[pre_c] += 1

M = [i for i in range(C)]
for a,b,c in permutations(M,3):
    total = 0
    for k,v in X.items():
        total += D[k][a]*v
    for k,v in Y.items():
        total += D[k][b]*v
    for k,v in Z.items():
        total += D[k][c]*v
    
    ans = min(ans,total)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, C = map(int, input().split())
D = []
for i in range(C):
    K = list(map(int, input().split()))
    D.append(K)
Before = []
for i in range(N):
    K = list(map(int, input().split()))
    Before.append(K)
Num = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        Num[i][j] = (i + j + 2) % 3
Zero = defaultdict(int)
One = defaultdict(int)
Two = defaultdict(int)

for i in range(N):
    for j in range(N):
        if Num[i][j] == 0:
            Zero[Before[i][j] - 1] += 1
        elif Num[i][j] == 1:
            One[Before[i][j] - 1] += 1
        else:
            Two[Before[i][j] - 1] += 1
Cost = [[0]*C for _ in range(3)]
for i in range(C):
    for k, v in Zero.items():
        Cost[0][i] += v * D[k][i]
    for k, v in One.items():
        Cost[1][i] += v * D[k][i]
    for k, v in Two.items():
        Cost[2][i] += v * D[k][i]
ans = float("inf")
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and j != k and k != i:
                ans = min(ans, Cost[0][i] + Cost[1][j] + Cost[2][k])
print(ans)

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)]
lis = [[] for _ in range(3)]
#print(lis)
for i in range(N):
    for j in range(N):
        lis[(i+j+2) % 3].append(c[i][j])
#print(lis)
val = [[] for _ in range(3)]
for i in range(3):#lis[i]
    for j in range(C):#d[]
        cnt = 0
        for k in lis[i]:
            #print(k)
            cnt += D[k-1][j]
        val[i].append(cnt)
#print(lis)
#print(val)
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,val[0][i]+val[1][j]+val[2][k])
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())))
c0 = {}
c1 = {}
c2 = {}
for i in range(0, n * 2 - 1, 3):
    for j in range(max(0, i - n + 1), min(n, i + 1)):
        c0.setdefault(c[j][i - j], 0)
        c0[c[j][i - j]] += 1
for i in range(1, n * 2 - 1, 3):
    for j in range(max(0, i - n + 1), min(n, i + 1)):
        c1.setdefault(c[j][i - j], 0)
        c1[c[j][i - j]] += 1
for i in range(2, n * 2 - 1, 3):
    for j in range(max(0, i - n + 1), min(n, i + 1)):
        c2.setdefault(c[j][i - j], 0)
        c2[c[j][i - j]] += 1
D = []
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
            for p, q in c0.items():
                temp += d[p - 1][i] * q
            for p, q in c1.items():
                temp += d[p - 1][j] * q
            for p, q in c2.items():
                temp += d[p - 1][k] * q
            D.append(temp)
print(min(D))

Submission status: Accepted

Solution code:
# 色の塗り方は全部で何通りか。O(C^3)で、C^3 = 27000通り。
# 各塗り方に対していちいち計算していると最大25000マスで、これだと間に合わない。
# 3つに別れた各部分を各色に変えるコスト合計を前計算しておけば良い。O(C^3 + N^2 C)。
# 一ひねりした全探索。

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

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

for row in range(n):
    for col in range(n):
        before = init_color[row][col] - 1
        for after in range(c):
            idx = (row + col) % 3
            cost[idx][after] += change_cost[before][after]

ans = 1000 * 500 * 500 * 10
for ci in range(c):
    for cj in range(c):
        for ck in range(c):
            if (ci != cj != ck != ci):
                ans = min(ans, cost[0][ci] + cost[1][cj] + cost[2][ck])

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations, product
INF = float("inf")
N,C=map(int, input().split())
D=[[INF]*(C+1) for _ in range(C+1)]
c = [[-1]*(N+1) for _ in range(N+1)]
for i in range(1, C+1):
    tmp=list(map(int, input().split()))
    for j in range(1, C+1):
        D[i][j] = tmp[j-1]
for i in range(1, N+1):
    tmp=list(map(int, input().split()))
    for j in range(1, N+1):
        c[i][j] = tmp[j-1]
res0 = []
res1 = []
res2 = []
for i in range(1, N+1):
    for j in range(1, N+1):
        if (i+j)%3==0:
            res0.append((i,j))
        elif (i+j)%3==1:
            res1.append((i,j))
        else:
            res2.append((i,j))
ans = INF
dc0 = []
dc1 = []
dc2 = []
for nx in range(1,C+1):
    d0 = 0
    d1 = 0
    d2 = 0
    for i,j in res0:
        d0 += D[c[i][j]][nx]
    for i,j in res1:
        d1 += D[c[i][j]][nx]
    for i,j in res2:
        d2 += D[c[i][j]][nx]
    dc0.append((d0, nx))
    dc1.append((d1, nx))
    dc2.append((d2, nx))
dc0.sort()
dc1.sort()
dc2.sort()

for i, j, k in product(range(0, 3), repeat=3):
    c0 = dc0[i][1]
    c1 = dc1[j][1]
    c2 = dc2[k][1]
    if c0 == c1 or c1 == c2 or c2 == c0:
        continue
    disgust = 0
    for i, j in res0:
        disgust += D[c[i][j]][c0]
    for i, j in res1:
        disgust += D[c[i][j]][c1]
    for i, j in res2:
        disgust += D[c[i][j]][c2]
    ans = min(ans, disgust)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,n_color = map(int,input().split())
change_cost = [list(map(int, input().split())) for i in range(n_color)]
color_grid = [list(map(int, input().split())) for i in range(n)]

mod0_colors = [0] * n_color
mod1_colors = [0] * n_color
mod2_colors = [0] * n_color
for y in range(n):
    for x in range(n):
        color = color_grid[y][x]-1
        if (y+x+2) % 3 == 0:
            mod0_colors[color]+= 1
        elif (y+x+2) % 3 == 1:
            mod1_colors[color]+= 1
        else:
            mod2_colors[color]+= 1

mod2color_cost = [[0]*n_color for _ in range(3)]
for mod,mod_colors in enumerate([mod0_colors,mod1_colors,mod2_colors]):
    for color_to in range(n_color):
        total_cost = 0
        for color_from in range(n_color):
            cost_per_node = change_cost[color_from][color_to]
            n_node = mod_colors[color_from]
            total_cost += n_node*cost_per_node
        mod2color_cost[mod][color_to] = total_cost

ans = float('inf')
for pettern in permutations([i for i in range(n_color)],3):
    total_cost = 0
    for from_ in range(3):
        to = pettern[from_]
        total_cost += mod2color_cost[from_][to]
    ans = min(ans, total_cost)
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
# D[i][j] = 色をiからjに変える時の「違和感」 = 「コスト」
D = [list(map(int, input().split())) for _ in range(C)]
# 最初の色
c = [list(map(int, input().split())) for _ in range(N)]

# cnt[i][j] = 初期状態において、(x+y)%3==iで、色がj(0,1,...,C-1)の数
cnt = [[0 for _ in range(C)]for _ in range(3)]
# グリッド全体(N*N)を調べる
for i in range(1, N + 1):
    for j in range(1, N + 1):
        cnt[(i + j) % 3][c[i - 1][j - 1] - 1] += 1
# print(cnt)

ans = 10**18

# (x+y)%3==0,1,2をc0,c1,c2で塗る
for c0 in range(C):
    for c1 in range(C):
        for c2 in range(C):
            # 同じ色があってはならない
            if c0 == c1 or c1 == c2 or c2 == c0:
                continue

            cost = 0
            # (x+y)%3==0 をc0に塗り替える
            for i, n in enumerate(cnt[0]):
                cost += n * D[i][c0]
            # (x+y)%3==1 をc1に塗り替える
            for i, n in enumerate(cnt[1]):
                cost += n * D[i][c1]
            # (x+y)%3==2 をc2に塗り替える
            for i, n in enumerate(cnt[2]):
                cost += n * D[i][c2]

            ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import sys
sys.setrecursionlimit(10**9)


INF=10**18
def solve(N,C,D,colormap,new_colormap):
    ans = INF
    for j in range(len(new_colormap)):
        new_colors = new_colormap[j]
        res = 0
        for mod in range(3):
            for current_color in range(1,C+1):
                if current_color == 0: continue
                new_color = new_colors[mod]
                res += D[current_color-1][new_color-1] * colormap[mod][current_color]

        ans = min(res,ans)

    
    print(ans)

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


    colormap = np.zeros((3,C+1),dtype=int)
    for i in range(1,N+1):
        for j in range(1,N+1):
            k = i+j
            k %= 3
            colormap[k][c[i-1][j-1]] += 1
            

    new_color_comb = list(itertools.permutations(list(range(1,C+1)),3))
    solve(N, C, np.array(D), colormap, np.array(new_color_comb))



def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8,i8[:,:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()

Submission status: Accepted

Solution code:
from itertools import permutations
N, C = map(int, input().split())
D, P = [], [[0]*C for _ in range(3)]
for i in range(C):
    D.append(list(map(int, input().split())))
for i in range(N):
    for j, c in enumerate(map(int, input().split())):
        P[(i+j)%3][c-1] += 1
res = float("inf")
for q in permutations(range(C),3):
    tmp = 0
    for k in range(3):
        c = q[k]
        for i, p in enumerate(P[k]):
            tmp += D[i][c]*p
    res = min(tmp, res)
print(res)

Submission status: Accepted

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

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)]
cnt = defaultdict(lambda: defaultdict(int))

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

ans = 10**18

for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if c1==c2 or c2==c3 or c3==c1:
                continue
            
            cand = 0
            
            for k, v in cnt[0].items():
                cand += v*D[k][c1]
            
            for k, v in cnt[1].items():
                cand += v*D[k][c2]
            
            for k, v in cnt[2].items():
                cand += v*D[k][c3]
            
            ans = min(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n, m = getList()
    g = []
    for i in range(m):
        g.append(getList())
    # print(g)
    ll = [defaultdict(int) for i in range(3)]

    for i in range(n):
        l = getZList()
        for j, nn in enumerate(l):
            ll[(i+j) % 3][nn] += 1
    # print(ll)
    ans = INF
    for i in range(m):
        for j in range(m):
            if i == j:
                continue
            for k in range(m):
                if i == k or j == k:
                    continue
                tmp = 0
                for kk, vv in ll[0].items():
                    tmp += g[kk][i] * vv
                for kk, vv in ll[1].items():
                    tmp += g[kk][j] * vv
                for kk, vv in ll[2].items():
                    tmp += g[kk][k] * vv
                    # print(tmp)
                # print(i, j, k, tmp)
                ans = min(ans, tmp)

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
#Brute Force
n, c = map(int, input().split())
D = []
for i in range(c):
    new_line = list(map(int, input().split()))
    D.append(new_line)

C = []
for i in range(n):
    new_line = list(map(lambda x: int(x) - 1, input().split()))
    C.append(new_line)

color_list = [[], [], []]
for i in range(n):
    for j in range(n):
        mod = ((i + 1) + (j + 1)) % 3
        color = C[i][j]
        color_list[mod].append(color)

def change_color_cost(mod, change_color):
    target = color_list[mod]
    total = 0
    for base_color in target:
        total += D[base_color][change_color]
    return total
#print(change_color_cost(1, 1))

def top3(mod):
    min_costs = [[None, float("inf")]] * 3
    for color in range(c):
        cost = change_color_cost(mod, color)
        min_costs.append([color, cost])
        min_costs.sort(key=lambda x: x[1])
        min_costs = min_costs[:3]
    return min_costs
#print(top3(0))

tops = []
for mod in range(3):
    tops.append(top3(mod))
#print(tops)

min_cost = float("inf")
for color0, cost0 in tops[0]:
    for color1, cost1 in tops[1]:
        for color2, cost2 in tops[2]:
            if color0 != color1 and color1 != color2 and color2 != color0:
                min_cost = min(min_cost, cost0 + cost1 + cost2)
print(min_cost)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

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

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

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

INF = 10**9
ans = INF

for cols in permutations(range(C), 3):
  temp = 0
  for i, Y in enumerate(cols):
    for X, cnt in enumerate(color[i]):
      temp += D[X][Y] * cnt
  ans = min(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, C = MAP()
D = [LIST() for _ in range(C)]
c = [LIST() for _ in range(N)]

c_kind = [[0]*(C+1) for _ in range(3)]

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


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


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

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

print(ans)

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)]
c = [list(map(int, input().split())) for i in range(n)]
l = [[0] * C for i in range(3)]
for i in range(n):
    for j, k in enumerate(c[i]):
        l[(i + j) % 3][k - 1] += 1
ans = float("inf")
for i in permutations(range(C), 3):
    cnt = 0
    for j in range(3):
        for k in range(C):
            cnt += d[k][i[j]] * l[j][k]
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

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

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

d = [defaultdict(int), defaultdict(int), defaultdict(int)]

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

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

for i in range(3):
    dic = d[i]
    for j in range(c):
        for k, v in dic.items():
            cost[i][j-1] += v * D[k-1][j-1]

ans = 1e9

for i, j, k in itertools.permutations(range(c), 3):
    ans = min(cost[0][i] + cost[1][j] + cost[2][k], ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

input = sys.stdin.readline


def main():
    N, C = map(int, input().split())
    D = [None] * C
    for i in range(C):
        D[i] = tuple(map(int, input().split()))
    A = [None] * N
    for i in range(N):
        A[i] = tuple(map(int, input().split()))

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

    cost = [[0] * C for _ in range(3)]
    for r in range(3):
        for Y in range(C):
            tmp = 0
            for X, num in enumerate(R[r]):
                tmp += D[X][Y] * num
            cost[r][Y] = tmp

    ans = float("inf")
    for c0, c1, c2 in permutations(range(C), r=3):
        ans = min(ans, cost[0][c0] + cost[1][c1] + cost[2][c2])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

C0={i:0 for i in range(1,c+1)}
C1={i:0 for i in range(1,c+1)}
C2={i:0 for i in range(1,c+1)}

CH=[-1]
for i in range(c):
    new=[-1]+[int(i) for i in input().split()]
    CH.append(new[:])

for i in range(n):
    D=[int(i) for i in input().split()]
    for q in range(n):
        now=(i+q)%3
        if now==0:
            C0[D[q]]+=1
        elif now==1:
            C1[D[q]]+=1
        else:
            C2[D[q]]+=1



def calc(dic,col):
    res=0
    for ele in dic:
        res+=dic[ele]*CH[ele][col]
    return res

ans=10**10
for i in range(1,c+1):
    for q in range(1,c+1):
        for r in range(1,c+1):
            if i==q or q==r or r==i:
                continue
            sub=0
            sub+=calc(C0,i)
            sub+=calc(C1,q)
            sub+=calc(C2,r)
            ans=min(ans,sub)

print(ans)

Submission status: Accepted

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

from itertools import permutations

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 permutations(list(range(C)), 3):
    # print(iter_)
    tmp = []
    for i, j in enumerate(iter_):
        tmp.append(data[i][j])
    ans = min(ans, sum(tmp))
print(ans)

Submission status: Accepted

Solution code:
LI = lambda: list(map(int, input().split()))

N, C = LI()
D = [LI() for _ in range(C)]
c = [LI() for _ in range(N)]

INF = 10 ** 15


def main():
    w = [[0] * C for i in range(3)]
    for i in range(N):
        for j in range(N):
            x = (i + j) % 3
            for k in range(C):
                w[x][k] += D[c[i][j] - 1][k]
    
    ans = INF
    for i in range(C):
        for j in range(C):
            if i == j:
                continue
            for k in range(C):
                if i == k or j == k:
                    continue
                ans = min(ans, w[0][i] + w[1][j] + w[2][k])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
g0 = [0]*C
g1 = [0]*C
g2 = [0]*C
for i in range(N):
    col = list(map(int,input().split()))
    for j in range(N):
        col[j] -= 1
        if (i+j)%3==0:
            g0[col[j]] += 1
        elif (i+j)%3 ==1:
            g1[col[j]] += 1
        else:
            g2[col[j]] += 1
ans = float('inf')
for i in range(C):
    for j in range(C): 
        for k in range(C):
            if i==j or j==k or i==k:
                continue
            s=0
            for l in range(C):
                s += d[l][i]*g0[l] + d[l][j]*g1[l] + d[l][k]*g2[l]
            ans = min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, C = map(int, readline().split())
    D = [0] * C
    for i in range(C):
        D[i] = list(map(int, readline().split()))
    G = [0] * N
    for i in range(N):
        G[i] = [int(s) - 1 for s in readline().split()]

    counter = [[0] * C for _ in range(3)]
    cost = [[0] * C for _ in range(3)]
    for x in range(N):
        for y in range(N):
            counter[(x + y) % 3][G[x][y]] += 1

    for cur_cost, cur_counter in zip(cost, counter):
        for i in range(C):
            for j in range(C):
                cur_cost[i] += cur_counter[j] * D[j][i]

    ans = INF
    for c1, c2, c3 in permutations(range(C), 3):
        if ans > cost[0][c1] + cost[1][c2] + cost[2][c3]:
            ans = cost[0][c1] + cost[1][c2] + cost[2][c3]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, C = map(int, readline().split())
    D = [0] * C
    for i in range(C):
        D[i] = list(map(int, readline().split()))
    G = [0] * N
    for i in range(N):
        G[i] = [int(s) - 1 for s in readline().split()]

    cost = [[0] * C for _ in range(3)]
    for x in range(N):
        for y in range(N):
            color = G[x][y]
            cost_current = cost[(x + y) % 3]
            for i in range(C):
                cost_current[i] += D[color][i]

    ans = INF
    for c1, c2, c3 in permutations(range(C), 3):
        if ans > cost[0][c1] + cost[1][c2] + cost[2][c3]:
            ans = cost[0][c1] + cost[1][c2] + cost[2][c3]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, c = ns()
    d = [na() for _ in range(c)]
    color = [na() 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][color[i][j] - 1] += 1

    ans = INF
    for cost in itertools.permutations(range(c), 3):
        tmp_ans = 0
        for i in range(3):
            for j in range(c):
                tmp_ans += cnt[i][j] * d[j][cost[i]]
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()