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: Runtime Error

Solution code:
N,C=map(int,input().split())
D=[]
for i in range(C):
    Dlist=list(map(int,input().split()))
    D.append(Dlist)
c=[[0]*N*N for i in range(3)]
x=[]
X=[]
for i in range(N):
    x=list(map(int,input().split()))
    X.append(x)
for i in range(N):
    for j in range(N):
        x=X[i][j]
        c[(i+j)%3][x-1]+=1
def func(res):
    for i in range(C):
        for j in range(C):
            if i!=j:
                for k in range(C):
                    if i!=k and j!=k:
                        total=0
                        for l in range(C):                           
                            total+=D[l][i]*c[0][l]
                            total+=D[l][j]*c[1][l]
                            total+=D[l][k]*c[2][l]
                        if total<res:
                            res=total
    return res
x=10**6
res=func(x)
print(res)

Submission status: Runtime Error

Solution code:
from itertools import product
N,C=map(int,input().split())
D=[]
for i in range(C):
    Dlist=list(map(int,input().split()))
    D.append(Dlist)
c=[[0]*N*N for i in range(3)]
x=[]
X=[]
for i in range(N):
    x=list(map(int,input().split()))
    X.append(x)
for i in range(N):
    for j in range(N):
        x=X[i][j]
        c[(i+j)%3][x-1]+=1
def func(res):
    print(res)
    for i in range(C):
        for j in range(C):
            if i!=j:
                for k in range(C):
                    if i!=k and j!=k:
                        total=0
                        for l in range(C):                           
                            total+=D[l][i]*c[0][l]
                            total+=D[l][j]*c[1][l]
                            total+=D[l][k]*c[2][l]
                        if total<res:
                            res=total
    return res
x=10**6
res=func(x)
print(res)

Submission status: Runtime Error

Solution code:
from itertools import product
N,C=map(int,input().split())
D=[]
for i in range(C):
    Dlist=list(map(int,input().split()))
    D.append(Dlist)
c=[[0]*N*N for i in range(3)]
x=[]
X=[]
for i in range(N):
    x=list(map(int,input().split()))
    X.append(x)
for i in range(N):
    for j in range(N):
        x=X[i][j]
        c[(i+j)%3][x-1]+=1
print(D,c)
def func(res):
    print(res)
    for i in range(C):
        for j in range(C):
            if i!=j:
                for k in range(C):
                    if i!=k and j!=k:
                        total=0
                        for l in range(C):                           
                            total+=D[l][i]*c[0][l]
                            total+=D[l][j]*c[1][l]
                            total+=D[l][k]*c[2][l]
                        if total<res:
                            res=total
    return res
x=10**6
res=func(x)
print(res)

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import Counter
 
n, c = map(int, input().split())
color_costs = [list(map(int, input().split())) for _ in range(c)]
matrix = [list(map(int, input().split())) for _ in range(n)]
 
colord = {(i, j):cost for i, row in enumerate(color_costs)
                      for j, cost in enumerate(row)}
 
res = []
for n in range(3):
  color_count = Counter(c-1 for i, row in enumerate(matrix) 
                            for j, c in enumerate(row) 
                            if (i + j) % 3 == n)
  def color_cost(color):
    return sum(colord[ccolor, color] * ccount for ccolor, ccount in color_count.items())
  cx = [(color, color_cost(color)) for color in range(c)]
  sorted_by_cost = sorted(cx, key=lambda x:x[1])
  cheapest3 = sorted_by_cost[:3]
  res.append(cheapest3)
 
color_pickss = product(*res)
filtered_unique = (picks for picks in color_pickss if len(set(x[0] for x in picks)) == 3)
costs = (sum(x[1] for x in picks) for pick in filtered_unique)
print(min(costs))
from itertools import product
from collections import Counter
 
n, c = map(int, input().split())
color_costs = [list(map(int, input().split())) for _ in range(c)]
matrix = [list(map(int, input().split())) for _ in range(n)]

colord = {(i, j):cost for i, row in enumerate(color_costs)
                      for j, cost in enumerate(row)}
 
res = []
for n in range(3):
  color_count = Counter(c-1 for i, row in enumerate(matrix) 
                            for j, c in enumerate(row) 
                            if (i + j) % 3 == n)
  def color_cost(color):
    return sum(colord[ccolor, color] * ccount for ccolor, ccount in color_count.items())
  cx = [(color, color_cost(color)) for color in range(c)]
  sorted_by_cost = sorted(cx, key=lambda x:x[1])
  cheapest3 = sorted_by_cost[:3]
  res.append(cheapest3)

color_pickss = product(*res)
filtered_unique = (picks for picks in color_pickss if len(set(x[0] for x in picks)) == 3)
costs = (sum(x[1] for x in picks) for picks in filtered_unique)
print(min(costs))

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import Counter
 
n, c = map(int, input().split())
color_costs = [list(map(int, input().split())) for _ in range(c)]
matrix = [list(map(int, input().split())) for _ in range(n)]

colord = {(i, j):cost for i, row in enumerate(color_costs)
                      for j, cost in enumerate(row)}
 
res = []
for n in range(3):
  color_count = Counter(c-1 for i, row in enumerate(matrix) 
                            for j, c in enumerate(row) 
                            if (i + j) % 3 == n)
  def color_cost(color):
    return sum(colord[ccolor, color] * ccount for ccolor, ccount in color_count.items())
  cx = [(color, color_cost(color)) for color in range(c)]
  sorted_by_cost = sorted(cx, key=lambda x:x[1])
  cheapest3 = sorted_by_cost[:3]
  res.append(cheapest3)

color_pickss = product(*res)
filtered_unique = (picks for picks in color_pickss if len(set(x[0] for x in picks)) == 3)
costs = (sum(x[1] for x in picks) for pick in filtered_unique)
print(min(costs))

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

n_color = [[0 for _ in range(3)] for _ in range(C)]
for i in range(N):
    for j in range(N):
        X = c[i][j] - 1
        n_color[(i + j + 2) % 3][X] += 1

ans = float('inf')
for paint in permutations(range(C), 3):
    cost = 0
    for ij3 in range(3):
        Y = paint[ij3]
        for X in range(C):
            cost += D[X][Y] * n_color[ij3][X]
    ans = min(ans, cost)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

# @functools.lru_cache(maxsize=None)
# def paint(i, c):  # i = 0, 1, 2
#     cost = 0
#     for row in range(N):
#         for col in range(N):
#             if (row + col) % 3 == i:
#                 cost += D[G[row][col] - 1][c - 1]

#     return cost

# def cost(comb):
#     cost = 0
#     for i, c in enumerate(comb):
#         cost += paint(i, c)

#     return cost


def cost(comb):
    cost = 0
    for r in range(N):
        for c in range(N):
            if (r + c) % 3 == 0:
                cost += D[G[r][c] - 1][comb[0]]
            elif (r + c) % 3 == 1:
                cost += D[G[r][c] - 1][comb[1]]
            else:
                cost += D[G[r][c] - 1][comb[2]]


if __name__ == '__main__':
    from itertools import permutations
    N, C = map(int, input().split())
    D = [[int(_) for _ in input().split()] for i in range(C)]
    G = [[int(_) for _ in input().split()] for i in range(N)]
    combs = permutations(range(1, C + 1), 3)
    min_cost = min([cost(comb) for comb in combs])
    print(min_cost)

Submission status: Runtime Error

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

group = [[] for _ in range(3)]

for i in range(N):
    for j in range(N):
        group[(i + j) % 3].append(grid[i][j])

color_costs = [[] for _ in range(C)]
for i in range(3):
    cost = 0
    for j in range(1, C + 1):
        for k in group[i]:
            cost += costs[k - 1][j - 1]
        color_costs[i].append(cost)
        cost = 0

min_cost = float('inf')
ccost = 0
offset = 0
for i in range(len(color_costs)):
    ccost = 0
    for j in range(len(color_costs)):
        ccost += color_costs[j][(j + offset) % C]
    offset += 1
    if min_cost > ccost:
        min_cost = ccost
print(min_cost)

Submission status: Runtime Error

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

sumD = 0
for i in range(N):
    for j in range(N):
        for x in range(N):
            for y in range(N):
                if (i+j)%3 == (x+y)%3:
                    if c[i][j] != c[x][y]:
                        if D[c[i][j]-1][c[x][y]-1] < D[c[x][y]-1][c[i][j]-1]:
                            sumD += D[c[i][j]-1][c[x][y]-1]
                            c[i][j] = c[x][y]
                        else:
                            sumD += D[c[x][y]-1][c[i][j]-1]
                            c[x][y] = c[i][j]
                else:
                    if c[i][j] == c[x][y]:
                        tmp, tmp2 = [], []
                        for n in range(N):
                            for m in range(N):
                                if n != i or m != j:
                                    if c[i][j] != c[n][m]:
                                        tmp.append([n,m])
                                        tmp2.append(D[c[i][j]-1][c[n][m]-1])
                        n,m = tmp[tmp2.index(min(tmp2))]
                        c[i][j] = c[n][m]
                        sumD += D[c[i][j]-1][c[n][m]-1]
print(sumD)

Submission status: Runtime Error

Solution code:
n, c = map(int, input().split())
D = []
C0 = []
C1 = []
C2 = []
for i in range(c):
    row = []
    rowinput = input().split()
    for j in range(c):
        row.append(int(rowinput[j]))
    D.append(row)
for i in range(n):
    row = []
    rowinput = input().split()
    for j in range(n):
        if (i + j + 2) % 3 == 0:
            C0.append(int(rowinput[j]))
        elif (i + j + 2) % 3 == 1:
            C1.append(int(rowinput[j]))
        else:
            C2.append(int(rowinput[j]))
mini = -1
for color0 in range(c):
    for color1 in range(c):
        if color0 != color1:
            for color2 in range(c):
                if color0 != color2 and color1 != color2:
                    total = 0
                    for c0 in C0:
                        if c0 != color0:
                            total += D[c0][color0]
                    for c1 in C1:
                        if c1 != color1:
                            total += D[c1][color1]
                    for c2 in C2:
                        if c2 != color2:
                            total += D[c2][color2]
                    if mini == -1 or total < mini:
                        mini = total
print(mini)

Submission status: Runtime Error

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

sep = {0:[0 for i in range(C)],1:[0 for i in range(C)],2:[0 for i in range(C)]}
for i,cx in enumerate(c):
    for j,cy in enumerate(cx):
        if len(c) == 2 and (i + j) % 3 == 2:
            sep[(i + j) % 3 - 1][cy -1] += 1
        else:
            sep[(i + j) % 3][cy - 1] += 1
minimums = [[],[],[]]
for key,values in sep.tems():
    for i in range(C):
        m0 = 0
        am0 = 0
        m1 = 0
        am1 = 1
        deposit = 0
        for j,value in enumerate(values):
            deposit += D[j][i] * valuea
        sep[key].append(deposit)
min0 = min(sep[0])
min1 = min(sep[1])
min2 = min(sep[2])

print(min1 + min2 + min0)

Submission status: Runtime Error

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))
    cost[0].sort()
    cost[1].sort()
    cost[2].sort()
    res=3000000
    for i in range(N):
        for j in range(N):
            for k in range(N):
                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])
                if cost[0][i][0]+cost[1][j][0]+cost[2][k][0]>res:
                    break

    print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N,C = map(int, raw_input().split())
da=[]
db=[]
dc=[]

colorGrid = [map(int, raw_input().split()) for _ in range(C)]

dataGrid = [map(int, raw_input().split()) for _ in range(N)]

for i in range(N):
	for j in range(N):
		d=i+j+2
		inn=dataGrid[i][j]
		if d%3==0:
			da.append(inn)
		elif d%3==1:
			db.append(inn)
		else:
			dc.append(inn)

ka=range(C)
kb=range(C)
kc=range(C)
du = lambda oc, tc : colorGrid[oc][dc]
for i in range(C):
	ka[i]=sum([du(oc, i) for oc in da])
	kb[i]=sum([du(oc, i) for oc in db])
	kc[i]=sum([du(oc, i) for oc in dc])	


ra=ka.sort()[0:3]
rb=kb.sort()[0:3]
rc=kc.sort()[0:3]

mm=-1
for i in range(3):
	for j in range(3):
		for k in range(3):
			d=ra[i]+rb[j]+rc[k]
			if mm == -1 or d< mm:
				mm=d

print mm

Submission status: Runtime Error

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

sep = {0:[0 for i in range(C)],1:[0 for i in range(C)],2:[0 for i in range(C)]}
for i,cx in enumerate(c):
    for j,cy in enumerate(cx):
        sep[(i + j) % 3][cy] + = 1
minimums = [[],[],[]]
for key,values in sep.tems():
    for i in range(C):
        m0 = 0
        am0 = 0
        m1 = 0
        am1 = 1
        deposit = 0
        for j,value in enumerate(values):
            deposit += D[j][i] * valuea
        sep[key].append(deposit)
min0 = min(sep[0])

min1 = min(sep[1])
min2 = min(sep[2])
min3 = min(sep[2])

print(min1 + min2 + min3)

Submission status: Runtime Error

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.matmul(now_mat, C_cost_mat)

res = 3000
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: Runtime Error

Solution code:
from math import inf
D = []
c = []
d = {}
N,C = map(int,input().split())
for i in range(C):
    D.append(list(map(int,input().split())))
for i in range(N):
    c.append(list(map(int,input().split())))

for C1 in range(C):
    for C2 in range(C):
        for C3 in range(C):
            if C1 != C2 and C2 != C3 and C3 != C1:
                d[(C1+1,C2+1,C3+1)]=0
            else:
                d[C1+1,C2+1,C3+1]=inf

for i in range(N):
    for j in range(N):
        for C1 in range(C):
            for C2 in range(C):
                for C3 in range(C):
                    if (i+j)%3==0:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C1]
                    elif (i+j)%3==1:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C2]
                    else:
                        d[(C1+1,C2+1,C3+1)]+=D[c[i][j]-1][C3]

l = []
for x in d:
    l.append(d[x])
print(min(l))

Submission status: Runtime Error

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 = now_mat @ C_cost_mat

res = 3000
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: Runtime Error

Solution code:
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N, C;
    cin >> N >> C;
    vector<vector<int>> D(C, vector<int>(C));
    vector<vector<int>> c(N, vector<int>(N));
    for(int i=0; i<C; i++)
        for(int j=0; j<C; j++)
            cin >> D[i][j];
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> c[i][j];

    if(N == 1){
        cout << 0 << endl;
        return 0;
    }
    vector<vector<int>> v(3, vector<int>(C, 0));
    for(int i=0; i<C; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<N; k++){
                int l = (j + k) % 3;
                v[l][i] += D[c[j][k]-1][i];
            }
        }
    }
    int ans = 1<<30;
    for(int i=0; i<C; i++)
        for(int j=0; j<C; j++)
            for(int k=0; k<C; k++){
                if(i == j || j == k || k == i) continue;
                int tmp = v[0][i] + v[1][j] + v[2][k];
                ans = min(ans, tmp);
            }
    cout << ans << endl;
    return 0;
}