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

N, N1 = tuple([int(x) for x in sys.stdin.readline().split()])
D, C = [], []

for _ in range(N1):
    D.append([int(x) for x in sys.stdin.readline().split()])
for _ in range(N):
    C.append([int(x) for x in sys.stdin.readline().split()])

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

min_cost = 2**64
for c0 in range(N1):
    for c1 in range(N1):
        if c0 == c1:
            continue
        for c2 in range(N1):
            if c0 == c2 or c1 == c2:
                continue
            cost = 0
            for j in range(N1):
                cost += color_count[0][j] * D[j][c0]
                cost += color_count[1][j] * D[j][c1]
                cost += color_count[2][j] * D[j][c2]
            if cost < min_cost:
                min_cost = cost

print(min_cost)

Submission status: Accepted

Solution code:
import collections
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)]
L1 = [c[i-1][j-1] for i in range(1,N+1) for j in range(1,N+1) if (i + j) % 3 == 1]
L2 = [c[i-1][j-1] for i in range(1,N+1) for j in range(1,N+1) if (i + j) % 3 == 2]
L3 = [c[i-1][j-1] for i in range(1,N+1) for j in range(1,N+1) if (i + j) % 3 == 0]
c1 = collections.Counter(L1)
c2 = collections.Counter(L2)
c3 = collections.Counter(L3)
result = 10**9
for i in range(1,C+1):
    for j in range(1,C+1):
        if i == j:
            continue
        for k in range(1,C+1):
            if i == k or j == k:
                continue
            tmp = 0
            for l in range(1,C+1):
                tmp += c1[l] * D[l-1][i-1]
                tmp += c2[l] * D[l-1][j-1]
                tmp += c3[l] * D[l-1][k-1]
            result = tmp if result > tmp else result

print(result)

Submission status: Accepted

Solution code:
n,c = [int(i) for i in input().split()]
effort = []
group1 = []
group2 = []
group3 = []

effort1 = []
effort2 = []
effort3 = []

color1 = [0 for i in range(c)]
color2 = [0 for i in range(c)]
color3 = [0 for i in range(c)]

for i in range(c):
    effort.append(list(map(int,input().split())))

for i in range(n):
    k = 0
    for j in input().split():
        k+=1
        tot = i+1+k
        if tot % 3 == 0:
            group1.append(int(j))
        elif tot % 3 == 1:
            group2.append(int(j))
        elif tot % 3 == 2:
            group3.append(int(j))

for i in group1:
    color1[i-1] +=1
for i in group2:
    color2[i-1] +=1
for i in group3:
    color3[i - 1] += 1


for i in range(c):
    eff = 0
    for k in range(c):
        eff += color1[k] * effort[k][i]
    effort1.append([eff,i])
for i in range(c):
    eff = 0
    for k in range(c):
        eff += color2[k] * effort[k][i]
    effort2.append([eff, i])
for i in range(c):
    eff = 0
    for k in range(c):
        eff += color3[k] * effort[k][i]
    effort3.append([eff, i])

effort1 = sorted(effort1)
effort2 = sorted(effort2)
effort3 = sorted(effort3)
toteff = 10000000000000000000
for i in range(3):
    col1 = effort1[i][1]
    for k in range(3):
        col2 = effort2[k][1]
        for j in range(3):
            col3 = effort3[j][1]
            if col1 != col2 and col2 !=col3 and col1!=col3:
                toteff = min(toteff,effort1[i][0]+effort2[k][0]+effort3[j][0])

print(toteff)

Submission status: Accepted

Solution code:
# 基本は３で割ったあまり毎に変換コストを計算する.
# a[i][j] i種類目がj色に変わる時のコストと計算し、それの合計のminを取る

import numpy as np
N,C = map(int,input().split())
a = np.zeros((3,C))
D = np.array([ list(map(int,input().split())) for i in range(C)])
c = np.array([ list(map(int,input().split())) for i in range(N)])


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

sum_arr = []
for C1 in range(C):
    for C2 in range(C):
        for C3 in range(C):
            if C1 != C2 and C2 != C3 and C3 != C1:
                sum_arr.append(a[0][C1]+a[1][C2]+a[2][C3])

print(int(min(sum_arr)))

Submission status: Accepted

Solution code:
from itertools import permutations

N, C = [int(elem) for elem in input().split(' ')]
D_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(C)]
assert len(D_matrix) == C
assert len(D_matrix[0]) == C
c_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(c_matrix) == N
assert len(c_matrix[0]) == N

# grouping
# O(N^2)
mod_list = [[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        mod_list[(i + j) % 3].append((i, j))

# O(N^2)
mod_color_list = [[0] * C for _ in range(3)]
for k, mod in enumerate(mod_list):
    for i, j in mod:
        mod_color_list[k][c_matrix[i][j] - 1] += 1

# O(C^3 * N^2) -> O(C^4)
min_cost = float('inf')
for colors in permutations(range(C), 3):
    total_cost = 0
    for color, mod_color in zip(colors, mod_color_list):
        total_cost += sum([D_matrix[X][color] * mod_color[X] for X in range(C)])
    min_cost = min(min_cost, total_cost)

print(min_cost)

Submission status: Accepted

Solution code:
import itertools
N,C = map(int,input().split())
D = [input().split() for l in range(C)]
c = [input().split() for l in range(N)]
F = list(range(C))
B = list(itertools.permutations(F, 3))
ans = 0
kotae = float("inf")
moto1 = [0] * C 
moto2 = [0] * C 
moto3 = [0] * C 
for i in range(N):
    for j in range(N):
        if (i+j+2) %3 == 1:
                moto1[int(c[i][j])-1] += 1
        if (i+j+2) %3 == 2:
                moto2[int(c[i][j])-1] += 1
        if (i+j+2) %3 == 0:
                moto3[int(c[i][j])-1] += 1
for e,f,g in B:
    for i in range(C):
        ans += moto1[i] * int(D[i][e])
        ans += moto2[i] * int(D[i][f])
        ans += moto3[i] * int(D[i][g])
    kotae = min(ans,kotae)
    ans = 0
print(kotae)

Submission status: Accepted

Solution code:
N, C = map(int, raw_input().split())
D = [map(int, raw_input().split()) for _ in range(C)]
G = [map(int, raw_input().split()) for _ in range(N)]
GC = []
GC.append([0]*C)
GC.append([0]*C)
GC.append([0]*C)
for y in range(N):
  for x in range(N):
    GC[(y+x)%3][G[y][x]-1] += 1
ans = 1000000000
for a in range(C):
  for b in range(C):
    if a == b:
      continue
    for c in range(C):
      if a == c or b == c:
        continue
      cost = 0
      for i in range(C):
        cost += GC[0][i]*D[i][a]
        cost += GC[1][i]*D[i][b]
        cost += GC[2][i]*D[i][c]
      ans = min(ans, cost)
print ans

Submission status: Accepted

Solution code:

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

mod2 = []
mod0 = []
mod1 = []
colormap = []


for n in range(C):
    row = input()
    col = row.split()
    for m in range(len(col)):
        col[m] = int(col[m])
    colormap.append(col)

for i in range(N):
    row = input()
    col = row.split()
    for j in range(len(col)):
        if (i+j)%3 == 0:
            mod2.append(int(col[j])-1)
        elif (i+j)%3 == 1:
            mod0.append(int(col[j])-1)
        else:
            mod1.append(int(col[j])-1)

colorscore = []
for c in range(C):
    s2 = 0
    s0 = 0
    s1 = 0
    for i in mod2:
        s2 += colormap[i][c]
    for i in mod0:
        s0 += colormap[i][c]
    for i in mod1:
        s1 += colormap[i][c]
    colorscore.append([s2,s0,s1])

score = []
l =  len(colorscore)
for i in range(l):
    tempj = []
    for j in range(l):
        tempk = []
        for k in range(l):
            if  k == j or k == i:
                tempk.append(float("inf"))
            else:tempk.append(colorscore[j][1] + colorscore[k][2])
        tempk = min(tempk)
        if j == i:
            tempj.append(float("inf"))
        else:tempj.append(colorscore[i][0] + tempk)
    tempj = min(tempj)
    score.append(tempj)

print(min(score))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    from collections import defaultdict

    n, c = map(int, input().split())
    dt = [[int(e) for e in input().split()] for _ in range(c)]
    ct = [[int(e) for e in input().split()] for _ in range(n)]

    cd0 = defaultdict(int)
    cd1 = defaultdict(int)
    cd2 = defaultdict(int)
    for i in range(n):
        for j in range(n):
            if (i + 1 + j + 1) % 3 == 0:
                cd0[ct[i][j]] += 1
            if (i + 1 + j + 1) % 3 == 1:
                cd1[ct[i][j]] += 1
            if (i + 1 + j + 1) % 3 == 2:
                cd2[ct[i][j]] += 1

    ans = 500 ** 2 * 1000 * 30
    for c0 in range(1, c + 1):
        base = 0
        for d in cd0:
            if d == c0:
                continue
            base += dt[d - 1][c0 - 1] * cd0[d]
        for c1 in range(1, c + 1):
            if c0 == c1:
                continue
            base2 = 0
            for d in cd1:
                if d == c1:
                    continue
                base2 += dt[d - 1][c1 - 1] * cd1[d]
            base2 += base
            for c2 in range(1, c + 1):
                if c0 == c2 or c1 == c2:
                    continue
                tans = 0
                for d in cd2:
                    if d == c2:
                        continue
                    tans += dt[d - 1][c2 - 1] * cd2[d]
                ans = min(ans, tans + base2)
                
    print(ans)
    
if __name__=="__main__":
    solve()

Submission status: Accepted

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

X0,X1,X2 = [],[],[]
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            X0.append(A[i][j])
        elif (i+j)%3 == 1:
            X1.append(A[i][j])
        else:
            X2.append(A[i][j])

# それぞれの集合を塗り替える場合のコストを計算
Xn = [X0,X1,X2]
cost = [[0 for _ in range(C)] for _ in range(3)]
for i in range(3):
    for c in range(1,C+1):
        Ans = 0
        for x in Xn[i]:
            if x != c:
                Ans += D[x-1][c-1]
        cost[i][c-1] = Ans

Y0 = cost[0]
Y1 = cost[1]
Y2 = cost[2]
Ans = 1000000000000000
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, Y0[i]+Y1[j]+Y2[k])

print(Ans)

Submission status: Accepted

Solution code:
s=input().split()
N=int(s[0])
C=int(s[1])
d=[]
for i in range(C):
    s=input().split()
    temp=[]
    for item in s:
        temp.append(int(item))
    d.append(temp)
if N==1:
    print("0")
else:
    c=[[],[],[]]
    cost=[[],[],[]]
    for j in range(N):
        s=input().split()
        for i in range(len(s)):
            c[(i+j)%3].append(int(s[i])-1)
    for i in range(C):
        s=0
        for col in c[0]:
            s+=d[col][i]
        cost[0].append((s,i))
        s=0
        for col in c[1]:
            s+=d[col][i]
        cost[1].append((s,i))
        s=0
        for col in c[2]:
            s+=d[col][i]
        cost[2].append((s,i))
    res=100000000000
    for i in range(C):
        for j in range(C):
            for k in range(C):
                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]:
                    res=min(res,cost[0][i][0]+cost[1][j][0]+cost[2][k][0])
    print(res)

Submission status: Accepted

Solution code:
import numpy as np
D = []
c = []
d0 = {}
d1 = {}
d2 = {}

N,C = map(int,input().split())
a = np.zeros((3,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 = np.array(D)
c = np.array(c)

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

l = []
for C1 in range(C):
    for C2 in range(C):
        for C3 in range(C):
            if C1 != C2 and C2 != C3 and C3 != C1:
                l.append(a[0][C1]+a[1][C2]+a[2][C3])

print(int(min(l)))

Submission status: Accepted

Solution code:
import collections
n,w = map(int,input().split())
d = []
for i in range(w):
	dtemp = list(map(int,input().split()))
	d.append(dtemp)

a = []
b = []
c = []
for i in range(n):
	temp = list(map(int,input().split()))
	if i%3 == 1:
		for k in range(n):
			if k %3 == 0:
				a.append(temp[k])
			elif k %3 == 1:
				b.append(temp[k])
			else:
				c.append(temp[k])
	elif i%3 == 2:
		for k in range(n):
			if k %3 == 0:
				b.append(temp[k])
			elif k %3 == 1:
				c.append(temp[k])
			else:
				a.append(temp[k])
	else:
		for k in range(n):
			if k %3 == 0:
				c.append(temp[k])
			elif k %3 == 1:
				a.append(temp[k])
			else:
				b.append(temp[k])
ac = collections.Counter(a)
bc = collections.Counter(b)
cc = collections.Counter(c)

ans = []
for i in range(1,w+1): #aについて
	for k in range(1,w+1): #bについて
		for e in range(1,w+1): #cについて
			if i != k and i != e and k != e:
				counter = 0
				for p in ac:
					if p != i:
						counter += ac[p]*d[p-1][i-1]
				for q in bc:
					if q != k and k != i:
						counter += bc[q]*d[q-1][k-1]
				for r in cc:
					if r != e and e != i and e != k:
						counter += cc[r]*d[r-1][e-1]
				ans.append(counter)
print(min(ans))

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
Ds = [list(map(int,input().split())) for x in range(c)]
colors = [list(map(int,input().split())) for x in range(n)]
count0,count1,count2 = [0]*c,[0]*c,[0]*c
for i in range(n):
  for j in range(n):
    if (i+j)%3 == 0:
      count0[colors[i][j]-1] += 1
    elif (i+j)%3 == 1:
      count1[colors[i][j]-1] += 1
    else:
      count2[colors[i][j]-1] += 1
total = pow(10,12)
for a in range(c):
  for b in range(c):
    for d in range(c):
      if a == b or b == d or d == a:
        continue
      tmp = 0
      for x in range(c):
        tmp += count0[x]*Ds[x][a]+count1[x]*Ds[x][b]+count2[x]*Ds[x][d]
      total = min(total,tmp)
print(total)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
d,c = [list(map(int,input().split())) for i in range(C)], [list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
cnt,t,ans = [[0 for j in range(C)] for i in range(3)],[[0 for j in range(C)] for i in range(3)],float("inf")
for i in range(N):
	for j in range(N):
		cnt[(i+j)%3][c[i][j]] += 1
for i in range(3):
	for j in range(C):
		t[i][j] = 0
		for k in range(C):
			t[i][j] += d[k][j] * cnt[i][k]; 
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,t[0][i]+t[1][j]+t[2][k])
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, c = map(int, input().split())
    cs = []
    ds = []

    cnums = []
    dsums = []

    for i in range(3):
        cnums.append([0]*c)
        dsums.append([0]*c)
    rs = []

    for i in range(c):
        ds.append(list(map(int, input().split())))
    for i in range(n):
        cs.append(list(map(int, input().split())))

    for x in range(n):
        for y in range(n):
            cnums[(x+y)%3][cs[y][x]-1] += 1

    for n in range(3):
        for i in range(c):
            s = 0
            for j in range(c):
                s += ds[j][i]*cnums[n][j]
            dsums[n][i] = s

    for i in range(3):
        mi = float('inf')
        mii = 0
        for n in range(c):
            if dsums[i][n] < mi:
                mi = dsums[i][n]
                mii = n
        for j in range(3):
            if j == i:
                continue
            mj = float('inf')
            mji = 0
            for n in range(c):
                if n == mii:
                    continue
                if dsums[j][n] < mj:
                    mj = dsums[j][n]
                    mji = n
            if (i == 0 and j == 1) or (i == 1 and j == 0):
                k = 2
            elif (i == 1 and j == 2) or (i == 2 and j == 1):
                k = 0
            else:
                k = 1
            mk = float('inf')
            mki = 0
            for n in range(c):
                if n == mii or n == mji:
                    continue
                if dsums[k][n] < mk:
                    mk = dsums[k][n]
                    mki = n
            rs.append(mi+mj+mk)
    print(min(rs))

main()

Submission status: Accepted

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

L = [[0]*C, [0]*C, [0]*C]
for i in range(N):
    for j in range(N):

        L[(i+j)%3][M[i][j]-1] += 1

D = np.array(D)
L = np.array(L)
P = np.dot(L, D)

ans = 999999999999999999999999999999999
"""
for i in range(3):
    c = np.argmin(P[i])
    for j in range(3):
        if i==j:
            continue
        else:
            c2 = np.argmin(P[j][])
            ans = min(ans, )
            """
for i in range(C):
    for j in range(C):
        if i==j: continue
        for h in range(C):
            if i==h or j==h: continue
            ans = min(ans, P[0][i] + P[1][j] + P[2][h])

print(ans)

Submission status: Accepted

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

A = [[0]*C, [0]*C, [0]*C] # color count
for i in range(N):
    x = 0
    y = i
    j = (x+y)%3
    while y>=0:
        A[j][c[y][x]-1] += 1
        y -= 1
        x += 1
#print(A)
for i in range(1, N):
    x = i
    y = N-1
    j = (x+y)%3
    while x<N:
        A[j][c[y][x]-1] += 1
        y -= 1
        x += 1
#print(A)

from itertools import permutations as p
ans = 1e10
for colors in p(range(C),3):
    tmp = 0
    for i in range(3):
        for j in range(C):
            tmp += A[i][j]*D[j][colors[i]]
    #print(colors, tmp)
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(50000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, CN, D, C):
    # for d in D:
    #     error_print(d)
    # for c in C:
    #     error_print(c)

    T = [[], [], []]
    for i, r in enumerate(C):
        for j, c in enumerate(r):
            T[(i + j) % 3].append((i, j, c))
    TC = [[], [], []]
    for j, t in enumerate(T):
        for i in range(CN):
            s = 0
            for c in t:
                s += D[c[2] - 1][i - 1]
            TC[j].append(s)

    ans = sys.maxsize
    for i, j, k in permutations(range(CN), 3):
        ans = min(ans, sum([TC[0][i], TC[1][j], TC[2][k]]))

    return ans


def main():

    N, CN = read_int_n()
    D = [read_int_n() for _ in range(CN)]
    C = [read_int_n() for _ in range(N)]
    print(slv(N, CN, D, C))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    N, C = [int(_) for _ in input().split()]
    nr0, nr1, nr2 = 0, 0, 0

    Diff = []
    for _ in range(C):
        Diff.append([int(__) for __ in input().split()])

    Color = []
    for _ in range(N):
        Color.append([int(__) for __ in input().split()])

    R0 = collections.defaultdict(lambda: 0)
    R1 = collections.defaultdict(lambda: 0)
    R2 = collections.defaultdict(lambda: 0)

    for y in range(N):
        for x in range(N):
            r = (y + x) % 3

            if r == 0:
                R0[Color[y][x]] += 1
                nr0 += 1
            elif r == 1:
                R1[Color[y][x]] += 1
                nr1 += 1
            else:
                R2[Color[y][x]] += 1
                nr2 += 1

    R0s = []
    for dist_color in range(C):
        d = 0
        for src_color in R0.keys():
            d += Diff[src_color-1][dist_color] * R0[src_color]

        R0s.append(d)

    R1s = []
    for dist_color in range(C):
        d = 0
        for src_color in R1.keys():
            d += Diff[src_color-1][dist_color] * R1[src_color]

        R1s.append(d)

    R2s = []
    for dist_color in range(C):
        d = 0
        for src_color in R2.keys():
            d += Diff[src_color-1][dist_color] * R2[src_color]

        R2s.append(d)
        
    ans = 10**100
    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

                ans = min(ans, R0s[i] + R1s[j] + R2s[k])

    print(ans)

main()

Submission status: Accepted

Solution code:
from itertools import *
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in [0]*C]
c = [list(map(int, input().split())) for _ in [0]*N]
tri = [[] for _ in [0]*3]
for i in range(1, N+1):
    for j in range(1, N+1):
        tri[(i+j) % 3] += [c[i-1][j-1] - 1]
incom = [[0]*C for _ in [0]*3]
for i in range(3):
    for color in range(C):
        incom[i][color] = sum(D[x][color] for x in tri[i])
ans = 1<<30
for p in permutations(range(C), 3):
    t = sum(incom[x][y]for x,y in enumerate(p))
    if t < ans: ans = t
print(ans)

Submission status: Accepted

Solution code:
# D
import numpy as np

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

C_cost_mat = np.zeros((C, C), dtype="int32")
now_mat = np.zeros((3, C), dtype="int32")

for i in range(C):
    c_list = list(map(int, input().split()))
    for j in range(C):
        C_cost_mat[i][j] = c_list[j]
        
for i in range(N):
    c_list = list(map(int, input().split()))
    for j in range(N):
        now_mat[(i + j + 2) % 3, c_list[j] - 1] += 1
        
res_mat = np.dot(now_mat, C_cost_mat)

res = 1000*N*N
for i1 in range(C):
    for i2 in range(C):
        for i3 in range(C):
            if i1 != i2 and i2 != i3 and i3 != i1:
                res = min(res, res_mat[0, i1] + res_mat[1, i2] + res_mat[2, i3])
print(res)

Submission status: Accepted

Solution code:
N, C = list(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())))

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

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

minCount = 500 * 500 * 10000

for i in range(1, C + 1):
    cost1 = 0
    for h in range(1, C + 1):
        cost1 += d[h - 1][i - 1] * e[0][h]

    for j in range(1, C + 1):
        if i == j:
            continue
        cost2 = 0
        for h in range(1, C + 1):
            cost2 += d[h - 1][j - 1] * e[1][h]

        for k in range(1, C + 1):

            if j == k or k == i:
                continue
            cost3 = 0
            for h in range(1, C + 1):
                cost3 += d[h - 1][k - 1] * e[2][h]

            minCount = min(minCount, cost1 + cost2 + cost3)

print(minCount)

Submission status: Accepted

Solution code:
import itertools, operator

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

Ds = list(map(list, zip(*Ds))) # 転置

cnts = [[0] * C for k in range(3)]
for i in range(N):
    for j in range(N):
        cnts[(i + j) % 3][cs[i][j] - 1] += 1

ws = [[0] * C for k in range(3)]
for k in range(3):
    for c in range(C):
        ws[k][c] = sum(map(operator.mul, cnts[k], Ds[c]))

ans = float('inf')
for x, y, z in itertools.permutations(range(C), 3):
    w = ws[0][x] + ws[1][y] + ws[2][z]
    ans = min(ans, w)

print(ans)

Submission status: Accepted

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

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

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

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

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

#print(colorNum)

minimum = 1000*500*500

def calc(i,j,k):
    cost = 0
    for color in range(C):
        c0 = colorNum[color][0]
        c1 = colorNum[color][1]
        c2 = colorNum[color][2]
    
        cost += c0 * d[color][i]
        cost += c1 * d[color][j]
        cost += c2 * d[color][k]
    return cost
        

for i in range(C):
    for j in range(C):
        if i==j:
            continue
        for k in range(C):
            if j==k or i==k:
                continue
            cand = calc(i,j,k)
            minimum = min(minimum,cand)

print(minimum)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import Counter
from pprint import pprint as pp
import itertools
import functools

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N,C = ria()
D = rian(C)
c = rian(N)

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

@functools.lru_cache(C*3)
def f2(color, mod3):
  ret_ = 0
  for color_now in range(1, C+1):
    ret_ += D[color_now-1][color-1] * syukei[mod3][color_now]
  return ret_

def f(colors, upper):
  ret_ = 0
  for mod3, color in enumerate(colors):
    ret_ += f2(color, mod3)
    if ret_ > upper:
      return upper
  return ret_

ret = N*N*1000
for colors in itertools.permutations(range(1, C+1), 3):
  ret = min(ret, f(colors, ret))
print(ret)

Submission status: Accepted

Solution code:
import itertools

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

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

c=[None]*N
for i in range(N):
    c[i]=list(map(int,input().split()))

c_0=[]
c_1=[]
c_2=[]

for i in range(N):
    for j in range(N):
        if (i+j+2)%3==0:
            c_0+=[c[i][j]]
        elif (i+j+2)%3==1:
            c_1+=[c[i][j]]
        else:
            c_2+=[c[i][j]]

clist_0=[0]*(C+1)
clist_1=[0]*(C+1)
clist_2=[0]*(C+1)

for i in c_0:
    clist_0[i]+=1
for i in c_1:
    clist_1[i]+=1    
for i in c_2:
    clist_2[i]+=1



L=[]
for i in range(C):
    L+=[i+1]

ROOP=list(itertools.permutations(L,3))


ANS=float("inf")


for i in range(len(ROOP)):
    IWA=0
    for j in range(1,C+1):
        IWA+=D[j-1][ROOP[i][0]-1]*clist_0[j]+D[j-1][ROOP[i][1]-1]*clist_1[j]+D[j-1][ROOP[i][2]-1]*clist_2[j]
        
    if ANS>IWA:
        ANS=IWA

print(ANS)

Submission status: Accepted

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

colors = [[0 for c in range(C)] for p in range(3)]

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

ans = float('inf')
for ptn in itertools.permutations(range(C),3):
    tmp = 0
    for p,ct in enumerate(ptn):
        for cf in range(C):
            tmp += D[cf][ct] * colors[p][cf]
    ans = min(ans, tmp)

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

diff0 = []
diff1 = []
diff2 = []

for color in range(1, C+1):
    d0 = 0
    d1 = 0
    d2 = 0
    for i in range(N):
        for j in range(N):
            diff = d[c[i][j]-1][color-1]
            if (i+j) % 3 == 0:
                d0 += diff
            elif (i+j) % 3 == 1:
                d1 += diff
            else:
                d2 += diff
    diff0.append(d0)
    diff1.append(d1)
    diff2.append(d2)

ans = 10**10
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, diff0[i] + diff1[j] + diff2[k])
print(ans)

Submission status: Accepted

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

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

res = 2*10**9
for i in range(C):
    for j in range(C):
        if i == j: continue
        for k in range(C):
            if k in (i, j): continue
            res = min(res, d[0][i]+d[1][j]+d[2][k])
else:
    print(res)