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

color = [[int(i) for i in input().split()] for _ in range(N)]
M = [defaultdict(int) for _ in range(3)]
for i in range(N):
    for j in range(N):
        M[(i+j) % 3][color[i][j]] += 1

ans = 10**20
for Y0 in range(C):
    for Y1 in range(C):
        for Y2 in range(C):
            if Y0 != Y1 and Y1 != Y2 and Y2 != Y0:
                Y = (Y0, Y1, Y2)
                d = 0
                for i in range(3):
                    for X, v in M[i].items():
                        d += D[X-1][Y[i]]*v
                ans = min(ans, d)
print(ans)

Submission status: Accepted

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

cost = [[0 for j in range(C)] for i in range(3)]
for i in range(N):
    for j in range(N):
        rem = (i+j+2)%3
        x = G[i][j] -1
        for y in range(C):
            cost[rem][y] += D[x][y]
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, cost[0][i] + cost[1][j] + cost[2][k])
print(ans)

Submission status: Accepted

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

from collections import Counter
from itertools import permutations

n, c = map(int, input().split())
d = [list(map(int,input().split())) for _ in range(c)]
ci = [[] for _ in range(3)]
for i in range(n):
    cl = list(map(int, input().split()))
    for j in range(3):
        ci[(i+j)%3].extend(cl[j::3])
for i in range(3):
    ci[i] = Counter(ci[i])

def iwa(cols):
    ret = 0
    for i in range(3):
        for x, v in ci[i].items():
            ret += v * d[x-1][cols[i]]
    return ret

L = list(permutations(range(c), 3))
ret = 500*500*1000
for cols in L:
    ret = min(ret, iwa(cols))
print(ret)

Submission status: Accepted

Solution code:
N,C=(int(i) for i in input().strip().split(" "))
D=[]
c=[]
for i in range(C):
    D.append([int(i) for i in input().strip().split(" ")])
for i in range(N):
    c.append([int(i) for i in input().strip().split(" ")])
from collections import defaultdict
d0=defaultdict(int)
d1=defaultdict(int)
d2=defaultdict(int)
d=[d0,d1,d2]
for i in range(N):
    for j in range(N):
        d[(i+j+2)%3][c[i][j]]+=1

from itertools import permutations
l=list(range(1,C+1))
k=permutations(l,3)
m=999999999999999999999999
for p in k:
    w=0
    a0,a1,a2=p
    for i in d[0].keys():
        w+=(D[i-1][a0-1]*(d[0][i]))
    for i in d[1].keys():
        w+=(D[i-1][a1-1]*(d[1][i]))
    for i in d[2].keys():
        w+=(D[i-1][a2-1]*(d[2][i]))
    if w<m:
        m=w
print(m)

Submission status: Accepted

Solution code:
from itertools import permutations

n,c = map(int, input().split())
cln = list(range(0,c))
cpl = list(permutations(cln,3))

dl = []
for _ in range(c):
    row = list(map(int, input().split()))
    dl.append(row)

cl = []
for _ in range(n):
    row = list(map(int, input().split()))
    cl.append(row)


costs = [ [0]*c for _ in range(3) ]
for i in range(n):
    for j in range(n):
        for target_c in range(c):
            val3 = (i+j+2)%3
            orig_c = cl[i][j]-1
            cost = dl[orig_c][target_c]
            costs[val3][target_c] += cost


ans = 10**10
for cp in cpl:
    cost = costs[0][cp[0]] + costs[1][cp[1]] + costs[2][cp[2]]
    ans = min(ans,cost)

print(ans)

Submission status: Accepted

Solution code:
n,c = map(int,input().split())

D_list = [[int(i) for i in input().split()] for _ in range(c)]
c_list = [[int(i) for i in input().split()] for _ in range(n)]

c_num=[[0 for _ in range(3)] for __ in range(c)]

for a in range(n):
    for b in range(n):
        c_num[c_list[b][a]-1][(a+b+2)%3] += 1


ans = 10 ** 10
for i in range(1,c**3):
    x=i%c
    y=(i%c**2)//c
    z=i//c**2
    if x==y or y==z or z==x:
        continue
    else:
        color=[x,y,z]
        count = 0
        for s in range(3):
            for t in range(c):
                count += c_num[t][s] *D_list[t][color[s]]

        if count < ans:
            ans = count

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations

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

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

c = [None] * N
for i in range(N):
    c[i] = list(map(int, input().split()))

# (i+j)%3 = 0,1,2 のそれぞれで初期マスの色をカウント
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 = 10**12

# 塗り分けの順列総数
for p in permutations(range(C),3):
    tmp = 0
    for i in range(C):
        tmp += D[i][p[0]] * t[0][i]
        tmp += D[i][p[1]] * t[1][i]
        tmp += D[i][p[2]] * t[2][i]
    ans = min(ans,tmp)

print(ans)

Submission status: Accepted

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

from collections import Counter
ctrs = [Counter() for _ in range(3)]
for i,row in enumerate(E):
    for j,c in enumerate(row):
        ctrs[(i+j)%3][c] += 1

ans = float('inf')
from itertools import permutations
for ptn in permutations(range(1,C+1), 3):
    t = 0
    for p,c in zip(ptn,ctrs):
        for k,v in c.items():
            t += D[k-1][p-1] * v
    ans = min(ans, t)
print(ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,c = map(int,ipt().split())
    d = [[int(i) for i in ipt().split()] for j in range(c)]
    cs = [[int(i) for i in ipt().split()] for j in range(n)]
    di = [defaultdict(int) for i in range(3)]
    for i in range(n):
        for j in range(n):
            di[(i+j)%3][cs[i][j]] += 1

    cost = [[0]*c for i in range(3)]
    for i in range(3):
        for j in range(c):
            sm = 0
            for k in range(c):
                sm += d[k][j]*di[i][k+1]
            cost[i][j] = sm

    cm = [[(ci,i) for i,ci in enumerate(cost[j])] for j in range(3)]
    cm[0].sort()
    cm[1].sort()
    cm[2].sort()
    mi = 10**18
    for i in range(3):
        for j in range(3):
            for k in range(3):
                nm = cm[0][i][0]+cm[1][j][0]+cm[2][k][0]
                if cm[0][i][1] != cm[1][j][1] != cm[2][k][1] != cm[0][i][1] and mi > nm:
                    mi = nm

    print(mi)


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n,m=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(m)]
c_0={}
c_1={}
c_2={}

for i in range(n):
    c=list(map(int,input().split()))
    for j in range(n):
        if (i+j+2)%3==0:
            if c[j] not in c_0:
                c_0[c[j]]=1
            else:
                c_0[c[j]]+=1
        elif (i+j+2)%3==1:
            if c[j] not in c_1:
                c_1[c[j]]=1
            else:
                c_1[c[j]]+=1
        else:
            if c[j] not in c_2:
                c_2[c[j]]=1
            else:
                c_2[c[j]]+=1
color=[i for i in (range(1,m+1))]
ans=10**9
for l in itertools.permutations(color,3):
    x,y,z=l
    res=0
    for cr in c_0:
        res+=d[cr-1][x-1]*c_0[cr]
    for cr in c_1:
        res+=d[cr-1][y-1]*c_1[cr]
    for cr in c_2:
        res+=d[cr-1][z-1]*c_2[cr]
    ans=min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
n,c = map(int, input().split())

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

ax = [[0 for i in range(c)] for j in range(3)]

for i in range(n):
    for j in range(n):
        x = (i+j) % 3
        ax[x][nl[i][j]-1] += 1

l = list(range(0,c))
import itertools
ll = list(itertools.permutations(l, 3))
res = float('inf')

#axを変換していくコストを全列挙
for i in ll:
    temp= 0
    for j in range(c):
        temp += ax[0][j]*dl[j][i[0]]
        temp += ax[1][j]*dl[j][i[1]]
        temp += ax[2][j]*dl[j][i[2]]
    res= min(res,temp)
print(res)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from itertools import permutations

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, C = NMI()
    D = [NLI() for _ in range(C)]
    grid = [list(map(lambda x: int(x)-1, NMI())) for _ in range(N)]

    grid_mod = [{i:0 for i in range(C)} for _ in range(3)]
    for h in range(N):
        for w in range(N):
            t = (h+w) % 3
            grid_mod[t][grid[h][w]] += 1

    ans = 10**10
    for colors in permutations(range(C), 3):
        diff = 0
        for i in range(3):
            for c, n in grid_mod[i].items():
                diff += D[c][colors[i]] * n
        ans = min(ans, diff)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N,C =map(int,input().split())
D = [0]+[[0]+list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]
 
grid = [[],[],[]]
for i in range(N):
  for j in range(N):
    grid[(i+j)%3].append(c[i][j])

s = [[0]*(C+1) for i in range(3)]
 
for i in range(3):
  for j in range(1,C+1,1):
    for k in range(len(grid[i])):
      s[i][j]+=D[grid[i][k]][j]

ans = float("inf")
for p in itertools.permutations(list(range(1,C+1)),3):
  tmp = 0
  for i in range(3):
     tmp +=s[i][p[i]]
  ans = min(tmp,ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import sys
def query(i,j):
    print("? {0} {1}".format(i, j))
    sys.stdout.flush()
    return int(input())

n,c = list(map(int, input().split()))
ds = [None]*c
cs = [None]*n
for i in range(c):
    ds[i] = list(map(int, input().split()))
for i in range(n):
    cs[i] = list(map(lambda x : int(x)-1, input().split()))
from itertools import product
ans = float("inf")
v0 = [0]*c
v1 = [0]*c
v2 = [0]*c
for i,j in product(range(n), range(n)):
    if (i+j)%3==0:
        v = v0
    elif (i+j)%3==1:
        v = v1
    else:
        v = v2
    for cc in range(c):
        v[cc] += ds[cs[i][j]][cc]
for c0,c1,c2 in product(range(c), range(c), range(c)):
    if c0==c1 or c0==c2 or c1==c2:
        continue
    val = v0[c0] + v1[c1] + v2[c2]
    ans = min(ans, val)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    col_cnt = [[0] * c for _ in range(3)]
    for i in range(n):
        for j in range(n):
            col = grid[i][j] - 1
            col_cnt[(i + j + 2) % 3][col] += 1

    res = f_inf
    for pattern in permutations(list(range(c)), 3):
        cost = 0
        for idx, col in enumerate(pattern):
            for k in range(c):
                cnt = col_cnt[idx][k]
                cost += D[k][col] * cnt
        res = min(res, cost)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,C = LI()
D = [[0]*(C+1)] + [[0]+LI() for _ in range(C)]
c = [[0]*(N+1)] + [[0]+LI() for _ in range(N)]

from collections import defaultdict

d0,d1,d2 = defaultdict(int),defaultdict(int),defaultdict(int)
# dk = ((i+j)%3==k たる (i,j) に対して各色が何個ずつあるか)
for i in range(1,N+1):
    for j in range(1,N+1):
        if (i + j) % 3 == 0:
            d0[c[i][j]] += 1
        elif (i + j) % 3 == 1:
            d1[c[i][j]] += 1
        elif (i + j) % 3 == 2:
            d2[c[i][j]] += 1

ans = 10**18
# 変化後の色で全探索
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 k == i:
                continue
            else:
                a = 0
                for color in d0.keys():
                    a += D[color][i]*d0[color]
                for color in d1.keys():
                    a += D[color][j]*d1[color]
                for color in d2.keys():
                    a += D[color][k]*d2[color]
                ans = min(ans,a)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
INF=10**18
n,c=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(c)]
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(c)]for i in range(3)]
for i in range(n):
  for j in range(n):
    dp[(i+j)%3][a[i][j]-1]+=1
li=list(permutations(list(range(c)),3))
fans=INF
for i,j,k in li:
  ans=0
  for x in range(c):
    ans+=dp[0][x]*d[x][i]
    ans+=dp[1][x]*d[x][j]
    ans+=dp[2][x]*d[x][k]
  fans=min(fans,ans)
print(fans)

Submission status: Accepted

Solution code:
import itertools

N,C =map(int,input().split())
D = [0]+[[0]+list(map(int,input().split())) for i in range(C)]

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

grids = [[],[],[]]#振り分ける
for i in range(N):
    for j in range(N):
        grids[(i+j)%3].append(c[i][j])

iwa = [[0]*(C+1) for i in range(3)]#grids[i]を色jにした時の違和感

for i in range(3):
    for j in range(1,C+1,1):
        for k in range(len(grids[i])):
            iwa[i][j]+=D[grids[i][k]][j]

ans = float("inf")
for bits in itertools.permutations(list(range(1,C+1)),3):
    tmpans = 0
    for i in range(3):
        tmpans +=iwa[i][bits[i]]
    ans = min(tmpans,ans)

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 i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in permutations(range(C),3):
	tmp=0
	for i in range(3):
		for j in range(C):
			tmp+=a[i][j]*d[j][v[i]]
	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)]
c = [list(map(int,input().split())) for _ in range(n)]

num = []
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        else:
            for k in range(C):
                if i == k or j == k:
                    continue
                else:
                    num.append((i,j,k))
                    
col = [[0]*C for _ in range(3)]

for i in range(n):
    for j in range(n):
        x = c[i][j]-1
        y = (i+j) % 3
        
        col[y][x] += 1
    
ans = 1145141919810
for ll in num:
    a = 0
    for i in range(3):
        for j in range(C):
            a += col[i][j] * d[j][ll[i]]
            
    ans = min(ans,a)
    
print(ans)

Submission status: Accepted

Solution code:
# D - Good Grid

from collections import defaultdict
import itertools

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

# MOD3の世界で0,1,2ごとに、最初の値の数をカウントしておく
dict_c = [defaultdict(int) for _ in range(3)]
for i in range(N):
    c = list(int(x) for x in input().split())
    for j in range(N):
        dict_c[(i+j)%3][c[j]-1] += 1

# ここからは全探索。
# 0, 1, 2の各配列に対して、全ての色を試す(C**3)
list_C = list(range(C))
ans = 10**18
for (p, q, r) in itertools.permutations(list_C, 3):
    tmp = 0
    for i, j in enumerate((p, q, r)):
        for m, n in dict_c[i].items():
            tmp += D[m][j] * n
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
D=[list(map(int,input().split())) for i in range(C)]
A=[list(map(int,input().split())) for i in range(N)]
X=[[0]*C for i in range(3)]
for c in range(C):
  for i in range(N):
    for j in range(N):
      X[(i+j)%3][c]+=D[A[i][j]-1][c]
P=10**20
for i in range(C):
  for j in range(C):
    for k in range(C):
      if len(set([i,j,k]))==3:
        P=min(P,X[0][i]+X[1][j]+X[2][k])
print(P)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, C = mi()
D = li2(C)
S = li2(N)

table = dp2(0, C, 3)
'''
#for num in range(3):
    #for start in range(num, N, 3):
        for color in range(C):
            i = 0
            j = start
            print(i, j)
            while True:
                table[num][color] += D[S[i][j]-1][color]
                if j < 1 or i >= N:
                    break
                j -= 1
                i += 1
'''
for i in range(N):
    for j in range(N):
        for color in range(C):
            table[(i+j)%3][color] += D[S[i][j]-1][color]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


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

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

    for y in range(N):
        for x in range(N):
            d = grid[(x + y + 2) % 3]
            d[c[y][x]] += 1

    comb = itertools.permutations(range(1, C + 1), 3)

    ans = 10**9 + 7
    for com in comb:
        iwa = 0
        for i in range(3):
            n_c = com[i]
            for k, v in grid[i].items():
                iwa += D[k - 1][n_c - 1] * v
        ans = min(ans, iwa)

    print(ans)


if __name__ == '__main__':
    main()

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

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

for i in range(N):
  for j in range(N):
    tmp=(i+j)%3
    
    for d in range(C):
      grid[tmp][d]+=D[c[i][j]-1][d]
      
print(min([grid[0][x]+grid[1][y]+grid[2][z] for x in range(C) for y in range(C) for z in range(C) if x!=y and y!=z and z!=x]))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, C = getNM()
D = [getList() for i in range(C)]
maze = [getList() for i in range(N)]

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

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

ans = float('inf')
for vi in permutations([i for i in range(C)], 3):
    opt_0, opt_1, opt_2 = vi
    cnt = 0
    for i in range(C):
        cnt += lis[0][i] * D[i][opt_0]
        cnt += lis[1][i] * D[i][opt_1]
        cnt += lis[2][i] * D[i][opt_2]
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,C = IL()
D = ILL(C)

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

for i in range(N):
  temp = IL()
  for j in range(N):
    data[(i+j)%3][temp[j]-1] += 1

MIN = INF
for a in range(C):
  for b in range(C):
    for c in range(C):
      if (a-b)*(b-c)*(c-a):
        score = 0
        for j in range(C):
          score += D[j][a]*data[0][j]
          score += D[j][b]*data[1][j]
          score += D[j][c]*data[2][j]
        MIN = min(MIN,score)
print(MIN)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
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,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,c=MI()
colors=[LI() for i in range(c)]
grid=[LI() for i in range(n)]
lis0=[]
lis1=[]
lis2=[]
for i in range(n):
    for j in range(n):
        if (i+j)%3==0:
            lis0.append(grid[i][j]-1)
        elif (i+j)%3==1:
            lis1.append(grid[i][j]-1)
        else:
            lis2.append(grid[i][j]-1)
#print(grid)
c0=Counter(lis0)
c1=Counter(lis1)
c2=Counter(lis2)
ind=[i for i in range(c)]
mn=inf
for i in product(ind,repeat=3):
    ans=0
    if i[0]==i[1] or i[1]==i[2] or i[2]==i[0]:
        continue
    #print(i[0],i[1],i[2])
    for x in c0.keys():
        #print(x,i[0])
        ans+=c0[x]*colors[x][i[0]]
    for y in c1.keys():
        #print(y,i[1])
        ans+=c1[y]*colors[y][i[1]]
    for z in c2.keys():
        #print(z,i[2])
        ans+=c2[z]*colors[z][i[2]]
    if ans<mn:
        mn=ans
print(mn)

Submission status: Accepted

Solution code:
n , c = map(int,input().split())
iwaka = [list(map(int,input().split())) for i in range(c)]
masu = [list(map(int,input().split())) for i in range(n)]
amari = [{} for i in range(3)]

for i in range(n):
    for j in range(n):
        amari[(i+j)%3][masu[i][j]] = amari[(i+j)%3].get(masu[i][j],0) + 1

kouho = []
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                kouho.append((i+1,j+1,k+1))
ans = 10**9
for p in kouho:
    cou = 0
    for i in range(3):
        for k , v in amari[i].items():
            cou += iwaka[k-1][p[i]-1]*v
    ans = min(ans,cou)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    mod = [defaultdict(int), defaultdict(int), defaultdict(int)]
    for i in range(N):
        c = list(map(int, input().split()))
        for j in range(N):
            mod[(i + j) % 3][c[j] - 1] += 1
    #print(mod)
    
    hq = [[], [], []]
    for i in range(3):
        for y in range(C):
            diff = 0
            for x in mod[i]: diff += D[x][y] * mod[i][x]
            heappush(hq[i], (diff, y))
    #print(hq)
    
    cand = [[], [], []]
    for i in range(3):
        for _ in range(3):
            diff, color = heappop(hq[i])
            cand[i].append((diff, color))
    #print(cand)
    ans = 10**18
    for p in cand[0]:
        for q in cand[1]:
            for r in cand[2]:
                if p[1] == q[1] or q[1] == r[1] or r[1] == p[1]: continue
                ans = min(ans, p[0] + q[0] + r[0])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,nc=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(nc)]
c=[list(map(int,input().split())) for _ in range(n)]
from collections import defaultdict
dct=defaultdict(int)
for x in range(n):
  for y in range(n):
    for ci in range(nc):
      if (ci,(x+y)%3) in dct:
        dct[(ci,(x+y)%3)]+=d[c[x][y]-1][ci]
      else:
        dct[(ci,(x+y)%3)]=d[c[x][y]-1][ci]

def func(c1,c2,c3): #(i+j)%=0をc1に、=1をc2に、=2をc3に塗るときの違和感
  ret=dct[(c1,0)]+dct[(c2,1)]+dct[(c3,2)]
  return ret
ans=float('inf')
for c1 in range(nc):
  for c2 in range(nc):
    if c1==c2:continue
    for c3 in range(nc):
      if c1==c3 or c2==c3:continue
      ans=min(ans,func(c1,c2,c3))
print(ans)
#print(dct)