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 math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, C = l_inpl()
    D = [ l_inpl() for _ in range(C) ]
    c = []
    for _ in range(N):
        ci = l_inpl()
        ci = [ i-1 for i in ci ] 
        c.append(ci)

    # t[i][j]: i={0, 1, 2}, jは色
    t = create_grid(3, C)
    for ci in range(C):
        for i in range(N):
            for j in range(N):
                t[(i+j)%3][ci] += D[c[i][j]][ci]

    ans = 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
                tmp = 0
                tmp += t[0][i]
                tmp += t[1][j]
                tmp += t[2][k]
                ans = min(ans, tmp)
    
    print(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)]

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:
import itertools

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

m0 = [0] * C
m1 = [0] * C
m2 = [0] * C
for i, j in itertools.product(range(N), repeat=2):
    if (i + j) % 3 == 0: m0[c[i][j]] += 1
    if (i + j) % 3 == 1: m1[c[i][j]] += 1
    if (i + j) % 3 == 2: m2[c[i][j]] += 1

ans = float('inf')
for x, y, z in itertools.permutations(range(C), 3):
    point = 0
    for i in range(C): point += D[i][x] * m0[i]
    for i in range(C): point += D[i][y] * m1[i]
    for i in range(C): point += D[i][z] * m2[i]
    ans = min(ans, point)

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,C = map(int,input().split(' '))
D = [list(map(int,input().split(' '))) for i in [0]*C]
c = [list(map(int,input().split(' '))) for i in [0]*N]


l = [[],[],[]]
n = 0
for i in range(N):
	for j in range(i+1):
		l[n].append(c[i-j][j])
	n = (n+1) % 3
for i in range(N-1):
	for j in range(N-i-1):
		l[n].append(c[i+j+1][N-j-1])
	n = (n+1) % 3

d1,d2,d3 = [[sum([D[j-1][i] for j in l[n]]) for i in range(C)] for n in range(3)]

ans = 1000*500*500
colors = list(range(C))
for c1,c2,c3 in itertools.permutations(colors,3):
	ans = min(ans,d1[c1] + d2[c2] + d3[c3])
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, permutations, chain

N, C = map(int, input().split())
D = [[0] * (C + 1)]
for _ in range(C):
    a = [0]
    a.extend(list(map(int, input().split())))
    D.append(a)
c = [list(map(int, input().split())) for _ in range(N)]

# color[g][c] := グループgのうち、色cであるグリッドの数
color = [[0 for _ in range(C + 1)] for _ in range(3)]
for row in range(1, len(c) + 1):
    for col in range(1, len(c[row - 1]) + 1):
        g = (row + col) % 3
        color[g][c[row - 1][col - 1]] += 1


def count():
    for x, y, z in combinations(range(C), 3):
        for a, b, c in permutations([x + 1, y + 1, z + 1]):
            yield a, b, c


ans = float('inf')
for c1, c2, c3 in count():
    cost = 0
    for i in range(1, C + 1):
        cost += color[0][i] * D[i][c1]
    for i in range(1, C + 1):
        cost += color[1][i] * D[i][c2]
    for i in range(1, C + 1):
        cost += color[2][i] * D[i][c3]
    ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

for i in range(N):
    C_array = map(int, input().split())
    for j, c in enumerate(C_array):
        grid_array[(i+j) % 3][c-1] += 1

# print(D_array)

cost_array = [[0] * C for _ in range(3)]
for i in range(3):
    for j in range(C):
        cost = 0
        for k in range(C):
            cost += grid_array[i][k] * D_array[k][j]
        cost_array[i][j] = cost

ans = 10 ** 20

for i in range(C):
    for j in range(C):
        if j == i:
            continue
        for k in range(C):
            if k == i or k == j:
                continue
            ans = min(ans, cost_array[0][i] +
                      cost_array[1][j] + cost_array[2][k])
print(ans)

Submission status: Accepted

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

D = []
c = []

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

colorCount = [[0 for _ in range(C + 1)] for _ in range(3)]  # colorCount[index][color]
for i in range(N) :
    for j in range(N) :
        colorCount[(i + j + 2) % 3][c[i][j]] += 1

ans = float('inf')
for firstColor in range(1, C + 1) :
    for secondColor in range(1, C + 1) :
        for thirdColor in range(1, C + 1) :
            if firstColor == secondColor or secondColor == thirdColor or thirdColor == firstColor :
                continue
            cost = 0
            for dist, toColor in enumerate([secondColor, thirdColor, firstColor]) :
                for fromColor in range(1, C + 1) :
                    if toColor == fromColor :
                        continue
                    cost += colorCount[dist][fromColor] * D[fromColor - 1][toColor - 1]
            ans = min(ans, cost)

print(ans)

Submission status: Accepted

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

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

cnt0 = [0]*30
cnt1 = [0]*30
cnt2 = [0]*30

for y in range(1,n+1):
    for x in range(1,n+1):
        if (x+y) % 3 == 0:
            cnt0[g[y-1][x-1]-1] += 1
        elif (x+y) % 3 == 1:
            cnt1[g[y-1][x-1]-1] += 1
        else:
            cnt2[g[y-1][x-1]-1] += 1

l = list(permutations(range(c),3))
ans = float('inf')
for c0,c1,c2 in l:
    preans = 0
    for i in range(c):
        preans += d[i][c0] * cnt0[i]
        preans += d[i][c1] * cnt1[i]
        preans += d[i][c2] * cnt2[i]
    ans = min(ans,preans)
print(ans)

Submission status: Accepted

Solution code:
def min3(x, y, z):
    inf = 10 ** 9
    m1 = min(x)
    m2 = min(y)
    m3 = min(z)
    i1 = x.index(m1)
    i2 = y.index(m2)
    i3 = z.index(m3)
    if abs((i1 - i2) * (i2 - i3) * (i3 - i1)):
        return m1 + m2 + m3
    re1 = re2 = re3 = inf
    if i1 == i2 or i1 == i3:
        x[i1] = inf
        re1 = min3(x, y, z)
        x[i1] = m1
    if i1 == i2 or i2 == i3:
        y[i2] = inf
        re2 = min3(x, y, z)
        y[i2] = m2
    if i3 == i2 or i1 == i3:
        z[i3] = inf
        re3 = min3(x, y, z)
        z[i3] = m3
    return min(re1, re2, re3)

def dot(A, B):
    C = []
    for x in zip(*B):
        s = 0
        for y, z in zip(A, x):
            s += y * z
        C.append(s)
    return C

gs, cn = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(cn)]
c = [list(map(int, input().split())) for _ in range(gs)]
cc = [[0] * cn for _ in range(3)]
for i in range(gs):
    ci = c[i]
    for j in range(gs):
        cc[(i + j) % 3][ci[j] - 1] += 1
ds = []
for i in range(3):
    ds.append(dot(cc[i], d))
print(min3(ds[0], ds[1], ds[2]))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
D = [[]]
for _ in range(C):
    di = [0] + [int(s) for s in input().split()]
    D.append(di)
c = []
for _ in range(N):
    ci = [int(s) for s in input().split()]
    c.append(ci)

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

ans = float("inf")
for c0 in range(1, C + 1):
    for c1 in range(1, C + 1):
        for c2 in range(1, C + 1):
            if c0 == c1 or c1 == c2 or c2 == c0:
                continue
            d = 0
            d += sum(cnt[0][v] * D[v][c0] for v in range(1, C + 1))
            d += sum(cnt[1][v] * D[v][c1] for v in range(1, C + 1))
            d += sum(cnt[2][v] * D[v][c2] for v in range(1, C + 1))
            ans = min(ans, d)
print(ans)

Submission status: Accepted

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

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

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

for i in range(N) :
    line = list(map(int, input().split()))
    color.append(line)
    for j, c in enumerate(line) :
        colorCount[(i + j + 2) % 3][c - 1] += 1

ans = float('inf')

for firstColor in range(C) :
    for secondColor in range(C) :
        for thirdColor in range(C) :
            if firstColor == secondColor or secondColor == thirdColor or thirdColor == firstColor :
                continue
            cost = 0
            for i, newColor in enumerate([firstColor, secondColor, thirdColor]) :
                for oldColor in range(C) :
                    cost += colorCount[i][oldColor] * weight[oldColor][newColor]
            ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
def solve(p, query):
    # the cost of group's all color change to i
    group_a = [0]*(color+1)
    group_b = [0]*(color+1)
    group_c = [0]*(color+1)

    for c_a, c_b, c_c in zip(mod_1, mod_2, mod_0):
        for i in range(1, color+1):
            group_a[i] += d[c_a][i]
            group_b[i] += d[c_b][i]
            group_c[i] += d[c_c][i]

    top_3_group_a = sorted(
        list(zip(list(range(color+1)), group_a[1:])), key=lambda x: x[1])[:3]
    top_3_group_b = sorted(
        list(zip(list(range(color+1)), group_b[1:])), key=lambda x: x[1])[:3]
    top_3_group_c = sorted(
        list(zip(list(range(color+1)), group_c[1:])), key=lambda x: x[1])[:3]
    ans = float('inf')
    for i in top_3_group_a:
        for j in top_3_group_b:
            if i[0] != j[0]:
                for k in top_3_group_c:
                    if i[0] != k[0] and j[0] != k[0]:
                        ans = min(ans, i[1]+j[1]+k[1])
    return ans


if __name__ == '__main__':
    n, color = map(int, input().split())
    c, d = [], []
    d.append([0]*(color+1))

    for _ in range(color):
        d.append([0]+list(map(int, input().split())))

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

    mod_1, mod_2, mod_0 = [], [], []

    for i in range(n):
        for j in range(n):
            if (i+j) % 3 == 1:
                mod_1.append(_c[i][j])
            elif (i+j) % 3 == 2:
                mod_2.append(_c[i][j])
            else:
                mod_0.append(_c[i][j])

    if n % 3 == 1:
        mod_1.append(0)
        mod_2.append(0)
    if n % 3 == 2:
        mod_0.append(0)
        mod_2.append(0)

    print(solve(c, d))

Submission status: Accepted

Solution code:
from collections import defaultdict
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
cnt = [defaultdict(int) for i in range(3)]
for i in range(N):
    s = list(map(int, input().split()))
    for j in range(N):
        t = (i+j+2) % 3
        cnt[t][s[j]-1] += 1
ans = 10**9
for x in range(C):
    for y in range(C):
        for z in range(C):
            if x == y or y == z or z == x: continue
            tmp = 0
            for i, c in enumerate([x, y, z]):
                for key in cnt[i]:
                    tmp += D[key][c] * cnt[i][key]
            ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
D = []
for i in range(0, C):
	D.append(list(map(int, input().split())))
colors = [[], [], []]
for i in range(0, N):
	A = list(map(lambda v: int(v)-1, input().split()))
	for j in range(0, N):
		colors[(i+j)%3].append(A[j])
sums = [[], [], []]
for i in range(0, 3):
	for j in range(0, C):
		sum = 0
		for k in range(0, len(colors[i])):
			sum += D[colors[i][k]][j]
		sums[i].append(sum)
min = 5000000000000000
for i in range(0, C):
	for j in range(0, C):
		if i != j:
			for k in range(0, C):
				if i != k and j != k:
					if sums[0][i] + sums[1][j] + sums[2][k] < min:
						min = sums[0][i] + sums[1][j] + sums[2][k]
print(min)

Submission status: Accepted

Solution code:
N,C = map(int, input().split())
Dij = []
for i in range(C):
    Dij.append(list(map(int, input().split())))
cij = []
for i in range(N):
    cij.append(list(map(int, input().split())))
# 同じ色にしたいグリッドのまとめ
C1 = []
C2 = []
C3 = []
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            C1.append(cij[i][j])
        if (i+j)%3 == 1:
            C2.append(cij[i][j])
        if (i+j)%3 == 2:
            C3.append(cij[i][j])

"""
3色で塗る
"""
cost_c1 = []
cost_c2 = []
cost_c3 = []
for Y in range(C):
    #1
    cost = 0
    for X in C1:
        cost += Dij[X-1][Y]
        # print(X-1,"->",Y,":",Dij[X-1][Y])
    cost_c1.append(cost)
    #2
    cost = 0
    for X in C2:
        cost += Dij[X-1][Y]
        # print(X-1,"->",Y,":",Dij[X-1][Y])
    cost_c2.append(cost)
    #3
    cost = 0
    for X in C3:
        cost += Dij[X-1][Y]
        # print(X-1,"->",Y,":",Dij[X-1][Y])    
    cost_c3.append(cost)

#1->2->3

minA = 0

ans = float("inf")
for i,c1 in enumerate(cost_c1):
    for j,c2 in enumerate(cost_c2):
        for k,c3 in enumerate(cost_c3):
            if i!=j and j!=k and k!=i:
                ans = min(ans,c1+c2+c3) 
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

gg = [defaultdict(int) for _ in range(3)]
for i in range(n):
    g = list(map(int, input().split()))
    for j in range(n):
        gg[(i+j)%3][g[j]-1] += 1

ans = max(max(d)) * n**2
for c0 in range(c):
    for c1 in range(c):
        if c1 == c0:
            continue
        for c2 in range(c):
            if c0 == c2 or c1 == c2:
                continue

            tmp_ans = sum([d[i][c0] * gg[0][i] for i in gg[0]]) \
                    + sum([d[i][c1] * gg[1][i]  for i in gg[1]]) \
                    + sum([d[i][c2] * gg[2][i]  for i in gg[2]])
            # print(c0, c1, c2, tmp_ans)
            ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
MOD = 3
INF = 1000000000


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


def main():
    n, c = [int(e) for e in input().split()]
    dMat = [[int(e) for e in input().split()] for _ in range(c)]
    cMat = [[int(e) for e in input().split()] for _ in range(n)]

    cost = [[0 for _ in range(c)] for _ in range(MOD)]
    for hi in range(n):
        for wi in range(n):
            cMod = ((hi + 1) + (wi + 1)) % MOD
            for ci in range(c):
                cost[cMod][ci] += dMat[cMat[hi][wi] - 1][ci]

    ans = INF
    for perm in itertools.permutations(range(c), MOD):
        costSum = 0
        for di in range(MOD):
            costSum += cost[di][perm[di]]
        ans = min(ans, costSum)
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np
MOD = 3
INF = 1000000000


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


def main():
    n, c = [int(e) for e in input().split()]
    dMat = [[int(e) for e in input().split()] for _ in range(c)]
    cMat = [[int(e) for e in input().split()] for _ in range(n)]

    cost = [[0 for _ in range(c)] for _ in range(MOD)]
    for hi in range(n):
        for wi in range(n):
            cMod = ((hi + 1) + (wi + 1)) % MOD
            for ci in range(c):
                cost[cMod][ci] += dMat[cMat[hi][wi] - 1][ci]

    ans = INF
    for perm in itertools.permutations(range(c), MOD):
        costSum = 0
        for di in range(MOD):
            costSum += cost[di][perm[di]]
        ans = min(ans, costSum)
    print(ans)


main()

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

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

iwakan_all = []
for i in range(3):
    _init_colors = init_colors[i]
    _iwakan = []

    for target in range(C):

        iwakan = 0
        for j in range(len(_init_colors)):
            iwakan += d[_init_colors[j] - 1][target - 1]

        _iwakan.append(iwakan)

    iwakan_all.append(_iwakan)


res = float('inf')
for i in range(C):
    tmp1 = iwakan_all[0][i]
    for j in range(C):
        if j != i:
            tmp2 = iwakan_all[1][j]
            for k in range(C):
                if k != i and k != j:
                    tmp3 = iwakan_all[2][k]
                    res = min(res, tmp1 + tmp2 + tmp3)

print(res)

Submission status: Accepted

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

dic0 = {}
dic1 = {}
dic2 = {}

for i in range(N) :
    for j in range(N) :
        key = C[i][j]-1
        if (i+j) % 3 == 0 :
            if key not in dic0 :
                dic0[key] = 1
            else :
                dic0[key] += 1
        elif (i+j) % 3 == 1 :
            if key not in dic1 :
                dic1[key] = 1
            else :
                dic1[key] += 1
        else :
            if key not in dic2 :
                dic2[key] = 1
            else :
                dic2[key] += 1

ans = float("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
            
            calc = 0
            for a,b in dic0.items() :
                calc += D[a][i]*b
            for a,b in dic1.items() :
                calc += D[a][j]*b
            for a,b in dic2.items() :
                calc += D[a][k]*b
            ans = min(ans,calc)
print(ans)

Submission status: Accepted

Solution code:
def calc_total_D(stats, D, color):
    total = 0
    for i in range(3):
        y = color[i]
        for x in range(len(stats[i])):
            total += stats[i][x] * D[x][y]
    return total


def main():
    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)]

    # color -= 1
    stats = [[0] * C for _ in range(3)]

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

    retval = float("inf")
    for c1 in range(C):
        for c2 in range(C):
            if c1 == c2:
                continue
            for c3 in range(C):
                if c1 == c3 or c2 == c3:
                    continue
                retval = min(retval, calc_total_D(stats, D, [c1, c2, c3]))
    print(retval)


if __name__ == "__main__":
    main()

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

c0=Counter([c[i][j] for i in range(N) for j in range(N) if (i+j)%3==0])
c1=Counter([c[i][j] for i in range(N) for j in range(N) if (i+j)%3==1])
c2=Counter([c[i][j] for i in range(N) for j in range(N) if (i+j)%3==2])

d0,d1,d2=dict(),dict(),dict()
for i in range(C):
	d0[i]=sum([c0[j+1]*D[j][i] for j in range(C)])
	d1[i]=sum([c1[j+1]*D[j][i] for j in range(C)])
	d2[i]=sum([c2[j+1]*D[j][i] for j in range(C)])

min_=10**9
for i in range(C):
	for j in range(C):
		for k in range(C):
			if i!=j and j!=k and k!=i:
				if min_>d0[i]+d1[j]+d2[k]:
					min_=d0[i]+d1[j]+d2[k]
print(min_)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(c)]
board=[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][board[i][j]-1]+=1
ans=10**10
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 l in range(c):
        tmp+=d[l][i]*cnt[0][l]
        tmp+=d[l][j]*cnt[1][l]
        tmp+=d[l][k]*cnt[2][l]
      ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
D=[list(map(int,input().split())) for i in range(C)]
MAP=[list(map(int,input().split())) for i in range(N)]
from collections import defaultdict
cnt=[defaultdict(int) for i in range(3)]
for i in range(N):
    for j in range(N):
        cnt[(i+j)%3][MAP[i][j]-1]+=1
ans=float('inf')
cost=[[0]*C for i in range(3)]
for i in range(3):
    for y in range(C):
        for x in range(C):
            cost[i][y]+=D[x][y]*cnt[i][x]
for x in range(C):
    for y in range(C):
        if x==y:
            continue
        for z in range(C):
            if z==x or z==y:
                continue
            ans=min(ans,cost[0][x]+cost[1][y]+cost[2][z])
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,c = map(int,input().split())
D = []
for i in range(c):
    L = list(map(int,input().split()))
    D.append(L)
G = []
for i in range(n):
    P = list(map(int,input().split()))
    G.append(P)
mod3_0 = [0]*c
mod3_1 = [0]*c
mod3_2 = [0]*c
for i in range(n):
    for j in range(n):
        if (i+j+2)%3 == 0:
            mod3_0[G[i][j]-1] += 1
        elif (i+j+2)%3 == 1:
            mod3_1[G[i][j]-1] += 1
        else:
            mod3_2[G[i][j]-1] += 1
t = []
for i in range(c):
    t.append(i)
T = list(itertools.permutations(t,3))
ans = float('inf')
for i in range(len(T)):
    cur = 0
    for j in range(c):
        cur +=  mod3_0[j]*(D[j][T[i][0]])
    for k in range(c):
        cur +=  mod3_1[k]*(D[k][T[i][1]])
    for l in range(c):
        cur +=  mod3_2[l]*(D[l][T[i][2]])
    if ans >= cur:
        ans = cur
print(ans)

Submission status: Accepted

Solution code:
def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n,C=map(int, input().split())
    d = [0] * C
    for i in range(C):
        d[i] = [int(j) for j in input().split()]
    c = [0] * n
    for i in range(n):
        c[i] = [int(j)-1 for j in input().split()]
    cost = [[0] * C for _ in range(3)]
    for x in range(n):
        for y in range(n):
            for target in range(C):
                cost[(x+y)%3][target] += d[c[x][y]][target]
    ans = 1e9
    for i in range(C):
        for j in range(C):
            for k in range(C):
                if len({i, j, k}) < 3:
                    continue
                ans = min([ans, cost[0][i] + cost[1][j] + cost[2][k]])
    print(ans)

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)]
m0 = []
m1 = []
m2 = []
for i in range(N):
    for j in range(N):
        if (i+j+2)%3 == 0:
            m0.append(c[i][j])
        elif  (i+j+2)%3 == 1:
            m1.append(c[i][j])
        else:
            m2.append(c[i][j])
cost = [[0]*C for i in range(3)]
for m in m0:
    for color in range(C):
        cost[0][color] += D[m-1][color] 
for m in m1:
    for color in range(C):
        cost[1][color] += D[m-1][color] 
for m in m2:
    for color in range(C):
        cost[2][color] += D[m-1][color] 
#print(cost)
res = 10**10
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
            res = min(cost[0][i]+cost[1][j]+cost[2][k],res)
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations as perm
N,C = map(int, input().split())
colors = []
for i in range(C):
    colors.append(list(map(int, input().split())))

grids = {0:{}, 1:{}, 2:{}}
for i in range(1,N+1):
    A =list(map(int, input().split()))
    for j in range(N):
        if A[j] not in grids[(i+j+1)%3]:
            grids[(i+j+1)%3][A[j]] = 1
        else:
            grids[(i+j+1)%3][A[j]] += 1
mn = 10**9
for color in perm([i for i in range(1,C+1)], 3):
    tmp = 0
    for i in range(3):
        for k,v in grids[i].items():
            tmp += colors[k-1][color[i]-1] * v
    mn = min(mn, tmp)
print(mn)

Submission status: Accepted

Solution code:
import sys

from collections import deque
# q = deque(); q.append(x); q.appendleft(x); q.pop() -> x; q.popleft() -> x
from collections import defaultdict
# d = defaultdict(lambda: []); d[key] -> []
import heapq
# hq = []; heapq.heappush(hq, x); heapq.heappop(hq) -> x; heapq.heappushpop(hq, x) -> x
import bisect
# i = bisect.bisect_left([1,2,3,4], 1.5); i = bisect.bisect_right([4,3,2,1], 1.5)

#import numpy as np
#from scipy.misc import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

"""
マスは1つの色を持つ -> c[i][j]
マスは3グループのいずれかに属する -> (i+j)%3
グループは1つの色 gc を持つ、ただし他のグループと同じ色を持てない gc1 != gc2 != gc3
マス違和感 = D[マスの色][グループの色]
グループ違和感 = グループ内のマスの、マス違和感の合計 = DG[グループ色]
全体違和感 = 3グループの、グループ違和感の合計
答え = 全体違和感
"""
def main():
    N, C = i2nn()
    D = ii2nnn(C)
    c = ii2nnn(N)
    iwakanG = [[0] * C for _ in range(3)]  # グループ違和感[グループID][グループ色] = グループID/色ごとのマス違和感の計
    for i in range(N):
        for j in range(N):
            groupID = (i + j) % 3  # グループID
            cM = c[i][j] - 1  # マス色
            for cG in range(C):
                iwakanM = D[cM][cG]   # マス違和感
                iwakanG[groupID][cG] += iwakanM  # グループ違和感にマス違和感を加算
    iwakan = 1e+9
    for gc1 in range(C):
        for gc2 in range(C):
            for gc3 in range(C):
                if gc1 == gc2 or gc2 == gc3 or gc3 == gc1:
                    continue
                n = iwakanG[0][gc1] + iwakanG[1][gc2] + iwakanG[2][gc3]
                if iwakan > n:
                    iwakan = n  # 全体違和感の最小化
    print(iwakan)

main()

Submission status: Accepted

Solution code:
import numpy as np
N,C = map(int,input().split())
D = np.array([list(map(int,input().split())) for _ in range(C)])
c = np.array([list(map(int,input().split())) for _ in range(N)])

strange = np.array([[0]*C for _ in range(3)])
for i in range(N):
    for j in range(N):
        strange[(i+j)%3] += D[c[i][j]-1]

ans = 1000*N**2
for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if c1 != c2 and c2 != c3 and c3 != c1:
                ans = min(ans,strange[0][c1]+strange[1][c2]+strange[2][c3])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
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)]

strange = [defaultdict(lambda:0) for _ in range(3)]
for i in range(N):
    for j in range(N):
        for color in range(C):
            strange[(i+j)%3][color] += D[c[i][j]-1][color]

ans = 1000*N**2
for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if c1 != c2 and c2 != c3 and c3 != c1:
                ans = min(ans,strange[0][c1]+strange[1][c2]+strange[2][c3])
print(ans)