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 numpy

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

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

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

mod = [ [ 0 for _ in range(m) ] for _ in range(3) ]

for i in range(n):
    for j in range(n):
        if ( i + j )% 3 == 0:
            mod[2][c[i][j] - 1] += 1
        elif ( i + j )% 3 == 1:
            mod[0][c[i][j] - 1] += 1
        else:
            mod[1][c[i][j] - 1] += 1

tri = []
num = []
for i in range(3):
    temp = [ 0 for _ in range(m) ]
    for j in range(m):
        for k in range(m):
            temp[j] += mod[i][k] * d[k][j]
    tri.append(list(numpy.argsort(temp)[:3]))
    num.append(list(numpy.sort(temp)[:3]))

if tri[0][0] != tri[1][0] and tri[1][0] != tri[2][0] and tri[2][0] != tri[0][0]:
    print(num[0][0] + num[1][0] + num[2][0])
    exit()

result = []
for i in range(3):
    for j in range(3):
        if tri[0][i] == tri[1][j]:
            continue
        for k in range(3):
            if tri[1][j] == tri[2][k] or tri[2][k] == tri[0][i]:
                continue
            else:
                result.append(num[0][i] + num[1][j] + num[2][k])

print(min(result))

Submission status: Accepted

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]*(10**6) 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
y=10**20
res=func(y)
print(res)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
arrD = list(list(map(int, input().split())) for i in range(c))
arrC = list(list(map(int, input().split())) for i in range(n))
 
##剰余r=0,1,2で、
    ##色の出現数を確認する -> いずれかの色に統一する
        ##どの色に統一するか全パターンを実施して、違和感を算出
##和を取る

 ## arrCCnt[r][c]: 剰余rグループにおける初期色cのマス数
arrCCnt = []
for r in range(3):
    arrCCnt.append([0] * (c + 1))
for i in range(1, n + 1):
    for j in range(1, n + 1):
        r = (i + j) % 3
        oriC = arrC[i - 1][j - 1]
        arrCCnt[r][oriC] += 1

ret = float('inf')
for c0 in range(1, c + 1):
    for c1 in range(1, c + 1):
        if (c0 != c1):
            for c2 in range(1, c + 1):
                 if (c1 != c2) and (c2 != c0):
                    arrToC = [c0, c1, c2]
                    buf = 0
                    for r in range(3):
                        for oriC in range(1, c + 1):
                            buf += arrD[oriC - 1][arrToC[r] - 1] * arrCCnt[r][oriC]
                    ret = min(ret, buf)
print(ret)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

# 3行にまとめる
c_listed = [{},{},{}]

for i in range(N):
    for j in range(N):
        index = (i + j) % 3
        c_listed[index][c[i][j]] = c_listed[index].get(c[i][j], 0) + 1

# 色の選び方
color_seq = permutations(range(C), 3)

ret = N * N * 1000
for color in color_seq:
    count = 0
    for line, line_color in zip(c_listed, color):
        for f, v in line.items():
            # f to line_color
            count += d[f-1][line_color] * v

    # 
    if count < ret:
        ret = count

print(ret)

Submission status: Accepted

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 picks in filtered_unique)
print(min(costs))

Submission status: Accepted

Solution code:
from itertools import product
from collections import Counter
 
n, c = map(int, input().split())
color_costs = [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)}
 
color_counts = []
for n in range(3):
  counter = Counter(c-1 for i, row in enumerate(matrix) 
                                       for j, c in enumerate(row) 
                                       if (i+j)%3==n)
  color_counts.append(counter)
 
cc = [[(color, sum(colord[cellcolor, color]*n for cellcolor, n in color_count.items()))
                                                                    for color in range(c)]
                                                                    for color_count in color_counts]
 
dd = [sorted(xs, key=lambda x:x[1])[:3] for xs in cc]
ee = (a[1]+b[1]+c[1] for a, b, c in product(*dd) if len(set((a[0], b[0], c[0]))) == 3)
print(min(ee))

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)]
a = [[0]*C for _ in range(3)]
for i in range(n):
    for j in range(n):
        a[(i+j)%3][c[i][j]-1] += 1
b = [[0]*C for _ in range(3)]
for i in range(3):
    for j in range(C):
        v = 0
        for k in range(C):
            v += a[i][k]*d[k][j]
        b[i][j] = v
r = 10**9
for i in range(C):
    for j in range(C):
        for k in range(C):
            if len({i,j,k}) == 3:
                r = min(r, b[0][i]+b[1][j]+b[2][k])
print(r)

Submission status: Accepted

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(C)] for _ in range(3)]
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: Accepted

Solution code:
from collections import Counter
N, C = list(map(int, input().split()))
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]
'''
D0 = {}
D1 = {}
D2 = {}
for color in range(1, C + 1):
    D0[color] = 0
    D1[color] = 0
    D2[color] = 0
    
for color in range(1, C + 1):
    for i in range(N):
        for j in range(N):
            if (i + j) % 3 == 0:
                D0[color] = D0[color] + D[ c[i][j] - 1 ][ color - 1 ] 
            if (i + j) % 3 == 1:
                D1[color] = D1[color] + D[ c[i][j] - 1 ][ color - 1 ] 
            if (i + j) % 3 == 2:
                D2[color] = D2[color] + D[ c[i][j] - 1 ][ color - 1 ] 

ans = 1000000000000000
for i in range(1, C + 1):
    for j in range(1, C + 1):
        for k in range(1, C + 1):
            if i != j and j != k and k != i:
                tmp = D0[i] + D1[j] + D2[k]
                if tmp < ans:
                    ans = tmp
print(ans)
'''
diclist = [Counter() for _ in range(3)]
for i in range(N):
    for j in range(N):
        diclist[(i+j)%3][c[i][j]] += 1

ans = 100000000000000
for i in range(C):
    for j in range(C):
        for k in range(C):
            tmp = 0
            if i != j and j != k and k != i:
                for l, v in diclist[0].items():
                    tmp += D[l - 1][i] * v
                for l, v in diclist[1].items():
                    tmp += D[l - 1][j] * v
                for l, v in diclist[2].items():
                    tmp += D[l - 1][k] * v
                if tmp < ans:
                    ans = tmp
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 20

n, c = map(int, input().split())
d_mp = [list(map(int, input().split())) for _ in range(c)]
c_mp = [list(map(int, input().split())) for _ in range(n)]
dic_lst = [dict() for _ in range(3)]

for x in range(n):
  for y in range(n):
    s = (x + 1 + y + 1) % 3
    v = c_mp[y][x]
    if v in dic_lst[s]:
      dic_lst[s][v] += 1
    else:
      dic_lst[s][v] =  1

ans = INF
for x in range(c):
  for y in range(c):
    for z in range(c):
      if x != y and x != z and y != z:
        score = 0
        dic1 = dic_lst[0]
        for k, v in dic1.items():
          score += d_mp[k - 1][x] * v
        dic2 = dic_lst[1]
        for k, v in dic2.items():
          score += d_mp[k - 1][y] * v
        dic3 = dic_lst[2]
        for k, v in dic3.items():
          score += d_mp[k - 1][z] * v
        ans = min(score, ans)

print(ans)

Submission status: Accepted

Solution code:
#!/bin/python

import math
import os
import random
import re
import sys

def solution(color, cost):
    global counter_mod
    for i in range(len(color)):
        for j in range(len(color)):
            counter_mod[(i+j)%3][color[i][j]-1] += 1
    min = sys.maxint
    for i in range(len(cost)):
        for j in range(len(cost)):
            if j == i:
                continue
            for k in range(len(cost)):
                if (k == i or k == j):
                    continue
                sum = 0
                for l in range(len(counter_mod[0])):
                    sum += counter_mod[0][l]*cost[l][i]
                    sum += counter_mod[1][l]*cost[l][j]
                    sum += counter_mod[2][l]*cost[l][k]
                if sum < min:
                    min = sum
    return min

if __name__ == '__main__':
    
    nk = raw_input().split()
    n = int(nk[0])
    c = int(nk[1])
    color = []
    cost = []
    temp_counter = []
    for i in range(c):
        temp = raw_input().split()
        for j in range(c):
            temp[j] = int(temp[j])
        cost.append(temp)
        temp_counter.append(0)
    counter_mod = [temp_counter[:],temp_counter[:],temp_counter[:]]
    
    for i in range(n):
        temp = raw_input().split()
        for j in range(n):
            temp[j] = int(temp[j])
        color.append(temp)
    
    result = solution(color, cost)

    print result

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import nsmallest
from itertools import product

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

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

preliminary = [nsmallest(3, ((sum(tbl[pc][color] * cnt for pc, cnt in grid_count[s].items()), color)
                             for color in range(c))) for s in range(3)]

ans = float('inf')
for (v0, c0), (v1, c1), (v2, c2) in product(*preliminary):
    if c0 == c1 or c1 == c2 or c2 == c0:
        continue
    ans = min(ans, v0 + v1 + v2)
print(ans)

Submission status: Accepted

Solution code:
from heapq import nsmallest
from itertools import product


def calc(start, color):
    _n, _tbl, _grids = n, tbl[color], grids
    ret = 0
    for i in range(start, _n - 1, 3):
        j = 0
        while i >= 0:
            # print('calc', start, c, i, j, ret)
            ret += _tbl[_grids[i][j]]
            i -= 1
            j += 1
    for j in range((start + 1 - _n % 3) % 3, _n, 3):
        i = _n - 1
        while j < _n:
            # print('calc', start, c, i, j, ret)
            ret += _tbl[_grids[i][j]]
            i -= 1
            j += 1
    return ret


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

tbl = list(zip(*tbl))
for row in grids:
    for i, k in enumerate(row):
        row[i] = k - 1

preliminary = []
for s in range(3):
    preliminary.append(nsmallest(3, ((calc(s, color), color) for color in range(c))))

ans = float('inf')
for (v0, c0), (v1, c1), (v2, c2) in product(*preliminary):
    if c0 == c1 or c1 == c2 or c2 == c0:
        continue
    ans = min(ans, v0 + v1 + v2)
print(ans)

Submission status: Accepted

Solution code:
N,C = [int(i) for i in input().split()]
D = [[int(j) for j in input().split()] for i in range(C)]
c_temp = [[int(j)-1 for j in input().split()] for i in range(N)]
c = [[0 for i in range(C)] for j in range(3)]
for i in range(N):
    for j in range(N):
        c[(i+j)%3][c_temp[i][j]] += 1

min = 10**15
for i in [ii for ii in range(C)]:
    for j in [jj for jj in range(C) if jj != i]:
        for k in [kk for kk in range(C) if kk != i and kk != j]:
            count = sum([D[x][i]*c[0][x] + D[x][j]*c[1][x] + D[x][k]*c[2][x] for x in range(C)])
            if min > count:
                min = count
print(min)

Submission status: Accepted

Solution code:
from itertools import permutations

n, c = map(int, input().split())
D = [list(map(int, input().split())) for i in range(c)]
C = [list(map(int, input().split())) for i in range(n)]
oc = []
for i in range(3):
  oc.append([0]*c)
ans = float('Inf')
for i in range(n):
  for j in range(n):
    if (i + j + 2) % 3 == 0:
      oc[0][C[i][j]-1] += 1
    elif (i + j + 2) % 3 == 1:
      oc[1][C[i][j]-1] += 1
    elif (i + j + 2) % 3 == 2:
      oc[2][C[i][j]-1] += 1

combo = list(permutations(range(0,c), 3))
for a, b, c in combo:
  temp = 0
  for i in range(len(oc[0])):
    temp += oc[0][i] * D[i][a]
    temp += oc[1][i] * D[i][b]
    temp += oc[2][i] * D[i][c]
  ans = min(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__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)]
    # D = [[0 for _ in range(C)] for __ in range(C)]
    # c = [[0 for _ in range(N)] for __ in range(N)]
    gr = [[0 for __ in range(C + 1)] for _ in range(3)]
    # for i in range(C):
    #     tmp = input().split()

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

    ans = 500000000000000000000000
    for g1 in range(1, C + 1):
        for g2 in range(1, C + 1):
            for g3 in range(1, C + 1):
                if g1 != g2 and g1 != g3 and g2 != g3:
                    tmp = 0
                    for i in range(1, C + 1):
                        tmp += gr[0][i] * D[i - 1][g1 - 1]
                        tmp += gr[1][i] * D[i - 1][g2 - 1]
                        tmp += gr[2][i] * D[i - 1][g3 - 1]
                    ans = min(tmp, ans)

    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

grid=defaultdict(int)
grid2=defaultdict(int)
grid3=defaultdict(int)

def culc(dict,c):
  ans=0
  for a,b in dict.items():
    ans+=D[a-1][c]*b
  return ans

for i in range(N):
  for j in range(N):
    if (i+j)%3 == 0:
      grid[c[i][j]]+=1
    elif (i+j)%3 == 1:
      grid2[c[i][j]]+=1
    else:
      grid3[c[i][j]]+=1

res=10000000000000000000
for i in range(C):
  for j in range(C):
    for k in range(C):
      if i!=j and j!=k and i!=k:
        res=min(res,culc(grid,i)+culc(grid2,j)+culc(grid3,k))
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
N,C=map(int,input().split())
D=[]
for c in range(C):
    D.append(list(map(int,input().split())))
c=[]
for i in range(N):
    c.append(list(map(lambda x:int(x)-1,input().split())))
color=[[0]*(C) for i in range(3)]
cost=[[0]*(C) for i in range(3)]
for i in range(N):
    for j in range(N):
        mod=(i+j+2)%3
        oldc=c[i][j]
        for ci,cl in enumerate(D[oldc]):
            cost[mod][ci]+=cl
mnc=float('inf')
for i,j,k in permutations(range(C),3):
    cst=cost[0][i] + cost[1][j]+cost[2][k]
    if cst<mnc:
        mnc=cst
print(mnc)

Submission status: Accepted

Solution code:
from itertools import permutations, product
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)]

zero = []
one = []
two = []
for i, j in product(range(N), repeat=2):
	if (i + j) % 3 == 0:
		zero.append(c[i][j])
	elif (i + j) % 3 == 1:
		one.append(c[i][j])
	else:
		two.append(c[i][j])

zero = Counter(zero)
one = Counter(one)
two = Counter(two)

iwakan_min = float("inf")

for p, q, r in permutations(range(0, C), r=3):
	iwakan = 0
	for key, value in zero.items():
		iwakan += value * (D[key - 1][p])
	for key, value in one.items():
		iwakan += value * (D[key - 1][q])
	for key, value in two.items():
		iwakan += value * (D[key - 1][r])
	if iwakan < iwakan_min:
		iwakan_min = iwakan

print(iwakan_min)

Submission status: Accepted

Solution code:
import copy
import sys
import time

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, C] = [long(input_raw[0]), long(input_raw[1])]
    grid = []
    D = []

    for i in range(C):
        input_raw = read_func().strip().split()
        row = [long(input_raw[i]) for i in range(len(input_raw))]
        D.append(row)

    for i in range(N):
        input_raw = read_func().strip().split()
        row = [long(input_raw[i]) for i in range(len(input_raw))]
        grid.append(row)

    grid_color_dic = {}
    for i in range(3):
        grid_color_dic[i] = [0 for j in range(C)]

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

    score = [[0 for i in range(C)] for j in range(3)]
    for g in range(3):
        for now_color in range(len(grid_color_dic[g])):
            for next_color in range(C):
                #if grid_color_dic[g][now_color] > 0:
                score[g][next_color] += D[now_color][next_color] * grid_color_dic[g][now_color]



    order = [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]
    s_min = sys.maxint
    for o in order:
        min_score=[sys.maxint for i in range(3)]
        arg_min_score =[0 for i in range(3)]
        for g in o:
            for color in range(C):
                if min_score[g] > score[g][color] and color != arg_min_score[(g + 1) % 3] and color != arg_min_score[(g - 1) % 3]:
                    min_score[g] = score[g][color]
                    arg_min_score[g] = color

        s = 0
        for i in range(len(min_score)):
            s += min_score[i]
        if s < s_min:
            s_min = s

    print s_min

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
n, c = map(int, input().split())
color_costs = [map(int, input().split()) for _ in range(c)]
matrix = [map(int, input().split()) for _ in range(n)]
colord = {(i+1, j+1):cost for i, row in enumerate(color_costs)
                         for j, cost in enumerate(row)}
 
cellgroups = [[] for _ in range(3)]
for i, row in enumerate(matrix):
  for j, color in enumerate(row):
    cellgroups[(i+1+j+1)%3].append(color)
  
cc = [[(color, sum(colord[cellcolor, color] for cellcolor in cells))
	       									for color in range(1,c+1)]
      										for cells in cellgroups]
 
dd = [sorted(xs, key=lambda x:x[1])[:3] for xs in cc]
ee = (a[1]+b[1]+c[1] for a, b, c in product(*dd) if len(set((a[0], b[0], c[0]))) == 3)
print(min(ee))

Submission status: Accepted

Solution code:
def d_good_grid(N, C, D, c):
    # cの各要素は、0-indexedに対応するため入力から1引いている
    import collections
    import itertools

    # マスを (i+j)%3 で同一視したとき、
    # 同一視できるマスのそれぞれは最初何色で塗られているか
    colors = [collections.defaultdict(int) for _ in range(3)]
    for i, row in enumerate(c):
        for j, color in enumerate(row):
            colors[(i + j) % 3][color] += 1

    # strangeness[k][c]は値kで同一視できるマスをすべて色cで塗ったときの違和感の和
    strangeness = []
    for k in range(3):
        tmp = []
        for c in range(C):
            total = 0
            for color, num in colors[k].items():
                total += D[color][c] * num
            tmp.append(total)
        strangeness.append(tmp)

    # 色の一覧から3色選び、同一視できるマス3種をそれらで塗ってみる
    # 違和感が一番低かったものが解
    ans = float('inf')
    for c1, c2, c3 in itertools.permutations(range(C), 3):
        ans = min(ans, strangeness[0][c1] + strangeness[1][c2] + strangeness[2][c3])
    return ans

N, C = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(C)]
c = [[int(i) - 1 for i in input().split()] for j in range(N)]
print(d_good_grid(N, C, D, c))

Submission status: Accepted

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

D = []
c = []

for a in range(C):
    D.append(map(int, raw_input().split()))

for a in range(N):
    c.append(map(int, raw_input().split()))

cc = [[] for j in range(3)]

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

c0 = [-1]
c1 = [-1]
c2 = [-1]

for i in range(1, C + 1):
    v = 0
    for j in cc[0]:
        v += D[j - 1][i - 1]
    c0.append(v)

for i in range(1, C + 1):
    v = 0
    for j in cc[1]:
        v += D[j - 1][i - 1]
    c1.append(v)

for i in range(1, C + 1):
    v = 0
    for j in cc[2]:
        v += D[j - 1][i - 1]
    c2.append(v)

res = pow(10, 100)

for i in range(1, C + 1):
    for j in range(1, C + 1):
        if i == j: 
            continue
        for z in range(1, C + 1):
            if i == z or j == z: 
                continue

            if res > c0[i] + c1[j] + c2[z]:
                res = c0[i] + c1[j] + c2[z]

print res

Submission status: Accepted

Solution code:
from itertools  import product, permutations

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

res = 1000*N*N

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


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

for c1, c2, c3 in permutations(range(C), 3):
    score = 0
    for cc, cn in enumerate(cnt[0]):
        score += cn*D[cc][c1]
    for cc, cn in enumerate(cnt[1]):
        score += cn*D[cc][c2]
    for cc, cn in enumerate(cnt[2]):
        score += cn*D[cc][c3]
    if res > score:
        res = score

print(res)

Submission status: Accepted

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

Submission status: Accepted

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

choices = [[0 for x in range(C)] for x in range(3)]
for i in range(N):
    for j in range(N):
        choices[(i+j)%3][grid[j][i]-1] += 1

ans = 10**18
for i in range(C):    
    for j in range(C):
        if j == i:
            continue
        for k in range(C):
            if k != i and k != j:
                temp = 0
                for l in range(C):
                    temp += wrongness[l][i]*choices[0][l]
                    temp += wrongness[l][j]*choices[1][l]
                    temp += wrongness[l][k]*choices[2][l]
                ans = min(ans,temp)

print(ans)

Submission status: Accepted

Solution code:
N,C=[int(i) for i in input().split()]
D=[[int(j) for j in input().split()] for i in range(C)]
c=[[int(j)-1 for j in input().split()] for i in range(N)]#0-indexed

cate=[[0 for j in range(C)] for i in range(3)]#category divide
for i in range(N):
    for j in range(N):
        cate[(i+j)%3][c[i][j]]+=1
score = 9999999999#answer

#O(30 Comb 3)≒5*10^3
for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if c1==c2 or c2==c3 or c3==c1:
                continue
            nowsc = 0
            cset = [c1,c2,c3]
            #O(3*C)=90 →4.5*10^5
            for i in range(3):
                for j in range(C):
                    num = cate[i][j]
                    nowsc += D[j][cset[i]]*num
            score=min(score,nowsc)
print(score)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
arrD = list(list(map(int, input().split())) for i in range(c))
arrC = list(list(map(int, input().split())) for i in range(n))

##剰余r=0,1,2で、
    ##色の出現数を確認する -> いずれかの色に統一する
        ##どの色に統一するか全パターンを実施して、違和感を算出
##和を取る

arrCCnt = []
for r in range(3):
    d = dict()
    for i in range(1, c + 1):
        d[i] = 0
    arrCCnt += [d]

ret = 1000 * 500 * 500
for r in range(3):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if (i + j) % 3 == r:
                arrCCnt[r][arrC[i - 1][j - 1]] += 1##色の出現数を確認

##print(arrCCnt)
for c0 in range(1, c + 1):
    for c1 in range(1, c + 1):
        for c2 in range(1, c + 1):
            if c0 != c1 and c1 != c2 and c2 != c0:
                buf = 0
                ##print(c0,c1,c2)
                for i0 in range(1, c + 1):
                    ##print(i0)
                    buf += arrD[i0 - 1][c0 - 1] * arrCCnt[0][i0]##数
                for i1 in range(1, c + 1):
                    buf += arrD[i1 - 1][c1 - 1] * arrCCnt[1][i1]##数
                for i2 in range(1, c + 1):
                    buf += arrD[i2 - 1][c2 - 1] * arrCCnt[2][i2]##数
                ret = min(ret, buf)
print(ret)

Submission status: Accepted

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

from collections import defaultdict
from itertools import permutations

xs = [defaultdict(int) for _ in range(3)]

for i, row in enumerate(c):
    for j, x in enumerate(row):
        xs[(i + j) % 3][x] += 1

cs = [[sum(D[x][j] * num for x, num in xs[i].items()) for j in range(C)] for i in range(3)]

result = min(
    cs[0][c1] + cs[1][c2] + cs[2][c3]
    for c1, c2, c3
    in permutations(range(C), 3)
)
    
print(result)

Submission status: Accepted

Solution code:
import itertools

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

ans = 10**10

group = {g: {c: 0 for c in range(C)} for g in range(3)}
for i, row in enumerate(grid):
    for j, r in enumerate(row):
        group[(i+j)%3][r-1] += 1

for tup in itertools.combinations(range(C), 3):
    for c1, c2, c3 in itertools.permutations(tup):
        temp = 0
        for c in range(C):
            for g, col in zip(range(3), [c1, c2, c3]):
                temp += group[g][c] * D[c][col]
        if ans > temp:
            ans = temp
            
print(ans)

Submission status: Accepted

Solution code:
N, C = list(map(int, input().split()))
D = []
t = [[0 for j in range(30)] for i in range(3)]
for i in range(C):
    D.append(list(map(int, input().split())))
for i in range(N):
    l = list(map(int, input().split()))
    for j in range(N):
        t[(i+j)%3][l[j]-1] += 1
res = float('inf')
for i in range(C):
    for j in range(C):
        if i != j:
            for k in range(C):
                if i != k and j != k:
                    tt = 0
                    for l in range(C):
                        tt += D[l][i]*t[0][l]
                        tt += D[l][j]*t[1][l]
                        tt += D[l][k]*t[2][l]
                    if tt < res:
                        res = tt
print(res)

Submission status: Accepted

Solution code:
n,c = (int(i) for i in input().split())
d = [[int(i) for i in input().split()] for i in range(c)]
x = [[int(i) for i in input().split()] for i in range(n)]
lis0,lis1,lis2 = [0 for i in range(c)],[0 for i in range(c)],[0 for i in range(c)]
for i in range(n):
	for j in range(n):
		if (i+j)%3==0: lis2[x[i][j]-1]+=1
		elif (i+j)%3==1: lis0[x[i][j]-1]+=1
		else: lis1[x[i][j]-1]+=1
from itertools import permutations
y,ans = [i for i in range(c)],float("inf")
for i,j,k in list(permutations(y,3)):
	num = 0
	for i2 in range(c): num+=lis0[i2]*d[i2][i]+lis1[i2]*d[i2][j]+lis2[i2]*d[i2][k]
	ans = min(ans,num)
print(ans)