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 collections
N , C = map(int, input().split())
ds =[list(map(int, input().split())) for i in range(C)]
cs =[list(map(int, input().split())) for i in range(N)]
c0 = collections.defaultdict(int)
c1 = collections.defaultdict(int)
c2 = collections.defaultdict(int)
for i in range(N):
    for j in range(N):
        if (i+j) % 3 == 0:
            c0[cs[i][j]] += 1
        elif (i+j) % 3 == 1:
            c1[cs[i][j]] += 1
        else:
            c2[cs[i][j]] += 1
            
d = 10**9
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
            d0 = 0
            for l in c0:
                d0 += c0[l] * ds[l-1][i]
            for l in c1:
                d0 += c1[l] * ds[l-1][j]
            for l in c2:
                d0 += c2[l] * ds[l-1][k]
            if d > d0:
                d = d0
            
print(d)

Submission status: Accepted

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

D = []
C = []
CELL0 = [-1]
CELL1 = [-1]
CELL2 = [-1]




for i in range(M):
    line = list(map(int,input().split()))
    D.append(line)

for i in range(N):
    line = list(map(int,input().split()))
    C.append(line)

for k in range(1,M+1):
    cl0 = 0
    cl1 = 0
    cl2 = 0
    for i in range(N):
        for j in range(N):
            cell = C[i][j]
            if (i+j)%3 == 0:
                cl0 += D[cell-1][k-1]
            if (i+j)%3 == 1:
                cl1 += D[cell-1][k-1]
            if (i+j)%3 == 2:
                cl2 += D[cell-1][k-1]
    CELL0.append(cl0)
    CELL1.append(cl1)
    CELL2.append(cl2)

ans = 2**64

for cell0 in range(1,M+1):
    for cell1 in range(1,M+1):
        if cell0==cell1:
            continue
        for cell2 in range(1,M+1):
            if cell0==cell2 or cell1==cell2:
                continue
            temp = CELL0[cell0] + CELL1[cell1] + CELL2[cell2]
            ans = min(ans, temp)

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(lambda x:int(x)-1,input().split())) for _ in range(N)]

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

ans = 500*500*1000
for c0 in range(C):
    for c1 in range(C):
        if c1 == c0:
            continue
        for c2 in range(C):
            if c2 in (c0,c1):
                continue
            score = 0
            for a in range(C):
                score += n[0][a] * D[a][c0] + n[1][a] * D[a][c1] + n[2][a] * D[a][c2]
            ans = min(ans,score)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N,C=map(int, input().split())
cost=[[int(st) for st in input().split()] for _ in range(C)]
count={0: {}, 1: {}, 2: {}}
for y in range(N):
    for x, v in enumerate(map(int, input().split())):
        rest = (x+y) % 3
        count[rest][v] = 1 + count[rest].get(v, 0)
mincost = 9223372036854775807
for cc in product(*[range(1, C+1)]*3):
    if cc[0] != cc[1] and cc[0] != cc[2] and cc[1] != cc[2]:
        sumcost = 0
        for i in range(3):
            for cl, cnt in count[i].items():
                sumcost += cnt*cost[cl-1][cc[i]-1]
        mincost = min(sumcost, mincost)
print(mincost)

Submission status: Accepted

Solution code:
N,C=map(int, input().split())
cost=[[int(st) for st in input().split()] for _ in range(C)]
count={0: {}, 1: {}, 2: {}}
for y in range(N):
    for x, v in enumerate(map(int, input().split())):
        rest = (x+y) % 3
        if not v in count[rest]:
            count[rest][v] = 1
        else:
            count[rest][v] += 1
mincost = 9223372036854775807
for c1 in range(1, C+1):
    for c2 in range(1, C+1):
        if c1 != c2:
            for c3 in range(1, C+1):
                if c1 != c3 and c2 != c3:
                    sumcost = 0
                    for cl, cnt in count[0].items():
                        sumcost += cnt*cost[cl-1][c1-1]
                    for cl, cnt in count[1].items():
                        sumcost += cnt*cost[cl-1][c2-1]
                    for cl, cnt in count[2].items():
                        sumcost += cnt*cost[cl-1][c3-1]
                    mincost = min(sumcost, mincost)

print(mincost)

Submission status: Accepted

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

inf = float('inf')

def solve(N: int, C: int, D: "List[List[int]]", c: "List[List[int]]"):
    num_count = [[0] * C for i in range(3)]
    for i in range(N):
        for j in range(N):
            num_count[(i+j)%3][c[i][j]] += 1
    
    diff_sum = [[0] * C for i in range(3)]
    for i in range(C):
        for j in range(C):
            for n in range(3):
                diff_sum[n][j] += D[i][j] * num_count[n][i]

    res = inf
    for i, j, k in itertools.permutations(range(C), 3):
        s = diff_sum[0][i] + diff_sum[1][j] + diff_sum[2][k]
        if s < res:
            res = s
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = [ [ int(next(tokens)) for _ in range(C) ] for _ in range(C) ]  # type: "List[List[int]]"
    c = [ [ int(next(tokens))-1 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 itertools
import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, C = map(int, input().split())
COSTS = []
for _ in range(C):
    COSTS.append(list(map(int, input().split())))
# (C, C)
COSTS = np.array(COSTS)
COLORS = []
for _ in range(N):
    COLORS.append(list(map(int, input().split())))
# (N, N)
COLORS = np.array(COLORS) - 1

# cs[x, y]: x == (i + j) % 3 で、色が y であるマスの数
cs = np.zeros((3, C))
for i in range(N):
    for j in range(N):
        cs[(i + j) % 3, COLORS[i, j]] += 1

ans = INF
# (i + j) % 3 == N のマスを cN にする場合のコストを全通り計算する
for c0, c1, c2 in itertools.permutations(range(C), r=3):
    ans = min(
        ans,
        np.dot(COSTS[:, c0], cs[0]) +
        np.dot(COSTS[:, c1], cs[1]) +
        np.dot(COSTS[:, c2], cs[2]))
print(int(ans))

Submission status: Accepted

Solution code:
from itertools import product


def main():
    """
    1 <= N <= 500
    3 <= C <= 30
    (i!=j): 1 <= D(i,j) <= 1000
    (i==j): 0  = D(i,j)
    1 <= c(i,j) <= C
    """
    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)
    ]
    ans = f(N, C, c, D)
    ans1 = fast_f(N, C, c, D)
    assert ans == ans1
    if N <= 30:
        ans2 = TLE(N, C, c, D)
        assert ans == ans2

    print(ans)


def WA(N, C, c, D):
    for i in range(N):
        for j in range(N):
            for x in range(N):
                for y in range(N):
                    same_type = (i + j) % 3 == (x + y) % 3
                    c1 = c[i][j]
                    same_color = c1 == c[x][y]
                    if same_type != same_color:
                        D[c1-1]

    return


def TLE(N, C, c, D):
    """
    3色に割り当てるので C^3
    """
    ans = float("inf")
    for i, j, k in product(range(C), repeat=3):
        if i == j or i == k or j == k:
            continue

        tmp = 0
        for x, y in product(range(N), repeat=2):
            rem = (x + y) % 3
            bef = c[x][y] - 1
            aft = [i, j, k][rem]
            tmp += D[bef][aft]

        ans = min(ans, tmp)

    return ans


def f(N, C, c, D):
    """
    """
    t = [[0] * C for _ in range(3)]
    ans = float("inf")
    for i in range(N):
        for j in range(N):
            # 余りのパターンごとに色の数を集計して圧縮
            rem = (i + j) % 3
            color = c[i][j]
            t[rem][color - 1] += 1

    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
                # 余りのパターン[0,1,2]について、変更後の色の組合せを全列挙[i,j,k]
                # パターンが違うなら、色も異なるので同色にならないように考慮

                tmp = 0
                for bef in range(C):
                    for aft, rem in zip((i, j, k), range(3)):
                        # 違和感 × 対象個数
                        tmp += D[bef][aft] * t[rem][bef]

                ans = min(ans, tmp)

    return ans


def fast_f(N, C, c, D):
    t = [[0] * C for _ in range(3)]
    ans = float("inf")
    for i, j in product(range(N), repeat=2):
        for aft in range(C):
            rem = (i + j) % 3
            color = c[i][j]
            # 個数だけでなく、違和感も前処理に含める
            t[rem][aft] += D[color - 1][aft]

    for i, j, k in product(range(C), repeat=3):
        if i == j or i == k or j == k:
            continue

        tmp = 0
        for aft, rem in zip((i, j, k), range(3)):
            tmp += t[rem][aft]

        ans = min(ans, tmp)

    return ans


if __name__ == '__main__':
    main()

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)]
c=[[] for i in range(3)]
for i in range(N):
    for j in range(N):
        k=((i+1)+(j+1))%3
        c[k].append(c_[i][j])
d=[[0]*C for i in range(3)]
for i in range(C):
    for j in range(3):
        for k in range(len(c[j])):
            d[j][i]+=D[c[j][k]-1][i]
ans=10**17
for i in range(C):
    for j in range(C):
        for k in range(C):
            if (i-j)*(j-k)*(k-i)==0:
                continue
            ans=min(ans,d[0][i]+d[1][j]+d[2][k])
print(ans)

Submission status: Accepted

Solution code:
def main():
    """
    1 <= N <= 500
    3 <= C <= 30
    (i!=j): 1 <= D(i,j) <= 1000
    (i==j): 0  = D(i,j)
    1 <= c(i,j) <= C
    """
    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)
    ]
    ans = f(N, C, c, D)
    print(ans)


def TLE(N, C, c, D):
    for i in range(N):
        for j in range(N):
            for x in range(N):
                for y in range(N):
                    same_type = (i + j) % 3 == (x + y) % 3
                    c1 = c[i][j]
                    same_color = c1 == c[x][y]
                    if same_type != same_color:
                        D[c1-1]

    return


def f(N, C, c, D):
    """
    """
    t = [[0] * C for _ in range(3)]
    ans = float("inf")
    for i in range(N):
        for j in range(N):
            # 余りのパターンごとに色情報の集計
            rem = (i + j) % 3
            color = c[i][j]
            t[rem][color - 1] += 1

    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

                tmp = 0
                for bef in range(C):
                    for aft, rem in zip((i, j, k), range(3)):
                        tmp += D[bef][aft] * t[rem][bef]

                ans = min(ans, tmp)

    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

d = {}
d[0] = {}
d[1] = {}
d[2] = {}
for i in range(C):
    d[0][i] = 0
    d[1][i] = 0
    d[2][i] = 0

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



import itertools
ans = 10**50
l = []
for i in range(C):
    l.append(i)

for li in itertools.permutations(l,3):
    ans = min(ans , d[0][li[0]] + d[1][li[1]] + d[2][li[2]])
print(ans)

Submission status: Accepted

Solution code:
import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

n, c = readIntN()
ds = [readIntN() for _ in range(c)]
cs = [readIntN() for _ in range(n)]

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

ret = float('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
            cur = 0
            for l in range(c):
                cur += ds[l][i] * acc[0][l]
                cur += ds[l][j] * acc[1][l]
                cur += ds[l][k] * acc[2][l]
            ret = min(ret, cur)

print(ret)

Submission status: Accepted

Solution code:
import itertools as it

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

d = []
for i in range(m):
    l = list(map(int,input().split()))
    d.append(l)

cs = [[] for i in range(3)]
for i in range(1,n+1):
    row = list(map(int,input().split()))
    for j, c in enumerate(row):
        cs[(i + (j+1)) % 3].append(c)

#print(cs)
ds = [[] for i in range(3)]
for i in range(1,m+1):
    for j in range(3):
        t = 0
        for e in cs[j]:
            t += d[e-1][i-1]
        ds[j].append(t)

#print(ds)
ans = -1
for (x,y,z) in list(it.permutations(range(m),3)):
    cand = ds[0][x] + ds[1][y] + ds[2][z]
    if ans == -1:
        ans = cand
    else:
        ans = min(ans,cand)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,c = li()
d = [list(li()) for _ in range(c)]
initial = [list(li_()) for _ in range(n)] 

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

for i,initi in enumerate(initial):
    for j, initij in enumerate(initi):
        mod_col[(i+j) % 3][initij] += 1
        
ans = float('inf')
colors = [-1]*3
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
            
            colors = [c0, c1, c2]
            
            tmp = 0
            for modnum in range(3):
                tmp += sum([d[color][colors[modnum]] * mod_col[modnum][color] for color in range(c)])
                
            ans = min(ans, tmp)


print(ans)

Submission status: Accepted

Solution code:
import collections
n, c = (int(i) for i in input().split())
d = [[int(i) for i in input().split()] for i in range(c)]
t = [[int(i)-1 for i in input().split()] for i in range(n)]

l = [[],[],[]]
for i in range(n):
    for j in range(n):
        l[(i+j)%3].append(t[j][i])

l = list(map(lambda x: collections.Counter(x), l))

min_cost = n*n*10**5
for i in range(c):
    for j in range(c):
        if j == i:continue
        for k in range(c):
            if k==j or k==i:continue
            cost = 0
            for idx, done in enumerate([i,j,k]):
                for pre, cnt in l[idx].items():
                    cost += d[pre][done] * cnt
            min_cost = min(min_cost, cost)
            
print(min_cost)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
import numpy as np
from collections import Counter
from itertools import permutations


def solve(N: int, C: int, D: "List[List[int]]", c: "List[List[int]]"):
    D = np.array(D)
    onedim = [[], [], []]
    for i in range(N):          # O(N^2)
        for j in range(N):
            onedim[(i+j) % 3].append(c[i][j])
    # print(onedim)
    counters = [Counter(onedim[i]) for i in range(3)]  # O(3*N*N)
    arr = np.empty((C, C))
    for i in range(3):          # O(C*C)
        for j in range(C):
            arr[i][j] = counters[i][j+1]
    # print("arr", arr)
    # print("D", D)
    hint = arr.dot(D)         # O(C*C*3)
    # print("arr@D\n", hint)
    print(int(min([hint[0][a] + hint[1][b]+hint[2][c]
                   for a, b, c in permutations(range(C), 3)])))
    # O(C*(C-1)*(C-2))
    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:
from itertools import permutations, product

N,C = list(map(int, input().split()))
D = [[0]*(C+1)] + [[0] + list(map(int, input().split())) for _ in range(C)] #D[i][j]
c = [[0]*(N+1)] + [[0] + list(map(int, input().split())) for _ in range(N)] #c[i][j]

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

for i,j in product(range(1,N+1), range(1,N+1)):
  mod3[(i+j)%3][c[i][j]] +=1

answer = 1000*500*500
for colors in permutations(range(1,C+1), 3):
  temp = sum([sum([D[i][colors[m]]*n for i,n in enumerate(mod3[m])]) for m in range(3)])
  answer = min(answer, temp)

print(answer)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

group0 = []
group1 = []
group2 = []
for i in range(N):
	for j in range(N):
		if (i+j)%3 == 0:
			group0.append(c[i][j]-1)
		elif (i+j)%3 == 1:
			group1.append(c[i][j]-1)
		elif (i+j)%3 == 2:
			group2.append(c[i][j]-1)
# print(group0)
# print(group1)
# print(group2)

color_0 = []
inv_0 = {}
for i in range(C):
	tmp = 0
	for item0 in group0:
		tmp += D[item0][i]
	color_0.append((tmp, i))
	inv_0[i] = tmp
color_0 = sorted(color_0)[0:3]
color_0_lis = [x[1] for x in color_0]

color_1 = []
inv_1 = {}
for i in range(C):
	tmp = 0
	for item1 in group1:
		tmp += D[item1][i]
	color_1.append((tmp, i))
	inv_1[i] = tmp
color_1 = sorted(color_1)[0:3]
color_1_lis = [x[1] for x in color_1]

color_2 = []
inv_2 = {}
for i in range(C):
	tmp = 0
	for item2 in group2:
		tmp += D[item2][i]
	color_2.append((tmp, i))
	inv_2[i] = tmp
color_2 = sorted(color_2)[0:3]
color_2_lis = [x[1] for x in color_2]
# print(color_0)
# print(color_0_lis)
# print(color_1)
# print(color_1_lis)
# print(color_2)
# print(color_2_lis)
ans = INF
for i in color_0_lis:
	for j in color_1_lis:
		for k in color_2_lis:
			tmp = 0
			if i == j or j == k or k == i:
				continue
			else:
				tmp += inv_0[i]
				tmp += inv_1[j]
				tmp += inv_2[k]
				ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

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

for i in range(N):
    c = input().split()
    for j in range(N):
        color[(i+j)%3][int(c[j])-1] += 1

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


for i in range(3):
    for j in range(C):
        for c in range(C):
            sumcolor[i][j] += color[i][c] * data[c][j]

answer = 10 ** 18
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and i != k and j != k:
                answer = min(answer, sumcolor[0][i]+sumcolor[1][j]+sumcolor[2][k])


print(answer)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
 
D=[list(map(int,input().split())) for i in range(C)]
grid=[list(map(int,input().split())) for i in range(N)]
 
a=[[0]*C for i in range(3)]
 
 
for i in range(N):
    for j in range(N):
        a[(i+j)%3][grid[i][j]-1]+=1
 
b=[[0]*C for i in range(3)]
for i in range(3):
    for j in range(C):
        b[i][j]=[ sum([ D[k][j] * a[i][k] for k in range(C)]), j]
 
b=[ sorted(b[i]) for i in range(3)]
 
ans=1000000000
for i in range(3):
    for j in range(3):
        for k in range(3):
            if b[0][i][1]!=b[1][j][1] and b[1][j][1]!=b[2][k][1] and b[2][k][1]!=b[0][i][1]:
                ans=min(ans,b[0][i][0]+b[1][j][0]+b[2][k][0])
 
print(ans)

Submission status: Accepted

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

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

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


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

b=[[0]*C for i in range(3)]
for i in range(3):
    for j in range(C):
        b[i][j]=sum([ D[k][j] * a[i][k] for k in range(C)])

b=[ sorted([ [b[i][j],j] for j in range(C)]) for i in range(3)]

ans=1000000000
for i in range(3):
    for j in range(3):
        for k in range(3):
            if b[0][i][1]!=b[1][j][1] and b[1][j][1]!=b[2][k][1] and b[2][k][1]!=b[0][i][1]:
                ans=min(ans,b[0][i][0]+b[1][j][0]+b[2][k][0])

print(ans)

Submission status: Accepted

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

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

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


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

b=[[0]*C for i in range(3)]
for i in range(3):
    for j in range(C):
        b[i][j]=[ sum([ D[k][j] * a[i][k] for k in range(C)]), j]

b=[ sorted(b[i]) for i in range(3)]

ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if b[0][i][1]!=b[1][j][1] and b[1][j][1]!=b[2][k][1] and b[2][k][1]!=b[0][i][1]:
                ans=min(ans,b[0][i][0]+b[1][j][0]+b[2][k][0])

print(ans)

Submission status: Accepted

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

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

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


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

b=[[0]*C for i in range(3)]
for i in range(3):
    for j in range(C):
        b[i][j]=sum([ D[k][j] * a[i][k] for k in range(C)])

b=[ sorted([ [b[i][j],j] for j in range(C)]) for i in range(3)]

ans=10**15
for i in range(3):
    for j in range(3):
        for k in range(3):
            if b[0][i][1]!=b[1][j][1] and b[1][j][1]!=b[2][k][1] and b[2][k][1]!=b[0][i][1]:
                ans=min(ans,b[0][i][0]+b[1][j][0]+b[2][k][0])

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, C = [int(n) for n in input().split()]
    D = []
    for i in range(C):
        D.append([int(n) for n in input().split()])
    grid = []
    for i in range(N):
        grid.append([int(n) for n in input().split()])
    # マスの種類ごとに出てくる色と数を記録
    dic = [{}, {}, {}]
    for h, row in enumerate(grid):
        for w, col in enumerate(row):
            i = ((h+1)+(w+1))%3
            c = col - 1
            if not (c in dic[i].keys()):
                dic[i][c] = 0
            dic[i][c] += 1

    result = 1e18
    for to_zero in range(C):
        for to_one in range(C):
            for to_two in range(C):
                if to_zero == to_one or to_one == to_two or to_two == to_zero:
                    continue
                to_li = [to_zero, to_one, to_two]
                cost = 0
                for i, to in enumerate(to_li):
                    for fr, num in dic[i].items():
                        cost += D[fr][to] * num
                result = min(result, cost)
    print(result)
                
     

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N,C=map(int,input().split())
L=[[0 for i in range(C)] for j in range(3)]
D=[]
for i in range(C):
  D.append([int(x) for x in input().split()])
for i in range(N):
  s=[int(x)-1 for x in input().split()]
  for j in range(N):
    L[(i+j)%3][s[j]]+=1
ans=float("inf")
for per in itertools.permutations(range(C),3):
  kans=sum(sum(D[x][per[i]]*L[i][x] for x in range(C))for i in range(3))
  ans=min(ans,kans)
print(ans)

Submission status: Accepted

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

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

d1 = {}
d2 = {}
d3 = {}

for i, clist in enumerate(cmap):
  for j, _c in enumerate(clist):
    if (i + j + 2) % 3 == 2:
      if _c-1 in d1:
        d1[_c-1] += 1
      else:
        d1[_c-1] = 1
    elif (i + j + 2) % 3 == 0:
      if _c-1 in d2:
        d2[_c-1] += 1
      else:
        d2[_c-1] = 1
    else:
      if _c-1 in d3:
        d3[_c-1] += 1
      else:
        d3[_c-1] = 1

minc = None
for c1 in range(c):
  for c2 in range(c):
    for c3 in range(c):
      tmp = 0
      if c1 == c2 or c2 == c3 or c3 == c1:
        continue
      for _c, cn in d1.items():
        tmp += dmap[_c][c1] * cn
      for _c, cn in d2.items():
        tmp += dmap[_c][c2] * cn
      for _c, cn in d3.items():
        tmp += dmap[_c][c3] * cn
      if minc is None:
        minc = tmp
      elif minc > tmp:
        minc = tmp

print(minc)

Submission status: Accepted

Solution code:
n, c = [int(item) for item in input().split()]
ds = [[int(item) for item in input().split()] for _ in range(c)]
cs = [[int(item) for item in input().split()] for _ in range(n)]

counter = [[0] * (c+1) for _ in range(3)]
for i in range(n):
  for j in range(n):
    counter[(i+j) % 3][cs[i][j]] += 1
    
costs = [[0] * (c+1) for _ in range(3)]
for i in range(1, c+1):
  for j in range(3):
    for k, count in enumerate(counter[j]):
      if k == 0:
        continue
      costs[j][i] += ds[k-1][i-1] * count

ans = 500*500*1000
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i == j or j == k or k == i:
        continue
      sol = costs[0][i+1] + costs[1][j+1] + costs[2][k+1]
      ans = min(ans, sol)
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,c=map(int,input().split())
x=[list(map(int,input().split()))for i in range(c)]
e=[[0]*c for i in range(3)]
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(n):
        e[(i+j+2)%3][a[j]-1]+=1
p=float("inf")
for i in range(c):
    for j in range(c):
            if i!=j:
                for h in range(c):
                    if i!=h and j!=h:
                        p=min(p,sum([x[s][i]*d for s,d in enumerate(e[0])]+[x[s][j]*d for s,d in enumerate(e[1])]+[x[s][h]*d for s,d in enumerate(e[2])]))
print(p)

Submission status: Accepted

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

L = [[0] * C for i in range(3)]
for i in range(N):
    X = [int(i) for i in input().split()]
    for j in range(N):
        L[(i + j) % 3][X[j] - 1] += 1
        
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:
                tmp = 0
                for x in range(C):
                    tmp += L[0][x] * D[x][i] + L[1][x] * D[x][j] + L[2][x] * D[x][k]
                ans = min(ans, tmp)
                    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations
N,C = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(C)]
color = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

# 3 groups
mod3 = {0:[], 1:[], 2:[]}
for i in range(N):
    for j in range(N):
        m = (i+j)%3
        mod3[m].append(color[i][j])

cnts = [Counter(mod3[i]) for i in range(3)]
cost_mod = [[-1]*C for _ in range(3)]
for i in range(3):
    for to_ in range(C):
        cond = 0
        for from_ in cnts[i].keys():
            cond += cnts[i][from_]*cost[from_][to_]
        cost_mod[i][to_] = cond

ans = float('inf')
for p in permutations(range(C), 3):
    cond = 0
    for i in range(3):
        cond += cost_mod[i][p[i]]
    ans = min(ans, cond)
    #print(cond, p)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations
N,C = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(C)]
color = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

# 3 groups
mod3 = {0:[], 1:[], 2:[]}
for i in range(N):
    for j in range(N):
        m = (i+j)%3
        mod3[m].append(color[i][j])

cnts = [Counter(mod3[i]) for i in range(3)]

ans = float('inf')
for p in permutations(range(C), 3):
    cond = 0
    for i in range(3):
        for col in cnts[i].keys():
            cond += cnts[i][col]*cost[col][p[i]]
    ans = min(ans, cond)
    #print(cond, p)
print(ans)