Problem:


Score : 400 points

Problem Statement

There is a grid with N rows and N columns of squares. Let (i,j) be the square at the i-th row from the top and the j-th column from the left.

These squares have to be painted in one of the C colors from Color 1 to Color C. Initially, (i,j) is painted in Color c_{i,j}.

We say the grid is a good grid when the following condition is met for all i,j,x,y satisfying 1 \leq i,j,x,y \leq N:

If (i+j) \% 3=(x+y) \% 3, the color of (i,j) and the color of (x,y) are the same.

If (i+j) \%  3 \neq (x+y) \% 3, the color of (i,j) and the color of (x,y) are different.

Here, X \% Y represents X modulo Y.

We will repaint zero or more squares so that the grid will be a good grid.

For a square, the wrongness when the color of the square is X before repainting and Y after repainting, is D_{X,Y}.

Find the minimum possible sum of the wrongness of all the squares.

Constraints

1 \leq N \leq 500

3 \leq C \leq 30

1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)

1 \leq c_{i,j} \leq C

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C
D_{1,1} ... D_{1,C}
:
D_{C,1} ... D_{C,C}
c_{1,1} ... c_{1,N}
:
c_{N,1} ... c_{N,N}

Output

If the minimum possible sum of the wrongness of all the squares is x, print x.

Sample Input 1

2 3
0 1 1
1 0 1
1 4 0
1 2
3 3

Sample Output 1

3

Repaint (1,1) to Color 2. The wrongness of (1,1) becomes D_{1,2}=1.

Repaint (1,2) to Color 3. The wrongness of (1,2) becomes D_{2,3}=1.

Repaint (2,2) to Color 1. The wrongness of (2,2) becomes D_{3,1}=1.

In this case, the sum of the wrongness of all the squares is 3.

Note that D_{i,j} \neq D_{j,i} is possible.

Sample Input 2

4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2

Sample Output 2

428



Sample input:
2 3
0 1 1
1 0 1
1 4 0
1 2
3 3


Sample output:
3

Submission status: Accepted

Solution code:
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n,c=map(int,input().split())
D=[]
for i in range(c):
    D.append(list(map(int,input().split())))
G=[]
for i in range(n):
    a=list(map(int,input().split()))
    G.append([i-1 for i in a])
A=[]
B=[]
C=[]
for i in range(n):
    for j in range(n):
        d=(i+j)%3
        if d==0:
            A.append(G[i][j])
        elif d==1:
            B.append(G[i][j])
        else:
            C.append(G[i][j])
A=Counter(A);B=Counter(B);C=Counter(C)
cost=inf
for s in range(c):
    for t in range(c):
        if s==t:continue
        for r in range(c):
            if s==r or t==r:continue
            cost=min(cost, sum(D[i][s]*j for i,j in A.items())+sum(D[i][t]*j for i,j in B.items())+sum(D[i][r]*j for i,j in C.items()))
print(cost)

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)]
color = [{} for i in range(3)]
for h in range(N):
    for w in range(N):
        if c[h][w] not in color[(h+w+2)%3]:
            color[(h+w+2)%3][c[h][w]] = 1
        else:
            color[(h+w+2)%3][c[h][w]] += 1

ans = float('inf')
for c1 in range(1,C+1):
    for c2 in range(1,C+1):
        if c1 != c2:
            for c3 in range(1,C+1):
                if c1 != c3 and c2 != c3:
                    cand = 0
                    for k,v in color[0].items():
                        cand += D[k-1][c1-1]*v
                    for k,v in color[1].items():
                        cand += D[k-1][c2-1]*v
                    for k,v in color[2].items():
                        cand += D[k-1][c3-1]*v
                    ans = min(ans,cand)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,C=map(int,input().split())
D=[tuple(map(int, input().split())) for i in range(C)]
c=[tuple(map(lambda x:int(x)-1, input().split())) for i in range(N)]
iw=[[0]*C for i in range(3)]
l=[[] for i in range(3)]
for i in range(N):
    for j in range(N):
        l[(i+j)%3].append(c[i][j])
for i in range(3):
    for j in range(C):
        for k in l[i]:
            iw[i][j]+=D[k][j]
a=10**9
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i!=j and i!=k and j!=k:
                a=min(a,iw[0][i]+iw[1][j]+iw[2][k])
print(a)

Submission status: Accepted

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

Res = [[] for _ in range(3)]
\
for i in range(n):
    for j in range(n):
        now = C[i][j]
        if (i+j) % 3 == 0:
            Res[0].append(now)
        elif (i+j) % 3 == 1:
            Res[1].append(now)
        else:
            Res[2].append(now)

Res_cost = [[0 for _ in range(c_max)] for _ in range(3)]

for i in range(3):    
    for color in range(c_max):
        cost = 0
        for now in Res[i]:
            cost += D[now-1][color-1]
        Res_cost[i][color-1] = cost

ans = 10**10
for i in range(c_max):
    for j in range(c_max):
        for k in range(c_max):
            if i == j or j == k or k == i:
                continue
            cost = Res_cost[0][i] + Res_cost[1][j] + Res_cost[2][k]
            ans = min(cost, ans)
# print(Res_cost)
# print(Res)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, C, *L = map(int, open(0).read().split())
ls =[[0]*(C+1) for i in range(3)]
D = L[:C*C]
X = L[C*C:]
for i in range(N):
  for j in range(N):
    c = X[i*N+j]
    ls[(i+j)%3][c] += 1
cost = [[0]*(C+1) for i in range(3)]
for i in range(3):
  n = sum(ls[i])
  for j in range(1,C+1):
    for h in range(1,C+1):
      cost[i][j] += D[(h-1)*C+j-1]*ls[i][h]
  
ans = 10**10
for l in permutations(range(1,C+1),3):
  ans = min(ans, sum(cost[i][l[i]] for i in range(3)))
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

def main():
    N, C = map(int, input().split())
    D = tuple(tuple(map(int, input().split())) for _ in range(C))

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

    for i in range(N):
        c = [int(x)-1 for x in input().split()]
        for j in range(3):
            cnt[j].update(c[(3-(i+2)+j)%3::3])

    ans = 1000*500*500+5
    for p in permutations(range(C), 3):
        s = 0
        for j in range(3):
            s += sum(D[k][p[j]] * v for k, v in cnt[j].items())
        if s < ans: ans = s
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

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

    for i in range(N):
        c = [int(x)-1 for x in input().split()]
        for j in range(3):
            cnt[j].update(c[(3-(i+2)+j)%3::3])

    ans = 1000*500*500+5
    for p in permutations(range(C), 3):
        s = 0
        for j in range(3):
            s += sum(D[k][p[j]] * v for k, v in cnt[j].items())
        if s < ans: ans = s
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

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

    for i in range(N):
        c = [int(x)-1 for x in input().split()]
        for j in range(3):
            cnt[j].update(c[(3-(i+2)+j)%3::3])

    ans = 1000*500*500+5
    for p in permutations(range(C), 3):
        s = 0
        for j in range(3):
            s += sum(D[k][p[j]] * v for k, v in cnt[j].items())
        if s < ans: ans = s
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

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

    for i in range(N):
        c = [int(x)-1 for x in input().split()]
        for j in range(3):
            cnt[j].update(c[(3-(i+2)+j)%3::3])

    ans = 1000*500*500+5
    for p in permutations(range(C), 3):
        s = 0
        for j in range(3):
            s += sum(D[k][p[j]] * v for k, v in cnt[j].items())
        ans = min(ans, s)
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

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

    for i in range(N):
        c = [int(x)-1 for x in input().split()]
        for j in range(3):
            cnt[j].update(c[(3-(i+2)+j)%3::3])

    ans = 1000*500*500+5
    for p in permutations(range(C), 3):
        s = 0
        for j in range(3):
            s += sum(D[k][p[j]] * v for k, v in cnt[j].items())
        ans = min(ans, s)
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

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

    for i in range(N):
        c = [int(x)-1 for x in input().split()]
        for j in range(3):
            cnt[j].update(c[(3-(i+2)+j)%3::3])

    ans = 1000*500*500+5
    for p in permutations(range(C), 3):
        s = 0
        for j in range(3):
            for k, v in cnt[j].items():
                s += D[k][p[j]] * v
        ans = min(ans, s)

    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations
import sys
input = sys.stdin.buffer.readline
N, C = map(int, input().split())
D = [[int(x) for x in input().split()] for _ in range(C)]

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

for i in range(N):
    c = [int(x)-1 for x in input().split()]
    for j in range(3):
        cnt[j].update(c[(3-(i+2)+j)%3::3])

ans = 1000*500*500+5
for p in permutations(range(C), 3):
    s = 0
    for j in range(3):
        for k, v in cnt[j].items():
            s += D[k][p[j]] * v
    ans = min(ans, s)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
D = [[int(x) for x in input().split()] for _ in range(C)]

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

for i in range(N):
    c = [int(x)-1 for x in input().split()]
    for j in range(3):
        cnt[j].update(c[(3-(i+2)+j)%3::3])

ans = 1000*500*500+5
for p in permutations(range(C), 3):
    s = 0
    for j in range(3):
        for k, v in cnt[j].items():
            s += D[k][p[j]] * v
    ans = min(ans, s)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import permutations

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

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

for i in range(N):
    c = [int(x)-1 for x in input().split()]
    for j in range(3):
        cnt[j].update(c[(3-(i+2)+j)%3::3])

ans = 1000*500*500+5
for p in permutations(range(C), 3):
    s = 0
    for j in range(3):
        for k, v in cnt[j].items():
            s += D[k][p[j]] * v
    ans = min(ans, s)

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

X = [[] for i in range(3)]
for i in range(N):
    for j in range(N):
        X[(i+j+2)%3].append(G[i][j])
ans = float('inf')

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

for c in range(C):
    for i in range(3):
        for e in X[i]:
            Costs[i][c] += D[e-1][c]

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            cost = 0
            for i,e in enumerate([c1,c2,c3]):
                cost += Costs[i][e]
            ans = min(cost,ans)
print(ans)

Submission status: Accepted

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

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
count = [[0] * C for _ in range(3)]
for i in range(N):
    for j in range(N):
        count[(i+j) % 3][c[i][j]] += 1
ans = float('inf')
for p in permutations(range(C), 3):
    tmp = 0
    for i in range(3):
        for j in range(C):
            tmp += count[i][j] * D[j][p[i]]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
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()))

c = [0 for i in range(N)]

for i in range(N):
    c[i] = list(map(int,input().split()))
    for j in range(N):
        c[i][j] -= 1
#print(c)

differ = [[0]*C for i in range(3)]
###differ[i][j] (x+y)%3==i　となるようなマス全ての色をCにした時の違和感の合計

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

ans = 25 *(10**7)

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

print(ans)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
cost = []
grid = []
for i in range(c):
    cost.append(list(map(int, input().split())))
for i in range(n):
    grid.append(list(map(int, input().split())))
div_3 = [[0 for i in range(c+1)] for j in range(3)]
for i in range(n):
    for j in range(n):
        div_3[(i+j+2)%3][grid[i][j]-1] += 1
ans = 10**9
for zero in range(c):
    for one in range(c):
        for two in range(c):
            if len(set([zero,one,two])) <= 2:
                continue
            cand = 0
            #3で割った余りがone,zeroとかの色で決まっている状態
            cand += sum([div_3[0][i] * cost[i][zero] for i in range(c) if i != zero])
            cand += sum([div_3[1][i] * cost[i][one]  for i in range(c) if i != one])
            cand += sum([div_3[2][i] * cost[i][two]  for i in range(c) if i != two])
            ans = min(ans, cand)
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)]

from collections import Counter
t=[Counter([c[i][j] for i in range(N) for j in range(N) if (i+j)%3==m]) for m in range(3)]

ans = 10**9
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
            d = 0
            for before in range(C):
                d += D[before][i] * t[0][before+1]
                d += D[before][j] * t[1][before+1]
                d += D[before][k] * t[2][before+1]
            ans = min(ans, d)
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)]

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

for color in range(1,C+1):
    t = [0]*3
    for i in range(N):
        for j in range(N):
            if c[i][j] != color:
                t[(i+j)%3] += D[c[i][j]-1][color-1]
    for k in range(3):
        d[k].append((color, t[k]))

for k in range(3):
    d[k].sort(key=lambda x:x[1])

ans = 10**9
for i in range(3):
    for j in range(3):
        for k in range(3):
            if len({d[0][i][0], d[1][j][0], d[2][k][0]}) != 3: continue
            ans = min(ans, d[0][i][1] + d[1][j][1] + d[2][k][1])
print(ans)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
D=[[]for i in range(C)]
for i in range(C):
    D[i]=list(map(int,input().split()))
c=[[] for i in range(N)]
for i in range(N):
    c[i]=list(map(int,input().split()))
data0=[0 for i in range(0,C+1)]
data1=[0 for i in range(0,C+1)]
data2=[0 for i in range(0,C+1)]

for i in range(0,N):
    for j in range(0,N):
        if (i+j)%3==0:
            data0[c[i][j]]+=1
        elif (i+j)%3==1:
            data1[c[i][j]]+=1
        else:
            data2[c[i][j]]+=1

ans=10**100
for i in range(1,C+1):
    for j in range(1,C+1):
        for k in range(1,C+1):
            if i!=j and j!=k and k!=i:
                test=sum(data0[l]*D[l-1][i-1] for l in range(1,C+1))+sum(data1[l]*D[l-1][j-1] for l in range(1,C+1))+sum(data2[l]*D[l-1][k-1] for l in range(1,C+1))
                if test<ans:
                    ans=test
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)]

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

ans = 1001001001
for i, j, k in permutations(range(C), 3):
    tmp = 0
    for l in range(C):
        tmp += D[l][i] * t[0][l]
    for l in range(C):
        tmp += D[l][j] * t[1][l]
    for l in range(C):
        tmp += D[l][k] * t[2][l]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=inf

n,c=LI()
d=[defaultdict(int)for i in' '*3]
f=[]
for i in range(c):
    f+=[LI()]
for i in range(n):
    x=LI()
    for j in range(n):
        d[(i+j)%3][x[j]-1]+=1

for i in range(c):
    for j in range(c):
        for k in range(c):
            if len(set([i,j,k]))<3:
                continue
            tmp=0
        
            for col,cnt in d[0].items():
                tmp+=f[col][i]*cnt
            for col,cnt in d[1].items():
                tmp+=f[col][j]*cnt
            for col,cnt in d[2].items():
                tmp+=f[col][k]*cnt
            ans=min(ans,tmp)

print(ans)

Submission status: Accepted

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

lst=[[],[],[]]

for y in range(N):
    for x in range(N):
        lst[(y+x)%3].append(c[y][x])


Revalue=10**18

valuelst=[[0 for i in range(C)] for i in range(3)]
for v in range(3):
    for Color in range(1,C+1):
        value=0
        for i in lst[v]:
            value+=D[i-1][Color-1]
        valuelst[v][Color-1]=value


for Color1,Color2,Color3 in list(permutations(list(range(1,C+1)),3)):
    value=valuelst[0][Color1-1]+valuelst[1][Color2-1]+valuelst[2][Color3-1]

    Revalue=min(Revalue,value)
print(Revalue)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(c)]
z=[]
o=[]
t=[]
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(n):
    if (i+j+2)%3==0:
      z.append(a[j])
    elif (i+j+2)%3==1:
      o.append(a[j])
    else:
      t.append(a[j])
zz=[0]*c
oo=[0]*c
tt=[0]*c
for i in range(c):
  su=0
  for j in z:
    su+=d[j-1][i]
  zz[i]=su
  su=0
  for j in o:
    su+=d[j-1][i]
  oo[i]=su
  su=0
  for j in t:
    su+=d[j-1][i]
  tt[i]=su
x=10**10
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
      x=min(x,zz[i]+oo[j]+tt[k])
print(x)

Submission status: Accepted

Solution code:
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()))
C=[[0]*n for i in range(n)]
for i in range(n):
  C[i]=list(map(int,input().split()))
  for j in range(n):
    C[i][j]=C[i][j]-1
A=[[0]*c for i in range(3)]
for i in range(n):
  for j in range(n):
    A[(i+j)%3][C[i][j]]+=1
ans=0
e=10**20
for i in range(c):
  for j in range(c):
    if j==i:
      continue
    for k in range(c):
      if k==i:
        continue
      if k==j:
        continue
      f=0
      for u in range(c):
        f=f+A[0][u]*D[u][i]+A[1][u]*D[u][j]+A[2][u]*D[u][k]
      if e>f:
        e=f
print(e)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
irohen=[list(map(int,input().split())) for i in range(c)]
grid=[list(map(int,input().split())) for i in range(n)]
rem0=[0]*c
rem1=[0]*c
rem2=[0]*c
for i in range(n):
    for j in range(n):
        if (i+j)%3==0:
            rem0[grid[i][j]-1]+=1
        elif (i+j)%3==1:
            rem1[grid[i][j]-1]+=1
        elif (i+j)%3==2:
            rem2[grid[i][j]-1]+=1
ans=10**10
for i in range(c):
    for j in range(c):
        for h in range(c):
            chk=0
            if i==j or i==h or j==h:
                continue
            for k in range(c):
                chk+=rem0[k]*irohen[k][i]+rem1[k]*irohen[k][j]+rem2[k]*irohen[k][h]
            if chk < ans:ans=chk
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations as per
n,c = map(int,input().split())
d = [tuple(map(int,input().split())) for i in range(c)]
g = [[0]*c,[0]*c,[0]*c]
for i in range(1,n+1):
  ci = tuple(map(int,input().split()))
  for j in range(1,n+1):
    g[(i+j)%3][int(ci[j-1])-1] += 1
m = 10 ** 10
for i in per(range(c),3):
  e = 0
  for j in range(3):
    for o in range(c):
      e += g[j][o]*d[o][i[j]-1]
  m = min(m,e)
print(m)

Submission status: Accepted

Solution code:

from collections import Counter

N, K, *DC = map(int, open(0).read().split())

D = tuple(zip(*[iter(DC[:K * K])] * K))
C = tuple(zip(*[iter(DC[K * K:])] * N))

A = [Counter() for _ in range(3)]
for k in range(K):
    for i in range(N):
        for j in range(N):
            A[(i + j) % 3][k] += D[C[i][j] - 1][k]

ans = float("inf")
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i == j or j == k or k == i:
                continue
            ans = min(ans, A[0][i] + A[1][j] + A[2][k])

print(ans)

Submission status: Accepted

Solution code:
#14:31
n,m = map(int,input().split())
ch = []
for _ in range(m):
  ch.append(list(map(int,input().split())))
raw = []
for _ in range(n):
  raw.append(list(map(int,input().split())))
res = [[0 for _ in range(m)] for _ in range(3)]
for i in range(n):
  for j in range(n):
    d = (i+j) % 3
    e = raw[i][j] - 1
    res[d][e] += 1
#print(res)
can = []
for i in range(m):
  for j in range(m):
    for k in range(m):
      if i == j or j == k or k == i:
        continue
      tmp = 0
      for l in range(m):
        tmp += res[0][l] * ch[l][i]
        tmp += res[1][l] * ch[l][j]
        tmp += res[2][l] * ch[l][k]
      can.append(tmp)
print(min(can))
#print(can)

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)]
change = dict()
for i in range(C):
    for j in range(C):
        change[(i+1,j+1)] = D[i][j]

grid = [tuple(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):
        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")
# 色のとり方
# 余り0がi,1がj,2がkになる
for i in range(C):
    
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            tmp = 0
            if i == k or j == k:
                continue
            
            for c,v in mod_0.items():
               tmp += change[(c, i+1)] * v
            for c,v in mod_1.items():
                   tmp += change[(c, j+1)] * v
            for c,v in mod_2.items():
                   tmp += change[(c, k+1)] * v

            ans = min(ans, tmp)
            
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

lst = [[0] * 3 for _ in range(C)]
for y in range(N):
    for x in range(N):
        for c in range(C):
            lst[c][(x + y) % 3] += D[L[y][x] - 1][c]

ans = float('inf')
for t in itertools.permutations(range(C), 3):
    ans = min(ans, sum(lst[t[i]][i] for i in range(3)))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N, C = Scanner.map_int()
    D = Scanner.int_list_list(C)
    colors = Scanner.int_list_list(N)
    for i in range(N):
        for j in range(N):
            colors[i][j] -= 1
    T = [[0 for _ in range(C)] for _ in range(3)]
    for h in range(N):
        for w in range(N):
            T[(h+w) % 3][colors[h][w]] += 1
    ans = INF
    for a in range(C):
        for b in range(C):
            for c in range(C):
                if a == b or a == c or b == c:
                    continue
                now = 0
                for d in range(C):
                    now += T[0][d] * D[d][a]
                    now += T[1][d] * D[d][b]
                    now += T[2][d] * D[d][c]
                ans = min(ans, now)
    print(ans)
    return


if __name__ == "__main__":
    main()

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

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
D=[]
D.append([0 for i in range(C+1)])
for i in range(C):
    d=[0]+list(map(int,input().split()))
    D.append(d)
#print(D)
L=[]
for i in range(N):
    c=list(map(int,input().split()))
    L.append(c)

M0=[0 for i in range(C+1)]
M1=[0 for i in range(C+1)]
M2=[0 for i in range(C+1)]

for i in range(N):
    for j in range(N):
        if (i+j)%3==0:
            M0[L[i][j]]+=1
        elif (i+j)%3==1:
            M1[L[i][j]]+=1
        elif (i+j)%3==2:
            M2[L[i][j]]+=1
#print(M0,M1,M2)

Col=[i for i in range(1,C+1)]
#print(Col)
import itertools
Arr=list(itertools.permutations(Col,3))
#print(Arr)
ans=10**20
for i in range(len(Arr)):
    cnt=0
    for j in range(1,C+1):
        cnt+=M0[j]*D[j][Arr[i][0]]
        cnt+=M1[j]*D[j][Arr[i][1]]
        cnt+=M2[j]*D[j][Arr[i][2]]
    if ans>cnt:
        ans=cnt
    #print(cnt,Arr[i])
print(ans)