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 itertools

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()))
    
hist=[[0]*C for i in range(3)]#hist[i][j]は余りiのマスにj色のマスがいくつあるか
    
    
for i in range(N):
    for j in range(N):
        rem=(i+j+2)%3
        hist[rem][c[i][j]-1]+=1
    
ans=10**10
for cset in itertools.permutations(range(C), 3):
    temp=0
    for i in range(3):
        for j in range(C):
            temp+=hist[i][j]*D[j][cset[i]]
    ans=min(ans,temp)
    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, C = [int(_) for _ in input().split()]

D = [[int(_) for _ in input().split()] for _ in range(C)]

cnt = [Counter() for _ in range(3)]
for i in range(N):
    tmp = [int(_) for _ in input().split()]
    for j in range(N):
        idx = (i + 1 + j + 1) % 3
        cnt[idx][tmp[j] - 1] += 1

ans = 1e12
for x in range(C):
    for y in range(C):
        if x == y: continue
        for z in range(C):
            if x == z or y == z: continue
            tmp = 0
            for i in range(C):
                tmp += cnt[0][i] * D[i][x]
                tmp += cnt[1][i] * D[i][y]
                tmp += cnt[2][i] * D[i][z]
            ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, C = [int(_) for _ in input().split()]

D = [[int(_) for _ in input().split()] for _ in range(C)]

cnt = [Counter() for _ in range(3)]
for i in range(N):
    tmp = [int(_) for _ in input().split()]
    for j in range(N):
        idx = (i + 1 + j + 1) % 3
        cnt[idx][tmp[j] - 1] += 1

vals = [[0] * C for _ in range(3)]
for i in range(3):
    for j in range(C):
        a = cnt[i][j]
        if a <= 0: continue
        for k in range(C):  # k 色に揃えるコスト
            vals[i][k] += D[j][k] * a
    # print(vals[i])

ans = 1e12
for x in range(C):
    for y in range(C):
        if x == y: continue
        for z in range(C):
            if x == z or y == z: continue
            ans = min(ans, vals[0][x] + vals[1][y] + vals[2][z])
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,c = map(int,input().split())
    d = [list(map(int,input().split())) for i in range(c)]
    cmat = [list(map(int,input().split())) for i in range(n)]
    t = [[0]*c for i in range(3)]
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            t[(i+j)%3][cmat[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:
                        tmpans = 0
                        for l in range(c):
                            tmpans += d[l][i]*t[0][l]+d[l][j]*t[1][l]+d[l][k]*t[2][l]
                        ans = min(ans,tmpans)

    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,c = map(int,input().split())
    d = [list(map(int,input().split())) for i in range(c)]
    cmat = [list(map(int,input().split())) for i in range(n)]
    t = [[0]*c for i in range(3)]
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            t[(i+j)%3][cmat[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:
                        tmpans = 0
                        for l in range(c):
                            tmpans += d[l][i]*t[0][l]+d[l][j]*t[1][l]+d[l][k]*t[2][l]
                        ans = min(tmpans,ans)
    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,c = map(int,input().split())
    d = [list(map(int,input().split())) for i in range(c)]
    cmat = [list(map(int,input().split())) for i in range(n)]
    t = [[0]*c for i in range(3)]
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            t[(i+j)%3][cmat[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:
                        sub = 0
                        for l in range(c):
                            sub += d[l][i]*t[0][l]+d[l][j]*t[1][l]+d[l][k]*t[2][l]
                        ans = min(sub,ans)
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,c = map(int,input().split())
    d = [list(map(int,input().split())) for i in range(c)]
    cmat = [list(map(int,input().split())) for i in range(n)]
    t = [[0]*c for i in range(3)]
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            t[(i+j)%3][cmat[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:
                        subans = 0
                        for l in range(c):
                            subans += d[l][i]*t[0][l]+d[l][j]*t[1][l]+d[l][k]*t[2][l]
                        ans = min(subans,ans)
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
#import numpy as np
n,c=list(map(int,input().split()))
difference=[list(map(int,input().split())) for _ in range(c)]
base=[list(map(int,input().split())) for _ in range(n)]
#tmp_d=np.array(difference)
#tmp_b=np.array(base)
cal_col=[[0 for _ in range(c)] for _ in range(3)]
for i in range(n):
    for j in range(n):
        cal_col[(i+j)%3][base[i][j]-1]+=1
ans=float("inf")
for f_i in range(c):
    for s_i in range(c):
        for t_i in range(c):
            if f_i==s_i or f_i==t_i or s_i ==t_i:
                continue
            cal_val=0
            for n_i in range(c):
                cal_val+=difference[n_i][f_i]*cal_col[0][n_i]
                cal_val+=difference[n_i][s_i]*cal_col[1][n_i]
                cal_val+=difference[n_i][t_i]*cal_col[2][n_i]
            ans=min(ans,cal_val)

print(ans)

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(C, D, F, r):
    import collections

    L = []
    for i, f0 in enumerate(F):
        for j, c in enumerate(f0):
            if (i + j) % 3 != r:
                continue
            L.append(c - 1)
    d = collections.Counter(L)
    res = []
    for x in range(C):
        tmp = 0
        for y, v in d.items():
            tmp += D[y][x] * v
        
        res.append((x, tmp))
    
    res.sort(key=lambda l: l[1])
    return res[:3]


def main():
    N, C = read_values()
    D = [read_list() for _ in range(C)]
    F = [read_list() for _ in range(N)]

    r0 = f(C, D, F, 0)
    r1 = f(C, D, F, 1)
    r2 = f(C, D, F, 2)
    res = 10 ** 18
    for c0, v0 in r0:
        for c1, v1 in r1:
            if c0 == c1:
                continue
            for c2, v2 in r2:
                if c2 in (c0, c1):
                    continue
                res = min(res, v0 + v1 + v2)
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
import itertools

def ddprint(x):
  if DBG:
    print(x)

n,c = inm()
d = []
e = []
for i in range(c):
    d.append(inl())
for i in range(n):
    cc = inl()
    cc2 = [x-1 for x in cc]
    e.append(cc2)

s = [ [0]*c for i in range(3) ]
for i in range(n):
    for j in range(n):
        s[(i+j)%3][e[i][j]] += 1
mn = BIG
pm = itertools.permutations(list(range(c)), 3)
for p in pm:
    sm = 0
    for i in range(3):
        for j in range(c):
            sm += s[i][j]*d[j][p[i]]
    mn = min(mn,sm)
print(mn)

Submission status: Accepted

Solution code:

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

grid = [[0 for j in range(c+1)] for i in range(3)]
for i in range(n):
    for j,cc in enumerate(map(int, input().split())):
        k = j
        grid[(i+j)%3][cc] += 1

ans = float('INF')

for i in range(1,c+1):
    for j in range(1,c+1):
        if i == j:
            continue
        for k in range(1,c+1):
            if i == k or j == k:
                continue
            cost = 0
            for a in range(1,c+1):
                # print(int(d[a-1][i-1]), grid[0][a], int(d[a-1][j-1]), grid[1][a], int(d[a-1][k-1]), grid[2][a])
                cost += d[a-1][i-1] * grid[0][a] + d[a-1][j-1] * grid[1][a] + d[a-1][k-1] * grid[2][a]
            
            if cost < ans:
                # print(i,j,k,cost)
                ans = cost

print(int(ans))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, C = LI()
    D = []
    c = []
    m0 = collections.defaultdict(int)
    m1 = collections.defaultdict(int)
    m2 = collections.defaultdict(int)
    for _ in range(C):
        D.append(LI())
    for __ in range(N):
        c.append(LI_())
    for row in range(N):
        for col in range(N):
            color = c[row][col]
            if (row + col) % 3 == 0:
                m0[color] += 1
            elif (row + col) % 3 == 1:
                m1[color] += 1
            else:
                m2[color] += 1
    min_cnt = inf
    for c0 in range(C):
        for c1 in range(C):
            for c2 in range(C):
                cnt = 0
                if c0 == c1 or c1 == c2 or c2 == c0:
                    continue

                for orig_c0, num in m0.items():
                    cnt += (D[orig_c0][c0] * num)

                for orig_c1, num in m1.items():
                    cnt += (D[orig_c1][c1] * num)

                for orig_c2, num in m2.items():
                    cnt += (D[orig_c2][c2] * num)
                min_cnt = min(min_cnt, cnt)
    print(min_cnt)
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools

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

N, C = lr()
D = np.array([lr() for _ in range(C)])

grid = [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
        three[remain][grid[i][j]-1] += 1

three = np.array(three)
answer = 10 ** 10
for x, y, z in itertools.permutations(range(C), 3):
    # three[0]をxの色にする
    result = 0
    for i in range(3):
        s = [x, y, z][i]
        result += (three[i] * D[:, s]).sum()
    if result < answer:
        answer = result

print(answer)
# 35

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        lic[i][j] -= 1

dict0 = {}
dict1 = {}
dict2 = {}
li0 = []
li1 = []
li2 = []

for i in range(n):
    for j in range(n):
        color = lic[i][j]
        if (i+j) % 3 == 0:
            if color in dict0:
                dict0[color] += 1
            else:
                dict0[color] = 1
                li0.append(color)
        elif (i+j) % 3 == 1:
            if color in dict1:
                dict1[color] += 1
            else:
                dict1[color] = 1
                li1.append(color)
        else:
            if color in dict2:
                dict2[color] += 1
            else:
                dict2[color] = 1
                li2.append(color)


ans = 10 ** 10

for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                ans_tmp = 0
                for ii in li0:
                    if ii != i:
                        ans_tmp += d[ii][i] * dict0[ii]
                for jj in li1:
                    if jj != j:
                        ans_tmp += d[jj][j] * dict1[jj]
                for kk in li2:
                    if kk != k:
                        ans_tmp += d[kk][k] * dict2[kk]
                ans = min(ans, ans_tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    n,c = inpm()
    D = inpll(c)
    a = inpll(n)
    dic1 = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    for i in range(n):
        for j in range(n):
            if (i+j)%3 == 0:
                dic1[a[i][j]] += 1
            elif (i+j)%3 == 1:
                dic2[a[i][j]] += 1
            elif (i+j)%3 == 2:
                dic3[a[i][j]] += 1
    ANS = 10**10
    if n == 1:
        for e in range(c):
            x = e
            ans = 0
            for color1 in dic1:
                if color1 == x+1:
                    continue
                ans += dic1[color1] * D[color1-1][x]
            ANS = min(ANS,ans)
        print(ANS)
        return
    for e in permutations(range(c),3):
        [x, y, z] = e
        ans = 0
        for color1 in dic1:
            if color1 == x+1:
                continue
            ans += dic1[color1] * D[color1-1][x]
        for color2 in dic2:
            if color2 == y+1:
                continue
            ans += dic2[color2] * D[color2-1][y]
        for color3 in dic3:
            if color3 == z+1:
                continue
            ans += dic3[color3] * D[color3-1][z]
        ANS = min(ANS,ans)
    print(ANS)            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 色のパターン 30*29*28 == 24360
# 全部試すだけ

N, C = list(map(int, sys.stdin.buffer.readline().split()))
D = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(C)]
S = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

D = np.array(D, dtype=int)
S = np.array(S, dtype=int) - 1

md = np.zeros((N, N), dtype=int)
md += np.arange(N, dtype=int)
md += np.arange(N, dtype=int)[:, None]
md %= 3

# s += D[S[md == 0], colors[0]].sum()
# s += D[S[md == 1], colors[1]].sum()
# s += D[S[md == 2], colors[2]].sum()

# costs[d][c]: md == d の場所を c に変えるときのコスト
costs = [[0] * C for _ in range(3)]
for d in range(3):
    for c in range(C):
        # md == d の場所を c に変えるときのコスト
        costs[d][c] = D[S[md == d], c].sum()

ans = INF
for colors in itertools.permutations(range(C), r=3):
    ans = min(ans, costs[0][colors[0]] + costs[1][colors[1]] + costs[2][colors[2]])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

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

colors = defaultdict(lambda : defaultdict(int))

for h in range(1, N + 1):
    for w, c in enumerate(map(int, input().split()), start=1):
        colors[(h + w) % 3][c] += 1

cost = [[None] * C for _ in range(3)]

for i in range(3):
    for color in range(1, C + 1):
        cnt = 0
        for c, k in colors[i].items():
            cnt += D[c - 1][color - 1] * k
        cost[i][color - 1] = cnt

ans = 10**10
for cs in product(range(C), repeat=3):
    if len(set(cs)) == 3:
        cnt = 0
        for i, c in enumerate(cs):
            cnt += cost[i][c]
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,c=map(int,input().split())
ld=[list(map(int,input().split())) for i in range(c)]
lc=[list(map(int,input().split())) for i in range(n)]
ct=[[0 for i in range(c)] for i in range(3)]
for i in range(n):
  for j in range(n):
    ct[(i+j+2)%3][lc[i][j]-1]+=1
L=list(itertools.permutations([i for i in range(c)],3))

ans=[]
for i in range(len(L)):
  ct2=0
  for j in range(3):
    for k in range(c):
      ct2+=ld[k][L[i][j]]*ct[j][k]
  ans.append(ct2)
print(min(ans))

Submission status: Accepted

Solution code:
from itertools import product
from collections import Counter
N, C = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(C)]

color = [[] for _ in range(3)]
for i in range(N):
    inp = tuple(map(int, input().split()))
    for j, c in enumerate(inp):
        color[(i + j) % 3].append(c-1)

cnt = [Counter(color[i]) for i in range(3)]


def point(d, col):
    res = 0
    for k, v in d.items():
        res += D[k][col] * v
    return res


ans = 10**9
for xyz in product(range(C), repeat=3):
    if len(set(xyz)) != 3:
        continue
    tmp = sum(point(cnt[i], xyz[i]) for i in range(3))
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    def fcalc(cl,c):
        f = 0
        for i in cl.keys():
            if i != c:
                f += d[i-1][c-1]*cl[i]
        return f
                
    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)]
    clist = [defaultdict(int),defaultdict(int),defaultdict(int)]
    for i in range(n):
        for j in range(n):
            clist[(i+j+2)%3][color[i][j]] += 1
    ans_list = []
    for i in range(1,c+1):
        f1 = fcalc(clist[0],i)
        for j in range(1,c+1):
            if i != j:
                f2 = fcalc(clist[1],j)
                for k in range(1,c+1):
                    if j != k and k != i:
                        f3 = fcalc(clist[2],k)
                        ans_list.append(f1+f2+f3)
    print(min(ans_list))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

table = [collections.defaultdict(int) for i in range(3)]

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


ans = 10**9
for i in range(C):
    tmp = 0
    for x in table[0]:
        tmp += D[x][i]*table[0][x]

    for j in range(C):
        if i == j:
            continue
        tmp2 = 0
        for x in table[1]:
            tmp2 += D[x][j]*table[1][x]
        for k in range(C):
            if i == k or j == k:
                continue
            tmp3 = 0
            for x in table[2]:
                tmp3 += D[x][k]*table[2][x]

            ans = min(ans, tmp+tmp2+tmp3)
print(ans)

Submission status: Accepted

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

x0=[0]*c #余りが0のグループで、元の色が1～Cまでのやつがそれぞれ何個あったか記録
x1=[0]*c
x2=[0]*c


for i in range(n):
  for j in range(n):
    num=(i+j+2)%3
    if num==0:
      x0[cli[i][j]-1]+=1
    elif num==1:
      x1[cli[i][j]-1]+=1
    elif num==2:
      x2[cli[i][j]-1]+=1

import itertools
ans=float("inf")
rng=list(range(c))
for x,y,z in itertools.permutations(rng, 3):
  temp=0
  for j in range(c): #1～cまでの色それぞれについて、個数*x,y,zの遷移コストを求める
    temp+=x0[j]*d[j][x]
    temp+=x1[j]*d[j][y]
    temp+=x2[j]*d[j][z]
  #print(temp)
  ans=min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
#他人のを参考に手直し
import numpy as np
import itertools
import sys
input = sys.stdin.readline  #文字列入力では注意！

N,C = map(int,input().split())
D = np.array([list(map(int,input().split()))for _ in range(C)], dtype=np.int64)
c = np.array([list(map(int,input().split()))for _ in range(N)], dtype=np.int64)
c0 = np.zeros(C,dtype=np.int64)
c1 = np.zeros(C,dtype=np.int64)
c2 = np.zeros(C,dtype=np.int64)
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            c0[c[i,j]-1] += 1
        if (i+j)%3 == 1:
            c1[c[i,j]-1] += 1
        if (i+j)%3 == 2:
            c2[c[i,j]-1] += 1
# c0~2はXの情報
r = np.arange(C)	#先にnp.sumしておく
s0 = np.sum(D[:,r]*c0[:,None],axis=0)
s1 = np.sum(D[:,r]*c1[:,None],axis=0)
s2 = np.sum(D[:,r]*c2[:,None],axis=0)

lis = itertools.permutations(range(C),3)
ans = float("inf")
for l0,l1,l2 in lis:    # l0~2はYの情報
    tmp = s0[l0]+s1[l1]+s2[l2]
    ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import sys
input = sys.stdin.readline  #文字列入力では注意！

N,C = map(int,input().split())
D = np.array([list(map(int,input().split()))for _ in range(C)], dtype=np.int64)
c = np.array([list(map(int,input().split()))for _ in range(N)], dtype=np.int64)
c0 = np.zeros(C,dtype=np.int64)
c1 = np.zeros(C,dtype=np.int64)
c2 = np.zeros(C,dtype=np.int64)
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            c0[c[i,j]-1] += 1
        if (i+j)%3 == 1:
            c1[c[i,j]-1] += 1
        if (i+j)%3 == 2:
            c2[c[i,j]-1] += 1
# c0~2はXの情報
lis = itertools.permutations(range(C),3)
ans = float("inf")
for l0,l1,l2 in lis:    # l0~2はYの情報
    tmp = np.sum(D[:,l0]*c0+D[:,l1]*c1+D[:,l2]*c2)
    ans = min(ans,tmp)
print(ans)