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 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 = [list(map(lambda s: int(s) - 1, input().split())) for i in range(N)]

d = [Counter(sum([c[j][(i - j) % 3::3] for j in range(N)], []))
     for i in range(3)]
ans = 1000000007
for t in permutations(range(C), 3):
    dis = 0
    for i in range(3):
        for k, v in d[i].items():
            dis += D[k][t[i]] * v
    ans = min(dis, ans)
print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
d = [lr() for i in range(k)]
c = [lr() for i in range(n)]
ans = [0 for i in range(3)]
pre = inf
fir = []
sec = []
thr = []
firkouho = []
seckouho = []
thrkouho = []
for y in range(n):
    for x in range(n):
        if (y + x) % 3 == 0:
            fir.append(c[y][x]-1)
        elif (y + x) % 3 == 1:
            sec.append(c[y][x]-1)
        else:
            thr.append(c[y][x] - 1)

for i in range(k):
    ans[0] = 0
    for ind in fir:
        ans[0] += d[ind][i]
    firkouho.append([ans[0], i])

for i in range(k):
    ans[1] = 0
    for ind in sec:
        ans[1] += d[ind][i]
    seckouho.append([ans[1], i])

for i in range(k):
    ans[2] = 0
    for ind in thr:
        ans[2] += d[ind][i]
    thrkouho.append([ans[2], i])

firkouho.sort()
seckouho.sort()
thrkouho.sort()

for i in range(k):
    ans[0] = 0
    ans[0],ind1 = firkouho[i]
    for j in range(k):
        if seckouho[j][1] != ind1:
            ans[1] = 0
            ans[1],ind2 = seckouho[j]
            for l in range(k):
                if thrkouho[l][1] != ind1 and thrkouho[l][1] != ind2:
                    ans[2] = 0
                    ans[2],ind3 = thrkouho[l]
                    pre = min(pre,sum(ans))
print(pre)

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

#グリッド座標を3種類に分ける
rem = [[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        rem[(i+j+2)%3].append(c[i][j])
# print(rem)

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

for i in range(3):
    for s in range(C):
        tmp = 0
        for t in rem[i]:
            tmp += D[t-1][s]
        cost[i].append((tmp, s+1))

for i in cost:
    i.sort()
    i = i[:3]
 
ans = 1e10
for i in cost[0]:
    for j in cost[1]:
        for h in cost[2]:
            if i[1] != j[1] and j[1] != h[1] and h[1] != i[1]:
                ans = min(ans,i[0]+j[0]+h[0])
print(ans)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
g0 = [0]*C
g1 = [0]*C
g2 = [0]*C
for i in range(N):
    col = list(map(int,input().split()))
    for j in range(N):
        col[j] -= 1
        if (i+j)%3==0:
            g0[col[j]] += 1
        elif (i+j)%3 ==1:
            g1[col[j]] += 1
        else:
            g2[col[j]] += 1
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 i==k:
                continue
            s=0
            for l in range(C):
                s += d[l][i]*g0[l] + d[l][j]*g1[l] + d[l][k]*g2[l]
            ans = min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

rem = [[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        rem[(i+j+2)%3].append(c[i][j])

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

for i in range(3):
    for s in range(C):
        tmp = 0
        for t in rem[i]:
            tmp += D[t-1][s]
        cost[i].append((tmp,s+1))

for i in cost:
    i.sort()
    i = i[:3]

ans = 1e10
for i in cost[0]:
    for j in cost[1]:
        for h in cost[2]:
            if i[1] != j[1] and j[1] != h[1] and h[1] != i[1]:
                ans = min(ans,i[0]+j[0]+h[0])
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(C)]
G = [list(map(int,input().split())) for _ in range(N)]
Z = [0]*C
O = [0]*C
T = [0]*C
for x in range(N):
    for y in range(N):
        if (x+y)%3 == 0:
            Z[G[x][y]-1] += 1
        elif (x+y)%3 == 1:
            O[G[x][y]-1] += 1
        else:
            T[G[x][y]-1] += 1

ans = 10**9
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
            temp = 0
            for k in range(C):
                temp += Z[k]*D[k][c1]
            for k in range(C):
                temp += O[k]*D[k][c2]
            for k in range(C):
                temp += T[k]*D[k][c3]
            ans = min(ans,temp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

n, c = map(int, input().split())
d = []
for i in range(c):
    di = list(map(int, input().split()))
    d.append(di)
dic0 = {}
dic1 = {}
dic2 = {}
for i in range(1, n+1):
    ci = list(map(int, input().split()))
    for j in range(n):
        cj = ci[j]
        if (i+j+1)%3 == 0:
            if cj in dic0:
                dic0[cj] += 1
            else:
                dic0[cj] = 1
        elif (i+j+1)%3 == 1:
            if cj in dic1:
                dic1[cj] += 1
            else:
                dic1[cj] = 1
        else:
            if cj in dic2:
                dic2[cj] += 1
            else:
                dic2[cj] = 1

ans = 10**9
for c0, c1, c2 in itertools.permutations(list(range(1, c+1)), 3):
    temp = 0
    for key in dic0.keys():
        if key != c0:
            temp += d[key-1][c0-1] * dic0[key]
    for key in dic1.keys():
        if key != c1:
            temp += d[key-1][c1-1] * dic1[key]
    for key in dic2.keys():
        if key != c2:
            temp += d[key-1][c2-1] * dic2[key]
    ans = min(ans, temp)
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)]

for i, l in enumerate(C):
    l = [x-1 for x in l]
    C[i] = l

import itertools
ans = 10**18

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


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

Submission status: Accepted

Solution code:
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())))
colors = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        colors[(i+j)%3][c[i][j]-1] += 1
ans = 10**10
for i in range(C):
    for j in range(C):
        if i==j:
            continue
        for k in range(C):
            if j==k or k==i:
                continue
            tmp = 0
            for l in range(C):
                tmp += colors[0][l]*D[l][i]
                tmp += colors[1][l]*D[l][j]
                tmp += colors[2][l]*D[l][k]
            ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

# 3色を保持するための変数
g0=[0]*C # 斜め列1
g1=[0]*C # 斜め列2
g2=[0]*C # 斜め列3

# 以下のような斜めごとに列を3色に分けようとしたときの違和感(コスト)を考える
# □ ○ △ □
# ○ △ □ ○
# △ □ ○ △
# □ ○ △ □

for i in range(N):
    col=list(map(int,input().split()))
    # 各マスの各色を見ていく
    #   斜めの列3種類ごとに持つ色を保持しておく
    for j in range(N):
        col[j]-=1
        if (i+j)%3==0:
            g0[col[j]]+=1
        elif (i+j)%3==1:
            g1[col[j]]+=1
        else:
            g2[col[j]]+=1

ans=float('inf')
# 全探索して、何色に変えるのが最もコストが低いかを出す
for i in range(C): # g0の色(をiにした場合)
    for j in range(C): # g1の色(をjにした場合)
        for k in range(C): # g2の色(をkにした場合)
            if i==j or j==k or i==k: # g0とg1が同じ色になる、みたいなパターンはないのでその場合の色分けは考えなくて良いので飛ばす
                continue
            s=0
            for l in range(C):
                # d[l][i]*g0[l]: lの色をiに変えるのに必要なコストの合計
                #  lをiに変えるコスト * g0にあるlの色の数
                #  d[l][j], d[l][k]も同様の計算
                #    l(全色)を特定のiやjに変えたときのコストの合計を算出
                s+=d[l][i]*g0[l]+d[l][j]*g1[l]+d[l][k]*g2[l]
            ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, Cnum = list(map(int, input().split()))
    D = [list(map(int, input().split())) for _ in range(Cnum)]
    C = [list(map(int, input().split())) for _ in range(N)]
    color_count = [{}, {}, {}]
    for i in range(N):
        for j in range(N):
            group = (i+j)%3
            d = color_count[group]
            if C[i][j]-1 in d:
                d[C[i][j]-1] += 1
            else:
                d[C[i][j]-1] = 1
    
    ans = float("inf")
    import itertools
    for pattern in itertools.permutations(list(range(0, Cnum)), 3):
        total = 0
        for i, after in enumerate(pattern):
            for color, count in color_count[i].items():
                total += count*D[color][after]
        ans = min(ans, total)
    print(ans)

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(c)]
g0=[0]*c
g1=[0]*c
g2=[0]*c
for i in range(n):
    col=list(map(int,input().split()))
    for j in range(n):
        col[j]-=1
        if (i+j)%3==0:
            g0[col[j]]+=1
        elif (i+j)%3==1:
            g1[col[j]]+=1
        else:
            g2[col[j]]+=1
ans=10**18
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i==j or j==k or i==k:
                continue
            s=0
            for l in range(c):
                s+=d[l][i]*g0[l]+d[l][j]*g1[l]+d[l][k]*g2[l]
            ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n, c = map(int, readline().split())
    cost = [list(map(int, readline().split())) for _ in range(c)]
    color = [list(map(int, readline().split())) for _ in range(n)]

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

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

    from itertools import permutations

    ans = INF

    for after in permutations(range(1, c + 1), 3):
        score = 0
        for gn, counter in enumerate(group):
            for key, val in counter.items():
                score += val * cost[key - 1][after[gn] - 1]
        ans = min(score, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# リファクタ
from collections import defaultdict
import itertools
n, c = map(int, input().split())
D = [list(map(int, input().split()))for _ in range(c)]

# 集計
diago = [defaultdict(int)for _ in range(3)]
for i in range(n):
    for j, color in enumerate(map(int, input().split())):
        diago[(i+j) % 3][color-1] += 1

# 0列目をcにするときのcにするときの最小コスト
costs = [[0]*c for _ in range(3)]
for i in range(3):
    for j in range(c):
        for k, v in diago[i].items():
            costs[i][j] += D[k][j]*v

INF = 10**18
ans = INF
for trio in itertools.combinations(range(c), 3):
    for color in itertools.permutations(trio, 3):
        cost = sum(costs[i][j] for i, j in enumerate(color))
        if cost < ans:
            ans = cost
print(ans)

Submission status: Accepted

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

# 集計
diago = [defaultdict(int)for _ in range(3)]
for i in range(n):
    for j, color in enumerate(map(int, input().split())):
        color -= 1
        if (i+j) % 3 == 0:
            diago[0][color] += 1
        elif (i+j) % 3 == 1:
            diago[1][color] += 1
        else:
            diago[2][color] += 1


# 0列目をcにするときのcにするときの最小コスト
costs = [[0]*c for _ in range(3)]
for i in range(3):
    for j in range(c):
        for k, v in diago[i].items():
            costs[i][j] += D[k][j]*v

INF = 10**18
ans = INF
for trio in itertools.combinations(range(c), 3):
    for color in itertools.permutations(trio, 3):
        cost = sum(costs[i][j] for i, j in enumerate(color))
        if cost < ans:
            ans = cost
print(ans)

Submission status: Accepted

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


# 色は0始まりで管理する

# 入力の色を受け取って、それぞれの色毎にいくつあるか
diago0 = defaultdict(int)
diago1 = defaultdict(int)
diago2 = defaultdict(int)

for i in range(n):
    for j, color in enumerate(map(int, input().split())):
        color -= 1
        if (i+j) % 3 == 0:
            diago0[color] += 1
        elif (i+j) % 3 == 1:
            diago1[color] += 1
        else:
            diago2[color] += 1


# 0列目をcにするときのcにするときの最小コスト
cost0 = [0]*c
cost1 = [0]*c
cost2 = [0]*c

for i in range(c):
    for k, v in diago0.items():
        cost0[i] += D[k][i]*v
for i in range(c):
    for k, v in diago1.items():
        cost1[i] += D[k][i]*v
for i in range(c):
    for k, v in diago2.items():
        cost2[i] += D[k][i]*v

INF = 10**18
ans = INF
for trio in itertools.combinations(range(c), 3):
    for a, b, c in itertools.permutations(trio, 3):
        cost = cost0[a]+cost1[b]+cost2[c]
        if cost < ans:
            ans = cost
print(ans)

Submission status: Accepted

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

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

ans = 500*500*1000
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
      now = 0
      for ci in range(C):
        now += D[ci][i] * cs[0][ci]
        now += D[ci][j] * cs[1][ci]
        now += D[ci][k] * cs[2][ci]
          
      ans = min(ans, now)
      
print(ans)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from itertools import permutations

#import numpy as np

def main():
	n,c=MI()
	D=[[0]*(c+1)]
	for _ in range(c):
		D.append([0]+LI())
	#print(D)
	
	C=[[0]*(n+1)]
	for _ in range(n):
		C.append([0]+LI())
	#print(C)
	
	li=[[0]*(c+1) for _ in range(3)]
	for i in range(1,n+1):
		for j in range(1,n+1):
			li[(i+j)%3][C[i][j]]+=1
	#print(li)
	
	ans=10**10
	
	for ii in permutations(range(1,c+1),3):
		ret=0
		#print(ii)
		for a in range(3):
			for b in range(1,c+1):
				#print(li[a][b],D[b][ii[a]])
				ret+=li[a][b]*D[b][ii[a]]
		#print(ans,ret)
		ans=min(ans,ret)
	print(ans)
	
	
	
	
	
	
	

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,max_c=map(int,readline().split())
    d=[list(map(int,readline().split())) for _ in range(max_c)]
    d=np.array(d,dtype=np.int64)
    c=[list(map(lambda x:int(x)-1,readline().split())) for _ in range(n)]

    #前処理
    color_table=np.zeros((3,max_c),dtype=np.int64)
    for i in range(n):
        for j in range(n):
            color_table[(i+j+2)%3,:]+=d[c[i][j],:]

    #全探索
    ans=float("inf")
    for i in range(max_c):
        for j in range(max_c):
            for k in range(max_c):
                if i==j or j==k or k==i:
                    continue
                ans=min(ans,color_table[0][i]+color_table[1][j]+color_table[2][k])

    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

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


m0 = Counter()
c0 = 0
m1 = Counter()
c1 = 0
m2 = Counter()
c2 = 0
for i in range(N):
    for j in range(N):
        if ((i+1)+(j+1)) % 3 == 0:
            m0[c[i][j]] += 1
            c0 += 1
        elif ((i+1)+(j+1)) % 3 == 1:
            m1[c[i][j]] += 1
            c1 += 1
        else:
            m2[c[i][j]] += 1
            c2 += 1

m = [m0, m1, m2]
cnt = [c0, c1, c2]

ans = float('inf')
for perm in itertools.permutations([i for i in range(1, C+1)], 3):
    tmp = 0
    for i in range(3):
        for k, v in m[i].items():
            if k != perm[i]:
                tmp += D[k-1][perm[i]-1] * v
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools


def calc(colo, target, d_mtx):
    ret = 0
    for i, item in enumerate(colo):
        ret += item * d_mtx[i][target]
    return ret


n, c = map(int, input().split())
d_mtx = []
c_mtx = []

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

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

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

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

ret = 10 ** 10
for item in itertools.permutations(range(c), 3):
    tmp = 0
    for i in range(3):
        tmp += calc(color[i], item[i], d_mtx)
    ret = min(ret, tmp)

print(ret)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
# 入力の C は M とする
N,M = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(N)]

# X[x][y] : (i+j)%3 == x の, 初期状態での色が y(0-indexed) のマスの数
X = [[0 for _ in range(M)] for _ in range(3)]
for i in range(N):
    for j in range(N):
        x = (i+1 + j+1)%3
        y = C[i][j] - 1
        X[x][y] += 1

# Y[x][y] : (i+j)%3 == x の領域を y で塗る場合に必要なコスト
Y = [[0 for _ in range(M)] for _ in range(3)]
for i in range(3):
    for c_to in range(M):
        total = 0
        for c_from in range(M):
            total += X[i][c_from] * D[c_from][c_to]
        Y[i][c_to] = total

ans = 10**10
# 塗る色の組み合わせで全探索
for i in range(M):
    for j in range(M):
        for k in range(M):
            # 全ての色が異なる場合のみ考える
            if i != j and j != k and k != i:
                ans = min(ans, Y[0][i] +Y[1][j] + Y[2][k] )

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np
from itertools import permutations

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, C = lr()
feeling = np.array([lr() for _ in range(C)])
Cij = [lr() for _ in range(N)]
three = [[0] * C for _ in range(3)]
for i in range(N):
    for j in range(N):
        remain = (i+j) % 3
        num = Cij[i][j] - 1
        three[remain][num] += 1

three = np.array(three)
answer = 10 ** 10
for X in permutations(range(C), 3):
    temp = 0
    for i in range(3):
        # X[i]の色にする
        x = X[i]
        y = feeling[:, x]
        temp += (three[i] * y).sum()
    if temp < answer:
        answer = temp

print(answer)
# 13

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)]
#print(d)
#print(c)

from collections import defaultdict
cd = [defaultdict(int), defaultdict(int), defaultdict(int)]
for i in range(N):
    for j in range(N):
        k = (i+1+j+1) % 3
        cd[k][c[i][j]] += 1

ans = 10 ** 10
import itertools
for p in itertools.permutations(list(range(C)), 3):
    iwa = 0
    for ci in cd[0].items():
        iwa += d[ci[0]-1][p[0]] * ci[1]
    for ci in cd[1].items():
        iwa += d[ci[0]-1][p[1]] * ci[1]
    for ci in cd[2].items():
        iwa += d[ci[0]-1][p[2]] * ci[1]
    ans = min(ans, iwa)
#print(cd)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

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

for i in range(3):
    for j in range(C):
        for k in range(C):
            disc[i][j]+=D[k][j]*cnt[i][k+1]
ans=10**10

for i,j,k in permutations(range(C),3):
    ans=min(ans,disc[0][i]+disc[1][j]+disc[2][k])

print(ans)

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(c)]
li = [list(map(int,input().split())) for i in range(n)]
ans = 10 ** 100
cnt = [0,0,0]
masu = [[0 for i in range(c)] for j in range(3)]
for i in range(n):
    for j in range(n):
        cnt[(i+j)%3] += 1
        masu[(i+j)%3][li[i][j]-1] += 1
for i in range(c):
    for j in range(c):
        if i != j:
            for k in range(c):
                if i != k and j != k:
                    tryans = 0
                    num = [i,j,k]
                    for l in range(3):
  #                         print(num[l], masu[l])
                        for h in range(c):
                            if h != num[l]:
                                tryans += lis[h][num[l]] * masu[l][h]
                    ans = min(ans,tryans)
  #                 print(i,j,k,ans)
print(ans)

Submission status: Accepted

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

cnt = [[0]*C for _ in range(3)]
for i in range(n):
    for j in range(n):
        for k in range(C):
            cnt[(i+j)%3][k] += d[c[i][j]][k]

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
            ans = min(ans, cnt[0][i] + cnt[1][j] + cnt[2][k])
print(ans)

Submission status: Accepted

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

cnt = [[0]*C for _ in range(3)]
for i in range(n):
    for j in range(n):
        for k in range(C):
            for r in range(3):
                if (i+j)%3 == r: cnt[r][k] += d[c[i][j]][k]

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
            ans = min(ans, cnt[0][i] + cnt[1][j] + cnt[2][k])
print(ans)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(c)]
C = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n)]

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

from itertools import permutations
d = 1000*500*500
for p0, p1, p2 in permutations(list(range(c)), 3):
    d_ = 0
    for c_from in range(c):
        d_ += cols[0][c_from]*D[c_from][p0]
        d_ += cols[1][c_from]*D[c_from][p1]
        d_ += cols[2][c_from]*D[c_from][p2]
    d = min(d, d_)
print(d)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

r0 = []
r1 = []
r2 = []
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            r0.append(c[i][j])
        elif (i+j)%3 == 1:
            r1.append(c[i][j])
        else:
            r2.append(c[i][j])

d0 = [[]]*C
d1 = [[]]*C
d2 = [[]]*C
for color in range(C):
    s = 0
    for i in range(len(r0)):
        s += D[r0[i]-1][color]
    d0[color] = (s,color)
for color in range(C):
    s = 0
    for i in range(len(r1)):
        s += D[r1[i]-1][color]
    d1[color] = (s,color)
for color in range(C):
    s = 0
    for i in range(len(r2)):
        s += D[r2[i]-1][color]
    d2[color] = (s,color)

d0.sort()
d1.sort()
d2.sort()

ans = float("inf")
for i in range(3):
    for j in range(3):
        for k in range(3):
            if d0[i][1] != d1[j][1] and d0[i][1] != d2[k][1] and d1[j][1] != d2[k][1]:
                ans = min(ans,d0[i][0]+d1[j][0]+d2[k][0])
print(ans)

Submission status: Accepted

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

d = []
for _ in range(C):
    d.append(tuple(map(int, sys.stdin.readline().rstrip().split())))

r_0 = []
r_1 = []
r_2 = []
for i in range(N):
    g = list(map(int, sys.stdin.readline().rstrip().split()))
    for j in range(N):
        if (i + j) % 3 == 0:
            r_0.append(g[j])
        elif (i + j) % 3 == 1:
            r_1.append(g[j])
        else:
            r_2.append(g[j])

def get_cost(r):
    cost = [0] * (C + 1)
    for c in range(1, C + 1):
        for i in r:
            cost[c] += d[i - 1][c - 1]

    return cost

cost_0 = get_cost(r_0)
cost_1 = get_cost(r_1)
cost_2 = get_cost(r_2)

ans = 10**18
for c_0, c_1, c_2 in permutations(range(1, C + 1), 3):
    total = cost_0[c_0] + cost_1[c_1] + cost_2[c_2]
    ans = min(ans, total)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

C0 = defaultdict(int)
C1 = defaultdict(int)
C2 = defaultdict(int)

for i in range(N):
    for j in range(N):
        if (i + j + 2) % 3 == 0:
            C0[Color[i][j]] += 1
        elif (i + j + 2) % 3 == 1:
            C1[Color[i][j]] += 1
        else:
            C2[Color[i][j]] += 1

ans = float('inf')
for x in range(C):
    for y in range(C):
        for z in range(C):
            if x == y or y == z or z == x:
                continue
            ansi = 0
            for key, value in C0.items():
                ansi += Disguise[key - 1][x] * value
            for key, value in C1.items():
                ansi += Disguise[key - 1][y] * value
            for key, value in C2.items():
                ansi += Disguise[key - 1][z] * value
            ans = min(ansi, ans)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

MAXN = 500
MAXC = 30

s = [[0 for _ in range(MAXC)] for _ in range(3)]
for i in range(3):
    for co in range(c):
        for x in range(n):
            for y in range(n):
                if (x+y)%3 == i:
                    s[i][co] += d[grid[x][y]-1][co]

ans = 10**10
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, s[0][c0]+s[1][c1]+s[2][c2])
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)]
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):
        for j in range(C):
            t += a[i][j] * D[j][b[i]]
    result = min(result, t)
print(result)