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:
N, C = map(int, input().split())

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

cc = [[0]*C for i in range(3)]
for i in range(N):
    color = list(map(int, input().split()))
    for j in range(len(color)):
        cc[(i+j)%3][color[j]-1] += 1
    
iwakan = [[[0, 0] for _ in range(C)] for _ in range(3)]

for i in range(3):
    for j in range(C):
        tmp = 0
        for k in range(len(cc[i])):
            tmp += cc[i][k]*D[k][j]
        iwakan[i][j][0] = tmp
        iwakan[i][j][1] = j

ans = 10**15
for i in range(len(iwakan)):
    iwakan[i] = sorted(iwakan[i], key=lambda x:x[0])
    
for i in range(3):
    for j in range(3):
        if(iwakan[0][i][1] == iwakan[1][j][1]):
            continue
        for k in range(3):
            if(iwakan[0][i][1] == iwakan[2][k][1]):
                continue
            if(iwakan[1][j][1] == iwakan[2][k][1]):
                continue
            ans = min(ans, iwakan[0][i][0]+iwakan[1][j][0]+iwakan[2][k][0])
            
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations

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

P = [defaultdict(int) for _ in range(3)]
for i in range(N):
    for j in range(N):
        P[(i+j)%3][c[i][j]-1] += 1

ans = float('inf')
for L in permutations([i for i in range(C)], 3):
    cnt = 0
    for i in range(3):
        for j in range(C):
            cnt += P[i][j] * D[j][L[i]]
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
  input = sys.stdin.readline
  n, c = map(int, input().split())
  d = [0 for _ in range(c)]
  for i in range(c):
    d[i] = [int(x) for x in input().split()]
  grid = [0 for _ in range(n)]
  for i in range(n):
    grid[i] = [int(x) for x in input().split()]
  
  k1, k2, k3 = [0]*c, [0]*c, [0]*c
  for i in range(n):
    for j in range(n):
      if (i+j)%3 == 1:
        k1[grid[i][j]-1] += 1
      elif (i+j)%3 == 2:
        k2[grid[i][j]-1] += 1
      else:
        k3[grid[i][j]-1] += 1
  
  key1, key2, key3 = [], [], []
  for i in range(c):
    sub1, sub2, sub3 = 0, 0, 0
    for j in range(c):
      if i == j:
        continue
      sub1 += k1[j]*d[j][i]
      sub2 += k2[j]*d[j][i]
      sub3 += k3[j]*d[j][i]
    key1.append([sub1, i])
    key2.append([sub2, i])
    key3.append([sub3, i])
  key1.sort()
  key2.sort()
  key3.sort()
  key1 = key1[:3]
  key2 = key2[:3]
  key3 = key3[:3]
  ans = pow(10, 9)
  for i in range(3):
    for j in range(3):
      for k in range(3):
        if key1[i][1] != key2[j][1] and key2[j][1] != key3[k][1] and key1[i][1] != key3[k][1]:
          if ans > key1[i][0]+key2[j][0]+key3[k][0]:
            ans = key1[i][0]+key2[j][0]+key3[k][0]
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import collections
N,C=map(int,input().split())
cost=[list(map(int,input().split())) for _ in range(C)]
table=[list(map(int,input().split())) for _ in range(N)]
l=[[] for _ in range(3)]
costs=[[] for _ in range(3)]

for i in range(N):
    for j in range(N):
        l[(i+j)%3].append(table[i][j])
#print(l)
c1=collections.Counter(l[0])
c2=collections.Counter(l[1])
c3=collections.Counter(l[2])
costs=[[] for _ in range(3)]
for i in range(C):
    for j in range(3):
        buf=0
        for k in l[j]:
            buf=buf+cost[k-1][i]
        costs[j].append(buf)
#print(costs)
mi=float("inf")
for i in range(C):
    for j in range(C):
        for k in range(C):
            if (i!=j)and(j!=k)and(i!=k):
                mi=min(mi,costs[0][i]+costs[1][j]+costs[2][k])
print(mi)

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

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

for i in range(N):
    for j in range(N):
        for to in range(C):
            delta[(i+j)%3][to] += D[c[i][j]-1][to]
ans = 1e100
for x,y,z in itertools.permutations(range(C),3):
    ans = min(ans, delta[0][x] + delta[1][y] + delta[2][z])
print(ans)

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

memo = [[0] * C for _ in range(3)]
for i in range(N):
    for j in range(N):
        k = (i + j + 2) % 3
        memo[k][X[i][j] - 1] += 1
        
ans = 10 ** 9 + 7
for c in permutations(range(C), 3):
    cost = 0
    for n in range(3):
        for j in range(C):
            cost += D[j][c[n]] * memo[n][j]
            
    ans = min(ans, cost)
    
print(ans)

Submission status: Accepted

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

ll = [[0]*c for i in range(3)]

for i in range(n):
    for j in range(n):
        x = (i+j+2)%3
        ll[x][l[i][j]-1] += 1

ans = float("INF")

for i in range(c):
    for j in range(c):
        if i == j:
            continue
        for k in range(c):
            if i == k or j == k:
                continue
            count = 0
            ch = [i,j,k]
            for m in range(3):
                for t in range(c):
                    count += ll[m][t]*d[t][ch[m]]
            ans = min(ans,count)
print(ans)

Submission status: Accepted

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

from itertools import combinations, permutations

def main():
  n, nc = map(int, input().split())
  md = [list(map(int, input().split())) for _ in range(nc)]
  mc = [list(map(lambda c: int(c)-1, input().split())) for _ in range(n)]
  cnt_c = [[0] * nc for _ in range(3)]
  
  for i in range(n):
    for j in range(n):
      cnt_c[(i + j) % 3][mc[i][j]] += 1
  
  def calc_cost(lx, itarget):
    return sum([cnt*md[i][itarget] for i, cnt in enumerate(lx)])
  
  cost = 10**9
  for inds in combinations(range(nc), 3):
    for itargets in permutations(inds):
      cost = min(cost, sum([calc_cost(cnt_c[i], itarget) for i, itarget in enumerate(itargets)]))
  print(cost)
    
      
  

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

# sum of wrongnesses to repaint i-th strip to color j. (i=0,1,2,  j=0,1,...,C-1)
sw = [[0] * C for _ in range(3)]

for i in range(N):
    for j in range(N):
        idc = c[i][j] - 1
        for _idc in range(C):
            sw[(i + j) % 3][_idc] += D[idc][_idc]

ans = 10**9
for p in permutations(range(C), 3):
    tmp = 0
    for idx, q in enumerate(p):
        tmp += sw[idx][q]

    if ans > tmp:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from itertools import permutations

def main():
    N,C = map(int,input().split())
    D = [list(map(int,input().split())) for _ in range(C)]
    col = [list(map(int,input().split())) for _ in range(N)]
    
    mod_color = [[0]*C,[0]*C,[0]*C]
    for i in range(N):
        for j in range(N):
            mod_color[(i+j)%3][col[i][j]-1] += 1

    ans = 10**10
    for x,y,z in permutations(range(C),3):
        ret = 0
        ret += sum(mod_color[0][i]*D[i][x] for i in range(C))
        ret += sum(mod_color[1][i]*D[i][y] for i in range(C))
        ret += sum(mod_color[2][i]*D[i][z] for i in range(C))
        ans = min(ans,ret)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 目指すグリッドは
# ABCABCABC..
# BCABCABCA..
# CABCABCAB..
# ABCABCABC..
# ...
# N = 500なので総マス数は250000
# 色の種類は30種類
# すべてのマスをあまりごとに3グループに分ける
# 各グループにおいて、各色が何マスずつあるかを計算する。250000回
# 長さ30の配列 * 3になるのであとは変更先の色をすべて試す。30 * 3回
# 隣あったマスを同じ色にすることができないため、
# グループごとに候補を3位まで用意し、3 * 3 * 3 = 27通りをすべて試す。
# 3位と4位がタイのときはどっちを取っても大丈夫

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

D = [[0]*C for i in range(C)] # 違和感
for i in range(C):
  D[i] = list(map(int,input().split())) # 色は0-indexで指定
  # D[i][j]で、iをjに変えるときの違和感を算出

# print(D)

groups = [[0]*C for i in range(3)]

for i in range(N):
  line = list(map(int,input().split()))
  for j in range(len(line)):
    groups[(i+j)%3][line[j] - 1] += 1

# groups[i(グループ名)][j(色 0-index)] = 該当する個数 が出来た。
# 各グループに対して、各色に塗り替えたときの違和感を計算する
pattern = [[[0]*2 for j in range(C)] for i in range(3)]
# pattern[i(グループ名)][j(色 0-index))] = 対象の色に塗り替えたときの違和感
# 30 * 30 = 900, 900 * 3 = 2700

for i in range(len(groups)):
  # グループごとのループ
  for j in range(C):
    # 変更後の色j
    iwakan = 0 # 色jに変えるときの違和感を累積
    for k in range(len(groups[i])):
      # グループiには色kがいくつあるか
      iwakan += groups[i][k] * D[k][j]
    pattern[i][j][0] = iwakan
    pattern[i][j][1] = j # あとで並び替えるため、何色に変えるかをメモしておく

for i in range(len(pattern)):
  pattern[i] = sorted(pattern[i],key = lambda x:x[0])

ans = 10 ** 9 + 7
for a in range(3): # グループ1が何位の数字を使うか
  for b in range(3): # 同2
    if pattern[0][a][1] == pattern[1][b][1]:
      continue
    for c in range(3): # 同3
      if pattern[0][a][1] == pattern[2][c][1]:
        continue
      if pattern[1][b][1] == pattern[2][c][1]:
        continue
      val = pattern[0][a][0] + pattern[1][b][0] + pattern[2][c][0]
      if val < ans:
        ans = val
print(ans)

Submission status: Accepted

Solution code:
# 目指すグリッドは
# ABCABCABC..
# BCABCABCA..
# CABCABCAB..
# ABCABCABC..
# ...
# N = 500なので総マス数は250000
# 色の種類は30種類
# すべてのマスをあまりごとに3グループに分ける
# 各グループにおいて、各色が何マスずつあるかを計算する。250000回
# 長さ30の配列 * 3になるのであとは変更先の色をすべて試す。30 * 3回
# 隣あったマスを同じ色にすることができないため、
# グループごとに候補を3位まで用意し、3 * 2 * 1は6通りをすべて試す。
# 3位と4位がタイのときはどっちを取っても大丈夫

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

D = [[0]*C for i in range(C)] # 違和感
for i in range(C):
  D[i] = list(map(int,input().split())) # 色は0-indexで指定
  # D[i][j]で、iをjに変えるときの違和感を算出

# print(D)

groups = [[0]*C for i in range(3)]

for i in range(N):
  line = list(map(int,input().split()))
  for j in range(len(line)):
    groups[(i+j)%3][line[j] - 1] += 1

# groups[i(グループ名)][j(色 0-index)] = 該当する個数 が出来た。
# 各グループに対して、各色に塗り替えたときの違和感を計算する
pattern = [[[0]*2 for j in range(C)] for i in range(3)]
# pattern[i(グループ名)][j(色 0-index))] = 対象の色に塗り替えたときの違和感
# 30 * 30 = 900, 900 * 3 = 2700

for i in range(len(groups)):
  # グループごとのループ
  for j in range(C):
    # 変更後の色j
    iwakan = 0 # 色jに変えるときの違和感を累積
    for k in range(len(groups[i])):
      # グループiには色kがいくつあるか
      iwakan += groups[i][k] * D[k][j]
    pattern[i][j][0] = iwakan
    pattern[i][j][1] = j # あとで並び替えるため、何色に変えるかをメモしておく

for i in range(len(pattern)):
#  print("bef",pattern[i])
  pattern[i] = sorted(pattern[i],key = lambda x:x[0])
#  print("after",pattern[i])

ans = 10 ** 9 + 7
for a in range(3): # グループ1が何位の数字を使うか
  for b in range(3): # 同2
    if pattern[0][a][1] == pattern[1][b][1]:
      continue
    for c in range(3): # 同3
      if pattern[0][a][1] == pattern[2][c][1]:
        continue
      if pattern[1][b][1] == pattern[2][c][1]:
        continue
      val = pattern[0][a][0] + pattern[1][b][0] + pattern[2][c][0]
      if val < ans:
        ans = val
print(ans)

Submission status: Accepted

Solution code:
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)]
D0 = {i: 0 for i in range(C)}
D1 = {i: 0 for i in range(C)}
D2 = {i: 0 for i in range(C)}
for i in range(N):
  for j in range(N):
    if (i+j) % 3 == 0:
      D0[grid[i][j]-1] += 1
    elif (i+j) % 3 == 1:
      D1[grid[i][j]-1] += 1
    elif (i+j) % 3 == 2:
      D2[grid[i][j]-1] += 1
m = int(1e11) + 23
for i in range(C):
  for j in range(C):
    for k in range(C):
      if i != j and j != k and k != i:
        differ = 0
        for l in range(C):
          differ += D0[l] * D[l][i]
          differ += D1[l] * D[l][j]
          differ += D2[l] * D[l][k]
        if m > differ:
          m = differ
print(m)

Submission status: Accepted

Solution code:
#ABC099-D Good Grid
"""
問題：
条件を満たすようにc色の色を塗り替える場合に生じるコスト(違和感)
を最小化する。
条件：
ある任意の２箇所のグリッド grid[a][b]とgrid[c][d]を見た時に、
(a+b)%3 == (c+d)%3 ならば、その２箇所は同じ色である必要があり、
そうでない場合は違う色である必要がある。
6*6のグラフで見るとこんな感じになる
012012
120120
201201
012012
120120
201201 

解法：
色が30色であるという制約から、
30C3通りを試した時のコストの最小値が答えになる。
500*500のgridで高速に計算する必要があるため、
予めdictを用いて3で割った余りが0,1,2の場所に何の色が何個入っているか
を求めておき、あとはそれぞれの場所から変更先の色へのコストを求めれば
良い。
"""
import sys
from collections import defaultdict
import itertools
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,c = map(int,readline().split()) #N*Nの正方行列,c色
D = [] #隣接リスト(ある色iから色jに塗り替えた時の違和感D[i][j])
#ちなみに、塗り替えなかった場合違和感は0になる
for i in range(c):
    D.append(list(map(int,readline().split())))

grid = [] #元の色のグリッド(1-indexed)
for i in range(n):
    grid.append(list(map(int,readline().split())))



dic_0 = defaultdict(int)
dic_1 = defaultdict(int)
dic_2 = defaultdict(int)

for i in range(n):
    for j in range(n):
        if (i+j)%3 == 0:
            dic_0[grid[i][j]] += 1
        elif (i+j)%3 == 1:
            dic_1[grid[i][j]] += 1
        else:
            dic_2[grid[i][j]] += 1

colors = [i for i in range(1,c+1)]
ans = 10**9
for i,j,k in itertools.combinations(colors,3):
    for o,p,q in itertools.permutations([i,j,k]):
        res = 0
        for a,b in dic_0.items():
            res += D[a-1][o-1]*b
        for a,b in dic_1.items():
            res += D[a-1][p-1]*b
        for a,b in dic_2.items():
            res += D[a-1][q-1]*b

        ans = min(ans,res)

print(ans)

Submission status: Accepted

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

a = [[0]*c for _ in range(3)]
b = [[[0,i] for i in range(c)] for _ in range(3)]

for i in range(n):
  l = list(map(int,input().split()))
  for j in range(n):
    a[(i+j)%3][l[j]-1] += 1
    
for i in range(3):
  for k in range(c):
    b[i][k][0] = sum([a[i][t]*d[t][k] for t in range(c)])
p = [[],[],[]]
for i in range(3):
  p[i] = sorted(b[i])[:3]
m = []
for t in p[0]:
  for s in p[1]:
    for u in p[2]:
      if (t[1] != s[1]) and (t[1] != u[1]) and (s[1] != u[1]):
        m.append(t[0]+s[0]+u[0])
print(min(m))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    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)]
    # 各余りのマスのグループをi番目の色に変えた時の違和感の総和
    iwakan = [[0]*C for _ in range(3)]

    for i in range(N):
        for j in range(N):
            amari = (i+j+2) % 3
            color = c[i][j]
            for k in range(C):
                iwakan[amari][k] += d[color-1][k]
    
    res = 10**20
    for i in permutations(range(C), 3):
        res = min(res, iwakan[0][i[0]]+iwakan[1][i[1]]+iwakan[2][i[2]])
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(c)]
lc = [[int(i)-1 for i in input().split()] for _ in range(n)]

ans = float("inf")

dp = [[0] * c for i in range(3)]
for C in range(c):
  for y in range(n):
    for x in range(n):
      if lc[y][x] != c:
        dp[(y+x)%3][C] += d[lc[y][x]][C]
for c0 in range(c):
  for c1 in range(c):
    if c0 == c1: continue
    for c2 in range(c):
      if c0 == c2 or c1 == c2: continue
      ans = min(ans, dp[0][c0] + dp[1][c1] + dp[2][c2])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, C = map(int, input().split())
    D = []
    for _ in range(C):
        d = list(map(int, input().split()))
        D.append(d)
    c = []
    for _ in range(N):
        cc = list(map(int, input().split()))
        c.append(cc)
    l = [[0] * (C+1) for _ in range(3)]
    for i in range(N):
        for j in range(N):
            l[(i + j) % 3][c[i][j]] += 1
    m = pow(10, 10000)
    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 i == k or j == k:
                    continue
                t = 0
                for ii in range(1, C+1):
                    t += l[0][ii] * D[ii-1][i-1]
                for jj in range(1, C+1):
                    t += l[1][jj] * D[jj-1][j-1]
                for kk in range(1, C+1):
                    t += l[2][kk] * D[kk-1][k-1]
                m = min(m, t)
    print(m)
main()

Submission status: Accepted

Solution code:
from itertools import product, permutations

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)]
    T = [[0] * C for _ in range(3)]
    for x, y in product(range(N), repeat=2):
        r = (x + y) % 3
        for i in range(C):
            T[r][i] += D[c[x][y] - 1][i]
    Q = []
    for j in range(3):
        Q.append(sorted((t, i) for i, t in enumerate(T[j])))
    m = 10**10
    for x, y, z in product(range(3), repeat=3):
        X, Y, Z = Q[0][x], Q[1][y], Q[2][z]
        if X[1] == Y[1] or Y[1] == Z[1] or Z[1] == X[1]:
            continue
        m = min(m, X[0] + Y[0] + Z[0])
    return m


print(main())

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

co = [Counter() for i in range(3)]
for i in range(n):
    C = list(map(int,input().split()))
    for j in range(n):
        co[(i+j)%3][C[j]-1] +=1
ans = 10**15
perm = permutations([i for i in range(c)],3)

for t in perm:
    temp = 0
    for i in range(3):
        color = t[i]
        for num,cnt in co[i].items():
            temp += D[num][color] * cnt
    ans = min(temp,ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from itertools import permutations

    N, C = map(int, input().split())
    change_cost = [[int(x) for x in input().split()] for _ in range(C)]
    init_color = [[int(x) - 1 for x in input().split()] for _ in range(N)]

    ctr = [[0] * C for _ in range(3)]
    for r in range(N):
        for c in range(N):
            p = (r + c) % 3
            color = init_color[r][c]
            ctr[p][color] += 1

    mi = 1000 * 500 * 500 + 1
    for perm in permutations(range(C), r=3):
        it = iter(perm)
        t = 0
        for p in range(3):
            color_to_be = next(it)
            for color, count in enumerate(ctr[p]):
                t += change_cost[color][color_to_be] * count
        mi = min(mi, t)
    print(mi)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import permutations

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

    sup0 = [0] * C
    sup1 = [0] * C
    sup2 = [0] * C
    for i in range(N):
        for j in range(N):
            if (i + j) % 3 == 0:
                sup2[grid[i][j] - 1] += 1
            elif (i + j) % 3 == 1:
                sup0[grid[i][j] - 1] += 1
            elif (i + j) % 3 == 2:
                sup1[grid[i][j] - 1] += 1

    ans = 10 ** 18
    for i, j, k in permutations(range(C), 3):
        tmp = 0
        for c in range(C):
            tmp += D[c][i] * sup0[c]
            tmp += D[c][j] * sup1[c]
            tmp += D[c][k] * sup2[c]
        ans = min(ans, tmp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

a = []
b = []

for _ in range(c):
    array = list(map(int, input().split()))
    a.append(array)

for _ in range(n):
    array = list(map(int, input().split()))
    b.append(array)


group1 = []
group2 = []
group3 = []

for i in range(n):
    for j in range(n):
        if (i + j) % 3 == 0:
            group1.append(b[i][j])
        elif (i + j) % 3 == 1:
            group2.append(b[i][j])
        else:
            group3.append(b[i][j])

g1 = Counter(group1)
g2 = Counter(group2)
g3 = Counter(group3)

sum1 = []
sum2 = []
sum3 = []


def cal(l, output):
    for i in range(c):
        s = 0
        for j in l.items():
            s += a[j[0]-1][i-1] * j[1]
        output.append(s)


li = [g1, g2, g3]
li2 = [sum1, sum2, sum3]

for i in range(3):
    cal(li[i], li2[i])

cc = list(range(c))

min_sum = 10**10
for i, j, k in permutations(cc, 3):
    sum = sum1[i] + sum2[j] + sum3[k]
    if sum < min_sum:
        min_sum = sum

print(min_sum)

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline
N, C = map(int, input().split())

D = [tuple(map(int, input().split())) for _ in [0]*C]
K = [tuple(map(int, input().split())) for _ in [0]*N]

T = [[0]*C for _ in [0]*3]

for i, _k in enumerate(K):
    for j, k in enumerate(_k):
        z = (i+j) % 3
        T[z][k-1] += 1

ans = float('inf')
for a, b, c in permutations(range(C), 3):
    cost = 0
    cost += sum(t*D[i][a] for i, t in enumerate(T[0]))
    cost += sum(t*D[i][b] for i, t in enumerate(T[1]))
    cost += sum(t*D[i][c] for i, t in enumerate(T[2]))
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
# # coding: utf-8
# # Your code here!

# //解説
# #include <iostream>
# #define rep(i,n) for(int i=0;i<n;i++)
# using namespace std;
# int N,C,X;
# int D[33][33];
# int t[3][33];
# int main(void)
# {
#     scanf("%d%d",&N,&C);
#     rep(i,C)rep(j,C)scanf("%d",&D[i][j]);
#     rep(i,N)rep(j,N)scanf("%d",&X),t[(i+j)%3][X-1]++;
#     int res=1<<30;
#     rep(i,C)rep(j,C)if(i!=j)rep(k,C)if(i!=k&&j!=k)
#     {
#         int tt=0;
#         rep(l,C)tt+=D[l][i]*t[0][l];
#         rep(l,C)tt+=D[l][j]*t[1][l];
#         rep(l,C)tt+=D[l][k]*t[2][l];
#         if(tt<res)res=tt;
#     }
#     printf("%d\n",res);
# }


from collections import defaultdict
N,C=map(int,input().split())
D=defaultdict(int)
t=defaultdict(int)

for i in range(C):
    s=list(map(int,input().split()))
    for j in range(C):
        D[(i,j)]=s[j]
for i in range(N):
    s=list(map(int,input().split()))
    for j in range(N):
        t[((i+j)%3,s[j]-1)]+=1
ans=1<<30
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i!=j!=k!=i:
                res=0
                for l in range(C):res+=D[(l,i)]*t[(0,l)]
                for l in range(C):res+=D[(l,j)]*t[(1,l)]
                for l in range(C):res+=D[(l,k)]*t[(2,l)]
                ans=min(ans,res)

                
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,c = map(int,input().split())
d = [0]
for i in range(c):
    d.append([0] + list(map(int,input().split())))
li0 = []
li1 = []
li2 = []
for i in range(n):
    g = list(map(int,input().split()))
    for j in range(n):
        if (i + j) % 3 == 0:
            li0.append(g[j])
        if (i + j) % 3 == 1:
            li1.append(g[j])
        if (i + j) % 3 == 2:
            li2.append(g[j])
dic0 = defaultdict(int)
dic1 = defaultdict(int)
dic2 = defaultdict(int)
for i in li0:
    dic0[i] += 1
for i in li1:
    dic1[i] += 1
for i in li2:
    dic2[i] += 1 
ans = 1000000000
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
            x = 0
            for color in range(1,c+1):
                x += dic0[color] * d[color][i]
                x += dic1[color] * d[color][j]
                x += dic2[color] * d[color][k]
            ans = min(x,ans) 
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations


def main():
    n, c = map(int, input().split())
    d = [[int(x) for x in input().split()] for _ in range(c)]
    g = [[int(x) - 1 for x in input().split()] for _ in range(n)]
    count = [{}, {}, {}]
    for i in range(n):
        for j in range(n):
            now = g[i][j]
            index = (i + j + 2) % 3
            if now in count[index % 3]:
                count[index % 3][now] += 1
            else:
                count[index % 3][now] = 1
    answer = float("inf")
    for color in permutations([i for i in range(c)], 3):
        now_answer = 0
        for i in range(3):
            for before_color, num in count[i].items():
                now_answer += d[before_color][color[i]] * num
        answer = min(answer, now_answer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve():
    ans0 = []
    ans1 = []
    ans2 = []
    for col in range(1, c_cnt + 1):
        res = 0
        for i in range(n):
            for j in range(n):
                if (i + j) % 3 == 0:
                    res += d[c[i][j] - 1][col - 1]
        ans0.append(res)

    for col in range(1, c_cnt + 1):
        res = 0
        for i in range(n):
            for j in range(n):
                if (i + j) % 3 == 1:
                    res += d[c[i][j] - 1][col - 1]
        ans1.append(res)

    for col in range(1, c_cnt + 1):
        res = 0
        for i in range(n):
            for j in range(n):
                if (i + j) % 3 == 2:
                    res += d[c[i][j] - 1][col - 1]
        ans2.append(res)
        
    return ans0, ans1, ans2

res = 10 ** 18
ans0, ans1, ans2 = solve()
for i0, num0 in enumerate(ans0):
    for i1, num1 in enumerate(ans1): 
        for i2, num2 in enumerate(ans2):
            if i0 != i1 and i1 != i2 and i2 != i0:
                res = min(num0 + num1 + num2, res)
print(res)

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

cst = [[0,0,0] for i in range(C)]

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

ans = 10**10

for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or i == k or j == k:
                continue
            x = [i,j,k]
            a = 0
            for l in range(3):
                for m in range(C):
                    a += D[m][x[l]]*cst[m][l]
            ans = min(ans,a)

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
import itertools

input = sys.stdin.readline


def main():
    N, C = [int(x) for x in 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)]

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

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

    one = collections.Counter(A[0])
    two = collections.Counter(A[1])
    three = collections.Counter(A[2])

    ans = float("inf")
    for x, y, z in itertools.permutations(range(C), 3):
        tmp = 0
        for k in one.keys():
            tmp += D[k - 1][x] * one[k]
        for k in two.keys():
            tmp += D[k - 1][y] * two[k]
        for k in three.keys():
            tmp += D[k - 1][z] * three[k]

        ans = min(ans, tmp)

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

counter = [[0 for i in range(cc)] for j in range(3)]
for i in range(n):
    for j in range(n):
        counter[(i+j)%3][c[i][j]-1] += 1

m = 250000000
for y in itertools.permutations(range(cc), 3):
    new = 0
    for i in range(3):
        for x in range(cc):
            new += counter[i][x-1]*d[x-1][y[i]]
    m = min(m, new)

print(m)

Submission status: Accepted

Solution code:

from itertools import permutations


def submit():
    n, c = map(int, input().split())
    d = [list(map(int, input().split())) for _ in range(c)]    
    color = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    color_cnt = {i: {cl: 0 for cl in range(c)} for i in range(3)}

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

    ans = float('inf')
    for c0, c1, c2 in permutations(range(c), 3):
        t = 0
        for cl in range(c):
            t += color_cnt[0][cl] * d[cl][c0]
            t += color_cnt[1][cl] * d[cl][c1]
            t += color_cnt[2][cl] * d[cl][c2]
        if t < ans:
            ans = t
    print(ans)


submit()

Submission status: Accepted

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

counts = [defaultdict(int) for _ in range(3)]
for i in range(n):
    for j in range(n):
        counts[(i+j+2) % 3][c[i][j]-1] += 1

def calc_cost(dic, color):
    cost = 0
    for k, v in dic.items():
        cost += d[k][color] * v
    return cost

INF = 10**9
cost = INF
for colors in permutations(range(C), 3):
    tmp_cost = 0
    for i in range(3):
        tmp_cost += calc_cost(counts[i], colors[i])
    cost = min(cost, tmp_cost)
print(cost)