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

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 y in range(N):
    for x in range(N):
        t = ((x + 1) + (y + 1)) % 3
        a[t][c[y][x] - 1] += 1

result = float('inf')
for b in permutations(range(C), 3):
    t = 0
    for i in range(3):
        ai = a[i]
        bi = b[i]
        for j in range(C):
            t += ai[j] * D[j][bi]
    result = min(result, t)
print(result)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
diff=[list(map(int, input().split())) for _ in range(c)]
color=[list(map(int, input().split())) for _ in range(n)]

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

for i in range(n):
    for j in range(n):
        dic[(i+j)%3][color[i][j]-1]+=1

result=10**9

for aa in range(c):
    #%0の色をaaにする
    a_cost=0
    for j in range(c):
        a_cost+=dic[0][j]*diff[j][aa]


    for bb in range(c):
        if aa!=bb:
            #%1の色をbbにする
            b_cost=0
            for j in range(c):
                b_cost+=dic[1][j]*diff[j][bb]

            for cc in range(c):
                if aa!=bb and bb!=cc and cc!=aa:
                    #%2の色をccにする
                    c_cost=0
                    for j in range(c):
                        c_cost+=dic[2][j]*diff[j][cc]
                    result=min(result,a_cost+b_cost+c_cost)

print(result)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
import copy as cp

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

MAX_N = 505
MAX_C = 35
D = VVI(MAX_C, MAX_C)
color = VVI(MAX_N, MAX_N)

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

for i in range(N):
  tmp_list = list(map(int, input().rstrip().split()))
  for j in range(N):
    color[i][j] = tmp_list[j]
    color[i][j] -= 1

table = VVI(3, MAX_C)

for i in range(N*N):
  x = i % N
  y = i // N
  c = color[y][x]
  for j in range(3):
    if (x+y+2)%3 == j:
      table[j][c] += 1

ans = int(1e9+7)

def dfs(s, diff):
  global ans
  if len(s) >= 3:
    ans = min(ans, diff)
    return

  for c in range(C):
    ddiff = diff
    ss = cp.deepcopy(s)
    if c in s:
      continue

    for i in range(C):
      ddiff += table[len(s)][i] * D[i][c]
    ss.add(c)
    dfs(ss , ddiff)

s = set([])

dfs(s, 0)

print(ans)

Submission status: Accepted

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

d = {i: [0]*c for i in range(3)}

for i in range(n):
    for j in range(n):
        d[(i+j)%3][int(cl[i][j])-1] += 1
cost = {i: [0]*c for i in range(3)}
for i in range(3):
    for j in range(c):
        for k in range(c):
            cost[i][j] += int(dl[k][j]) * d[i][k]
ans = float('inf')
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j !=k and k != i:
                ans = min(ans, cost[0][i]+cost[1][j]+cost[2][k])
print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())

    
    n, c = mi()
    color_cost = [lmi() for _ in range(c)]    # color x -> color y (0 to c-1 表現) にかかる擦ろtは color_cost[x][y]

    # color_cost = np.zeros((c, c), dtype="int16")
    # for i in range(c):
    #     tmp = lmi()
    #     for j in range(c):
    #         color_cost[i, j] = tmp[j]


    group = [[] for _ in range(3)]    # 0-index で i+j%3=0, 1, 2 となるやつら
    for i in range(n):
        tmp = lmi_0()    # color を 0 to c-1 表現に
        # print(tmp)
        for j in range(n):
            group[(i+j)%3].append(tmp[j])
    
    zero, one, two = group
    # O(n^2) で前処理
    zero_cnt, one_cnt, two_cnt = map(lambda x: Counter(x), group)

    ans = 10**15
    # O(30*29*28) (= O(2*10^4)) * O(C)
    for color_zero, color_one, color_two in permutations(range(c), r=3):
        cost = 0
        for col, v in zero_cnt.items():
            cost += v * color_cost[col][color_zero]
        for col, v in one_cnt.items():
            cost += v * color_cost[col][color_one]
        for col, v in two_cnt.items():
            cost += v * color_cost[col][color_two]
        ans = min(ans, cost)
    print(ans)



if __name__ == "__main__":
    main()

"""
O(10^7) だけど通らないっぽい <- 勘違い O(30*29*28* n) ではなく O(30*29*28* n * n) なので O(6*10^9)
辞書化の前処理で O(30*29*28 * c) = O(10**5) に
"""

Submission status: Accepted

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

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)]
    C = [0]*n
    for i, c_ in enumerate(C_):
        c_ = [x-1 for x in c_]
        C[i] = c_

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

    #print(C)
    import itertools
    ans = 10**18
    for p in itertools.permutations(range(c), 3):
        temp = 0
        for i in range(3):
            for j in range(c):
                temp += D[j][p[i]]*X[i][j]
        ans = min(ans, temp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

for i in range(N):
    for j in range(N):
        cnt[(i + j + 2) % 3][NM[i][j]] += 1

ans = 1 << 28
for i in range(1, C + 1):
    for j in range(1, C + 1):
        for k in range(1, C + 1):
            if i == j or j == k or i == k:
                continue
            c = 0
            for l in range(1, C + 1):
                c += cnt[0][l] * CM[l - 1][i - 1]
                c += cnt[1][l] * CM[l - 1][j - 1]
                c += cnt[2][l] * CM[l - 1][k - 1]
            ans = min(ans, c)

print(ans)

Submission status: Accepted

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

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

for i in range(N):
    for j in range(N):
        mod[(i+j+2)%3].append(c_field[i][j])

for i in range(3):
    mod[i] = Counter(mod[i])

def calc(p):
    ret = 0
    for j in range(3):
        for i, v in mod[j].items():
            if i == p[j]: continue
            ret += D[i-1][p[j]-1] * v
    return ret

ans = 10 ** 30
for p in permutations(range(1,C+1), 3):
    ans = min(ans, calc(p))

print(ans)

Submission status: Accepted

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

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

for i in range(N):
    for j in range(N):
        if (i+j+2) % 3 == 0:
            mod0.append(c_field[i][j])
        elif (i+j+1) % 3 == 1:
            mod1.append(c_field[i][j])
        else:
            mod2.append(c_field[i][j])

mod0 = Counter(mod0)
mod1 = Counter(mod1)
mod2 = Counter(mod2)

def calc(p):
    ret = 0
    for i, v in mod0.items():
        if i == p[0]: continue
        ret += D[i-1][p[0]-1] * v
    for i, v in mod1.items():
        if i == p[1]: continue
        ret += D[i-1][p[1]-1] * v
    for i, v in mod2.items():
        if i == p[2]: continue
        ret += D[i-1][p[2]-1] * v
    return ret
    

ans = 10 ** 30
for p in permutations(range(1,C+1), 3):
    ans = min(ans, calc(p))

print(ans)

Submission status: Accepted

Solution code:
import itertools


def main():
    N, C = list(map(int, input().split(' ')))
    D = [list(map(int, input().split(' '))) for _ in range(C)]
    grids = [list(map(lambda c: int(c) - 1, input().split(' '))) for _ in range(N)]
    color_counts = [[0 for _ in range(C)] for _ in range(3)]
    for i in range(N):
        for j in range(N):
            g = ((i + 1) + (j + 1)) % 3
            c = grids[i][j]
            color_counts[g][c] += 1
    min_d = 1000 * 500 * 500
    for dest_colors in itertools.permutations(range(C), 3):
        d = 0
        for g in range(3):
            for c in range(C):
                d += color_counts[g][c] * D[c][dest_colors[g]]
        min_d = min([min_d, d])
    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

color_counts = [[0]*(C+1) for i in range(3)]

for i in range(1,N+1):
    for j in range(1,N+1):
        color_counts[(i+j)%3][grid[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 and c1 != c2 and c2 != c0:
                total = 0
                for i in range(1,C+1):
                    total += discomforts[i][c0]*color_counts[0][i]
                    total += discomforts[i][c1]*color_counts[1][i]
                    total += discomforts[i][c2]*color_counts[2][i]
                ans = min(ans,total)
print(ans)

Submission status: Accepted

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

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)]
  A = [[0]*c for _ in range(3)]
  for i in range(n):
    for j in range(n):
      x = C[i][j] - 1
      r = (i+j)%3
      for y in range(c):
        A[r][y] += D[x][y]
  ans = float("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
        temp = A[0][i] + A[1][j] + A[2][k]
        ans = min(ans, temp)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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)]
    R = [[] for _ in range(3)]

    for i in range(N):
        for j in range(N):
            r = (i + 1) + (j + 1)
            if r % 3 == 0:
                R[0].append(c[i][j])
            elif r % 3 == 1:
                R[1].append(c[i][j])
            else:
                R[2].append(c[i][j])
    Diff = [[] for _ in range(3)]
    for i in range(3):
        l = len(R[i])

        for color in range(C):
            cnt = 0
            for j in range(l):
                cnt += D[R[i][j] - 1][color]
            Diff[i].append(cnt)
    answer = 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
                else:
                    ans = Diff[0][i] + Diff[1][j] + Diff[2][k]
                    if ans < answer:
                        answer = ans
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

memo = [[0 for i in range(C)]for j in range(3)]

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

ans = 250000001

for c1, c2, c3 in itertools.permutations(range(C), 3):
    ans = min(ans, memo[0][c1] + memo[1][c2] + memo[2][c3])

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

memo = [[0 for i in range(C)]for j in range(3)]

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

ans = float('inf')

for c1, c2, c3 in itertools.permutations(range(C), 3):
    ans = min(ans, memo[0][c1] + memo[1][c2] + memo[2][c3])

print(ans)

Submission status: Accepted

Solution code:
import itertools
n, cs = map(int, input().split())
d = [list(map(int, input().split())) for i in range(cs)]
c = [list(map(int, input().split())) for i in range(n)]
color_count = [[0] * cs for i in range(3)]
for i, j in itertools.product(range(n), repeat=2):
  color_count[(i + j) % 3][c[i][j] - 1] += 1
ans = 10**20
for t in itertools.permutations(range(cs), 3):
  s = 0
  for l in range(3):
    for m in range(cs):
      s += color_count[l][m] * d[m][t[l]]
  ans = min(ans, s)
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)]

col=[[0 for i in range(C+1)] for j in range(3)]

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

#print(col)

ans=10**15
import itertools
PRD=list(itertools.product([i for i in range(C)], repeat=3))

for i in range(len(PRD)):
    newc=[PRD[i][0],PRD[i][1],PRD[i][2]]
    if newc[0]==newc[1] or newc[1]==newc[2] or newc[2]==newc[0]:
        continue
    cost=0
    for j in range(3):
        for k in range(C):
            cost+=col[j][k+1]*D[k][newc[j]]
    ans=min(cost,ans)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import permutations
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,C=map(int,input().split())
    D=[tuple(map(int,input().split())) for _ in range(C)]
    c=[tuple(map(int1,input().split())) for _ in range(N)]
    l=[[0]*C for _ in range(3)]
    for i in range(N):
        for j in range(N):
            l[(i+j)%3][c[i][j]]+=1
    ans=INF
    for t in permutations(range(C),3):
        tmp=0
        for i in range(3):
            for j in range(C):
                tmp+=l[i][j]*D[j][t[i]]
        ans=min(ans,tmp)
    print(ans)

if __name__ == '__main__':
    main()

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

mod_0=defaultdict(int)
mod_1=defaultdict(int)
mod_2=defaultdict(int)

for i in range(N):
    for j in range(N):
        n=(i+j+2)%3
        if n==0:
            mod_0[grid[i][j]]+=1
        elif n==1:
            mod_1[grid[i][j]]+=1
        else:
            mod_2[grid[i][j]]+=1

ans=float("inf")
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

            total=0
            for prev,cnt in mod_0.items():
                total+=D[prev-1][i]*cnt
            for prev,cnt in mod_1.items():
                total+=D[prev-1][j]*cnt
            for prev,cnt in mod_2.items():
                total+=D[prev-1][k]*cnt
            
            ans=min(ans,total)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
a = [[] for _ in range(3)]
for i in range(n):
    for j, x in enumerate(map(lambda x: int(x)-1, input().split())):
        a[(i+j) % 3].append(x)

cnt = list(map(lambda x: Counter(x), a))
ans = float("inf")

for cp in permutations(range(c), 3):
    res = 0
    for i, x in enumerate(cp):
        for px in cnt[i].keys():
            res += d[px][x] * cnt[i][px]
    ans = min(res, ans)

print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict

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


# mod_x : (i+j)%3がxで、keyは色、valueは個数
mod_0 = defaultdict(int)
mod_1 = defaultdict(int)
mod_2 = defaultdict(int)


for i in range(N):
    for j in range(N):
        if (i+1 + j+1) % 3 == 0:
            mod_0[grid[i][j]] += 1
        elif (i+1 + j+1) % 3 == 1:
            mod_1[grid[i][j]] += 1
        elif (i+1 + j+1) % 3 == 2:
            mod_2[grid[i][j]] += 1

ans = float("inf")
# mod_0のマスにあるものをiに、mod_1のものをjに、mod_2のものをkに塗り替える
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

            total = 0
            for prev,cnt in mod_0.items():
                total += D[prev-1][i] * cnt
            for prev,cnt in mod_1.items():
                total += D[prev-1][j] * cnt
            for prev,cnt in mod_2.items():
                total += D[prev-1][k] * cnt

            ans = min(ans, total)

print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split()))for _ in range(c)]
cc=[list(map(int,input().split()))for _ in range(n)]
ans=10**15
cnt=[[0]*c for _ in range(3)]
for i in range(n):
	for j in range(n):
		cnt[(i+j)%3][cc[i][j]-1]+=1
for i in range(c):
	for j in range(c):
		for k in range(c):
			pre_ans=0
			if i==j or j==k or k==i:
				continue
			for l in range(3):
				for m in range(c):
					if l%3==0 and m!=i:
						pre_ans+=cnt[l][m]*d[m][i]
					elif l%3==1 and m!=j:
						pre_ans+=cnt[l][m]*d[m][j]
					elif l%3==2 and m!=k:
						pre_ans+=cnt[l][m]*d[m][k]
			ans=min(ans,pre_ans)
print(ans)

Submission status: Accepted

Solution code:
N,C=map(int, input().split())
D=[list(map(int, input().split())) for _ in range(C)]
c=[list(map(int, input().split())) for _ in range(N)]
C0=[0]*C
C1=[0]*C
C2=[0]*C
for i in range(N):
  for j in range(N):
    if (i+j)%3==0:
      C0[c[i][j]-1]+=1
    elif (i+j)%3==1:
      C1[c[i][j]-1]+=1
    else:
      C2[c[i][j]-1]+=1
      
import itertools
A=list(itertools.permutations(range(1,C+1),3))
ans=1000*250000
for a,b,c in A:
  d=0
  for i in range(C):
    d+=C0[i]*D[i][a-1]
    d+=C1[i]*D[i][b-1]
    d+=C2[i]*D[i][c-1]
  ans=min(ans,d)
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())))
    
A=[[0]*c for i in range(3)]
for i in range(n):
    for j in range(n):
        a=(i+j)%3
        A[a][C[i][j]-1]+=1

ans=10**100
for a0 in range(c):
    for a1 in range(c):
        for a2 in range(c):
            if a0==a1 or a1==a2 or a2==a0:
                continue
            cnt=0
            for i in range(c):
                cnt+=D[i][a0]*A[0][i]
                cnt+=D[i][a1]*A[1][i]
                cnt+=D[i][a2]*A[2][i]
            ans=min(cnt,ans)
print(ans)

Submission status: Accepted

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

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

for h, line in enumerate(C):
  for w, i in enumerate(line):
    CC[(h + w) % 3][i - 1] += 1
    
ans = 10 ** 19
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i != j and j != k and k != i:
        score = 0
        score += sum(D[itr][i] * val for itr, val in enumerate(CC[0]))
        score += sum(D[itr][j] * val for itr, val in enumerate(CC[1]))
        score += sum(D[itr][k] * val for itr, val in enumerate(CC[2]))
        ans = min(ans, score)

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

res=[[] for i in range(3)]
for mod in range(3):
    for color in range(C):
        dif=0
        for i in range(N):
            for j in range(N):
                if (i+j+2)%3==mod:
                    dif+=D[c[i][j]-1][color]
        res[mod].append([dif,color])
for i in range(3):
    res[i].sort()
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if((res[0][i][1]!=res[1][j][1])and(res[1][j][1]!=res[2][k][1])and(res[2][k][1]!=res[0][i][1])):
                ans=min(ans,res[0][i][0]+res[1][j][0]+res[2][k][0])
print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')
N, C = map(int, input().split())
D = list() #D[i][j]:=iからjに変える時の違和感
graph = list()
for i in range(C):
  D.append(list(map(int, input().split())))
for i in range(N):
  graph.append(list(map(int, input().split())))
E = [[0] * C for _ in range(3)] #E[i][j]:=mod3でiの場所を全て色jにしたときの違和感
for c in range(C):
  for x in range(N):
    for y in range(N):
      p = (x+y+2)%3
      cxy = graph[x][y]-1
      E[p][c] += D[cxy][c]
F = [[[INF]*2 for _ in range(3)] for _ in range(3)] 
#F[i][j][k]:=mod3でiの場所の違和感の最小値第j+1位。k=0色番号, k=1最小値]
for i in range(3):
  for j in range(C):
    if(E[i][j] < F[i][0][1]):
      F[i][2] = F[i][1]
      F[i][1] = F[i][0]
      F[i][0] = [j, E[i][j]]
    elif(E[i][j] < F[i][1][1]):
      F[i][2] = F[i][1]
      F[i][1] = [j, E[i][j]]
    elif(E[i][j] < F[i][2][1]):
      F[i][2] = [j, E[i][j]]
      
ans = INF
for i in range(3):
  for j in range(3):
    for k in range(3):
      c0 = F[0][i][0]
      c1 = F[1][j][0]
      c2 = F[2][k][0]
      if(c0 != c1 and c1 != c2 and c2 != c0):
        ans = min(ans, F[0][i][1]+F[1][j][1]+F[2][k][1])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc099/tasks
# 15:00-


def main():
    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[i] = [x-1 for x in c[i]]  # 0-index

    STU = [[0] * C, [0] * C, [0] * C]

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

    ans = 1000 * N * N
    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
                cand = STU[0][i] + STU[1][j] + STU[2][k]

                if cand < ans:
                    ans = cand

    return ans


print(main())

Submission status: Accepted

Solution code:
import itertools
n,c = map(int,input().split())
dij = [[int(i) for i in input().split()] for j in range(c)]
cij = [[int(i) for i in input().split()] for j in range(n)]

c0 = []
c1 = []
c2 = []


for i in range(1,c+1):
    c0_tmp = 0
    c1_tmp = 0
    c2_tmp = 0
    for j in range(n*n):
        c_num = cij[j//n][j%n]
        cnt = j//n + j % n + 2
        if cnt % 3 == 0:
            if c_num != i:
                #print(i,c_num,j)
                c0_tmp += dij[c_num-1][i-1]
        elif cnt % 3 == 1:
            if c_num != i:
                c1_tmp += dij[c_num-1][i-1]
            #c1.append(j+2)
        else:
            if c_num != i:
                c2_tmp += dij[c_num-1][i-1]
            #c2.append(j+2)
    c0.append(c0_tmp)
    c1.append(c1_tmp)
    c2.append(c2_tmp)
        
li = list(itertools.permutations(range(1, c+1),3))

ans = 10**18

for i in range(len(li)):
    tmp = 0
    #print(li[i])
    tmp += c0[li[i][0]-1]
    tmp += c1[li[i][1]-1]
    tmp += c2[li[i][2]-1]
    #print(tmp,i)
    #print(li[i][0])
    ans = min(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
INF = 10**18
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,C = LI()
D = [LI() for _ in range(C)]
p = [LI() for _ in range(N)]
q = [[0] * (C+1) for _ in range(3)]
for i in range(N):
    for j in range(N):
        k = (i + j) % 3
        q[k][p[i][j]] += 1

ans = INF
for col in itertools.permutations(range(1,C+1),3):
    iwa = 0
    for i in range(3):
        for j in range(1,C+1):
            iwa += D[j-1][col[i]-1] * q[i][j]
    ans = min(ans,iwa)
print (ans)