Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Here, X \% Y represents X modulo Y.

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

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

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

Constraints

1 \leq N \leq 500

3 \leq C \leq 30

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

3

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

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

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

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

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

Sample Input 2

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

Sample Output 2

428



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


Sample output:
3

Submission status: Accepted

Solution code:
from collections import Counter
N,C = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(C)]
color = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

# 3 groups
mod3 = {0:[], 1:[], 2:[]}
for i in range(N):
    for j in range(N):
        m = (i+j)%3
        mod3[m].append(color[i][j])

cnts = [Counter(mod3[i]) for i in range(3)]

ans = float('inf')
for p1 in range(C):
    for p2 in range(C):
        if p2==p1: continue
        for p3 in range(C):
            if p3==p1 or p3==p2: continue
            p = [p1,p2,p3]
            cond = 0
            for i in range(3):
                for col in cnts[i].keys():
                    cond += cnts[i][col]*cost[col][p[i]]
            ans = min(ans, cond)
            #print(cond, p)
print(ans)

Submission status: Accepted

Solution code:
N,C = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(C)]
color = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

mod3 = {0:[], 1:[], 2:[]}
for i in range(N):
    for j in range(N):
        m = (i+j)%3
        mod3[m].append(color[i][j])
        
from collections import Counter
from itertools import combinations, permutations
cnts = [Counter(mod3[i]) for i in range(3)]
# print(cnts)
ans = float('inf')
for comb in combinations(range(C), 3):
    for p in permutations(comb):
        cond = 0
        for i in range(3):
            for col in cnts[i].keys():
                cond += cnts[i][col]*cost[col][p[i]]
        ans = min(ans, cond)
        #print(cond, p)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    dp = [inf for i in range(n + 1)]
    ans = [1]
    x = 6
    while x <= n:
        ans.append(x)
        x = x * 6
    x = 9
    while x <= n:
        ans.append(x)
        x = x * 9
    ans.sort()
    for i in ans:
        dp[i] = 1
    for i in range(1, n + 1):
        if not i in ans:
            a = bisect.bisect_left(ans, i)
            for k in range(a):
                #print(i,ans[k], a)
                dp[i] = min(dp[i - ans[k]] + 1, dp[i])
    print(dp[n])

    return

#D
def D():
    n, c = LI()
    D = LIR(c)
    C = LIR_(n)
    CL = list(itertools.permutations(range(c), 3))
    ans = inf
    amari0 = [0 for i in range(30)]
    amari1 = amari0[::1]
    amari2 = amari0[::1]
    for y in range(n):
        for x in range(n):
            amari = (x + y) % 3
            if amari == 0:
                amari0[C[y][x]] += 1
            if amari == 1:
                amari1[C[y][x]] += 1
            if amari == 2:
                amari2[C[y][x]] += 1
    for c0, c1, c2 in CL:
        ansb = 0
        for i in range(c):
            ansb += D[i][c0] * amari0[i]
            ansb += D[i][c1] * amari1[i]
            ansb += D[i][c2] * amari2[i]
        ans = min(ans, ansb)

            
    print(ans)

    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    ans = float("inf")
    for i in range(n+1):
        m = 0
        k = i
        while k > 0:
            m += k%6
            k //= 6
        k = n-i
        while k > 0:
            m += k%9
            k //= 9
        ans = min(ans,m)
    print(ans)
#D
def D():
    n,C = LI()
    f = LIR(C)
    c = LIR(n)
    d = [defaultdict(int) for i in range(3)]
    for i in range(n):
        for j in range(n):
            d[(i+j+2)%3][c[i][j]-1] += 1
    ans = float("inf")
    for i in range(C):
        for j in range(C):
            if i != j:
                for k in range(C):
                    if k != i and k != j:
                        m = 0
                        for a in d[0].keys():
                            m += d[0][a]*f[a][i]
                        for a in d[1].keys():
                            m += d[1][a]*f[a][j]
                        for a in d[2].keys():
                            m += d[2][a]*f[a][k]
                        ans = min(ans,m)
    print(ans)


#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
D=[]
for i in range(C):
    d=list(map(int,input().split()))
    D.append(d)
    
mod0=[0 for i in range(C)]
mod1=[0 for i in range(C)]
mod2=[0 for i in range(C)]

Arr=[]
for i in range(N):
    c=list(map(int,input().split()))
    Arr.append(c)
    
for i in range(N):
    for j in range(N):
        if (i+j)%3==0:
            mod0[Arr[i][j]-1]+=1
        elif (i+j)%3==1:
            mod1[Arr[i][j]-1]+=1
        elif (i+j)%3==2:
            mod2[Arr[i][j]-1]+=1

MOD0=[]
MOD1=[]
MOD2=[]

for i in range(C):
    cnt0=0
    cnt1=0
    cnt2=0
    for j in range(C):
        cnt0+=mod0[j]*D[j][i]
        cnt1+=mod1[j]*D[j][i]
        cnt2+=mod2[j]*D[j][i]
    MOD0.append(cnt0)
    MOD1.append(cnt1)
    MOD2.append(cnt2)
ans=10**15
for a in range(len(MOD0)):
    for b in range(len(MOD0)):
        for c in range(len(MOD0)):
            if a==b or b==c or c==a:
                pass
            else:
                if MOD0[a]+MOD1[b]+MOD2[c]<ans:
                    ans=MOD0[a]+MOD1[b]+MOD2[c]
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()))
mat=[[] for i in range(n)]
cl=[[] for i in range(3)]
for i in range(n):
    mat[i]=list(map(int,input().split()))
for i in range(n):
    for j in range(n):
        if (i+j)%3==0:
            k=0
        elif (i+j)%3==1:
            k=1
        else:
            k=2
        cl[k].append(mat[i][j])
q=[[0 for i in range(c)] for i in range(3)]
for i in range(c):
    for j in range(3):
        for k in cl[j]:
            q[j][i]+=d[k-1][i]            
mi=10**9
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i!=j and j!=k and k!=i:
                s=q[0][i]+q[1][j]+q[2][k]
                if s<mi:
                    mi=s
print(mi)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
2 3
0 1 1
1 0 1
1 4 0
1 2
3 3
'''

test_data2 = '''\
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
'''

test_data3 = '''\

'''
td_num=2

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        N,C=map(int,f.readline().split())
        c=[[0 for j in range(C)] for i in range(3)]
        D=[[0 for i in range(C)] for j in range(C)]
        for i in range(C):
            D[i]=[int(x) for x in f.readline().split()]
        for x in range(N):
            y=0
            for j in f.readline().split():
                c[(x+y)%3][int(j)-1]+=1
                y+=1
        # End Input code ---------------------------------------
else:
    if 0==0:
        # Start Input code ---------------------------------------
        N,C=map(int,input().split())
        c=[[0 for j in range(C)] for i in range(3)]
        D=[[0 for i in range(C)] for j in range(C)]
        for i in range(C):
            D[i]=[int(x) for x in input().split()]
        for x in range(N):
            y=0
            for j in input().split():
                c[(x+y)%3][int(j)-1]+=1
                y+=1
        # End Input code ---------------------------------------

St=[[0 for i in range(3)] for j in range(C)]
ans=10**20
for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            cc=0
            dd=0
            for i in range(C):
                cc+=c[0][i]*D[i][c1]
                cc+=c[1][i]*D[i][c2]
                cc+=c[2][i]*D[i][c3]
                
                dd+=c[0][i]*D[c1][i]
                dd+=c[1][i]*D[c2][i]
                dd+=c[2][i]*D[c3][i]
            if len(set([c1,c2,c3]))==3:
                ans=min(ans,cc)
            #print(ans,c,D)
#print('N,C=',N,C,'D=',D,'c=',c,'St=',St)
print(ans)

Submission status: Accepted

Solution code:
def read():
    return raw_input()


def write(message):
    import sys
    print message
    sys.stdout.flush()


if __name__ == '__main__':
    n, c = map(int, read().split())
    # n < 500
    # 3 < c < 30
    D = []
    C = []
    for _ in range(c):
        D.append(map(int, read().split()))
    for _ in range(n):
        C.append(map(int, read().split()))

    import numpy as np
    g = [[],[],[]]
    for i in range(n):
        for j in range(n):
            g[(i+j)% 3].append(C[i][j] - 1)
    p0 = sorted([(tc, sum(D[d][tc] for d in g[0])) for tc in range(c)], key=lambda x:x[1])[:3]
    p1 = sorted([(tc, sum(D[d][tc] for d in g[1])) for tc in range(c)], key=lambda x:x[1])[:3]
    p2 = sorted([(tc, sum(D[d][tc] for d in g[2])) for tc in range(c)], key=lambda x:x[1])[:3]

    min_w = p0[2][1] + p1[2][1] + p2[2][1]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                w = p0[i][1] + p1[j][1] + p2[k][1]
                colors = (p0[i][0], p1[j][0], p2[k][0])
                if len(set(colors)) == 3 and w < min_w:
                    min_w = w
    write(min_w)

Submission status: Accepted

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

#計算しやすいよう、色Indexは全部-1する
for y in range(N):
    for x in range(N):
        C_map[y][x] -= 1

#
col_lines = [[0 for _ in range(C)] for _ in range(3)]
for y in range(N):
    for x in range(N):
        idx = (x + y) % 3
        col_lines[idx][C_map[y][x]] += 1

# 各行ごとにC色すべてに変更するときのコストを求める
def calc_cost(line, target_color):
    cost = 0
    for col, count in enumerate(line):
        cost += D[col][target_color] * count
    return cost

#[cost, 色] を覚える
costs = [[0 for _ in range(C)] for _ in range(3)]
for i in range(3):
    for c in range(0, C):
        costs[i][c] = [calc_cost(col_lines[i], c), c]
    costs[i].sort(key=lambda x: x[0])

# 貪欲法的に探す。i1, i2, i3 は各costsのIndex
# 他と色がかぶったらIndexをずらして調査、そうでなければOK
def find_min(i1, i2, i3):
    if i1 >= 3 or i2 >= 3 or i3 >= 3: #3色でいいので、4つ以上奥にいく必要がない
        return 100000000000000

    line1 = costs[0]
    line2 = costs[1]
    line3 = costs[2]
    if i1 >= len(line1) or i2 >= len(line2) or i3 >= len(line3):
        return 1000000000000
    c1 = line1[i1][1]
    c2 = line2[i2][1]
    c3 = line3[i3][1]
    if c1 == c2 and c1 == c3:
        return min(
            find_min(i1 + 1, i2, i3),
            find_min(i1, i2 + 1, i3),
            find_min(i1, i2, i3 + 1)
        )
    if c1 == c2:
        return min(
            find_min(i1 + 1, i2, i3),
            find_min(i1, i2 + 1, i3),
        )
    if c1 == c3:
        return min(
            find_min(i1 + 1, i2, i3),
            find_min(i1, i2, i3 + 1)
        )
    if c2 == c3:
        return min(
            find_min(i1, i2 + 1, i3),
            find_min(i1, i2, i3 + 1)
        )
    return line1[i1][0] + line2[i2][0] + line3[i3][0]

print(find_min(0, 0, 0))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
G = [list(map(int, input().split())) for _ in range(N)]
GC = []
GC.append([0]*C)
GC.append([0]*C)
GC.append([0]*C)
for y in range(N):
  for x in range(N):
    GC[(y+x)%3][G[y][x]-1] += 1
ans = 1000000000
for a in range(C):
  for b in range(C):
    if a == b:
      continue
    for c in range(C):
      if a == c or b == c:
        continue
      cost = 0
      for i in range(C):
        cost += GC[0][i]*D[i][a]
        cost += GC[1][i]*D[i][b]
        cost += GC[2][i]*D[i][c]
      ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]
c_set = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        c_set[(i+j)%3][c[i][j]-1] += 1
ans = 1e9
for c_1 in range(C):
    for c_2 in range(C):
        for c_3 in range(C):
            if c_1==c_2 or c_1==c_3 or c_2==c_3:
                continue
            c_list = [c_1,c_2,c_3]
            k = 0
            for i in range(C):
                for j in range(3):
                    k += d[i][c_list[j]-1]*c_set[j][i]
            ans = min(ans,k)
print(ans)

Submission status: Accepted

Solution code:
import itertools


def get_discomfort(group_dic, color, D):
    s = 0
    for c, num in group_dic.items():
        s += D[c - 1][color - 1] * num
    return s


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


from collections import Counter


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

for i in range(N):
    c = list(map(int, input().split()))
    for j in range(N):
        grids[(i + j) % 3][c[j]] += 1


ans = float("inf")
for colors in itertools.permutations(list(range(C)), 3):
    colors = list(colors)
    s = 0
    for i, c in enumerate(colors):
        s += get_discomfort(grids[i], c, D)
    ans = min(ans, s)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]  # 違和感
G = [list(map(lambda x: int(x) - 1, input().split())) for i in range(N)]


# mod3でグループ分け
group = [[] for i in range(3)]
for i in range(N):
    for j in range(N):
        group[(i + j) % 3].append(G[i][j])


# 各グループについて色cに変更する際にかかるコスト
cost = [[0] * C for i in range(3)]
for c in range(C):
    for i, g in enumerate(group):
        tmp_cost = sum([D[gi][c] for gi in g if gi != c])
        cost[i][c] = tmp_cost


# 色のあてはめ方を全探索
ans = float('inf')
for c0, c1, c2 in permutations(range(C), r=3):
    tmp_ans = cost[0][c0] + cost[1][c1] + cost[2][c2]
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

Solution code:
def good_grid(N: int, C: int, D: list, c: list) -> int:
    # (i+j) % 3 ごとに色の出現頻度を取る
    freqs = [{}, {}, {}]
    for i, row in enumerate(c):
        for j, e in enumerate(row):
            r = (i + j) % 3
            freq = freqs[r]
            if e not in freq:
                freq[e] = 0
            freq[e] += 1

    # (i+j) % 3 ごとの色の出現頻度から他の色に変更した際の
    # 違和感を全探索
    discomforts = [[(-1, float('inf'))] * 3 for _ in range(3)]

    for freq, discomfort in zip(freqs, discomforts):
        for y in range(C):
            sum_d = sum(D[x - 1][y - 1] * f for x, f in freq.items())
            discomfort.append((y, sum_d))

    # (i+j) % 3 ごとに y の値が被らないように決定して
    # 全体の不快感を最小にする。
    min_dis = float('inf')
    for y1, v1 in discomforts[0]:
        for y2, v2 in discomforts[1]:
            for y3, v3 in discomforts[2]:
                if y1 == y2 or y2 == y3 or y3 == y1:
                    continue
                if v1 + v2 + v3 < min_dis:
                    min_dis = v1 + v2 + v3

    return min_dis


if __name__ == "__main__":
    N = 0
    C = 0
    N, C = map(int, input().split())
    D = [[int(s) for s in input().split()] for _ in range(C)]
    c = [[int(s) for s in input().split()] for _ in range(N)]
    ans = good_grid(N, C, D, c)
    print(ans)

Submission status: Accepted

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

r0 = deque()
r1 = deque()
r2 = deque()
for i in range(N):
    for j in range(N):
        rest = (i+1+j+1) % 3
        if rest == 0:
            r0.append(c[i][j]-1)
        elif rest == 1:
            r1.append(c[i][j]-1)
        else:
            r2.append(c[i][j]-1)
c0 = Counter(r0)
c1 = Counter(r1)
c2 = Counter(r2)
ans = 10**10
for p in permutations([i for i in range(C)], 3):
    point = 0
    point += sum([d[k][p[0]]* v for k, v in c0.items()])
    point += sum([d[k][p[1]]* v for k, v in c1.items()])
    point += sum([d[k][p[2]]* v for k, v in c2.items()])
    ans = min(ans, point)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
G = [list(map(int, input().split())) for _ in range(N)]
count_color = [[0 for _ in range(C+1)] for _ in range(3)]
for y in range(N):
  for x in range(N):
    count_color[(x+y)%3][G[y][x]] += 1
ans = 10**12
for colors in itertools.permutations(range(1, C+1), 3):
  iwakan = 0
  for mod in range(3):
    for c in range(1, C+1):
      iwakan += D[c-1][colors[mod]-1]*count_color[mod][c]
  if iwakan < ans:
    ans = iwakan
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,C=map(int,input().split())
D=[[int(i) for i in input().split()] for j in range(C)]
M=[[int(i) for i in input().split()] for j in range(N)]
ans=10**9
L=[defaultdict(int) for i in range(3)]

for i in range(N):
    for j in range(N):
        L[(i+j)%3][M[i][j]-1]+=1
#print(L)
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
            num=0
            for color,number in L[0].items():
                #num+=D[i][color]*number
                num += D[color][i] * number
                #print(num)
            for color,number in L[1].items():
                #num+=D[j][color]*number
                #print(num)
                num += D[color][j] * number
            for color,number in L[2].items():
                #num+=D[k][color]*number
                #print(num)
                num += D[color ][k] * number
            ans=min(ans,num)

            #print(ans,i,j,k)
#for color,number in L[0].items():
    #print(color,number)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product
N, C = map(int, input().split())
D = [None]
for _ in range(C):
    D.append([None] + list(map(int, input().split())))
c3 = [Counter() for _ in range(3)]
for i in range(N):
    c = list(map(int, input().split()))
    for j in range(3):
        c3[j].update(c[(j-i)%3::3])
dis3 = [[] for _ in range(3)]
for c, i in product(range(1, C + 1), range(3)):
    dis = 0
    for c0, cnt in c3[i].items():
        dis += D[c0][c] * cnt
    dis3[i].append(dis)
ans = 10 ** 9
for c0, c1 in product(range(C), repeat=2):
    if c0 == c1:
        continue
    tmp = dis3[0][c0] + dis3[1][c1]
    tmp += min(dis3[2][c2] for c2 in range(C) if c2 not in (c0, c1))
    if tmp < ans:
        ans = tmp

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

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


c_arr1 = []
c_arr2 = []
c_arr3 = []

for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0: 
            c_arr1.append(c_arr[i][j])
        if (i+j)%3 == 1: 
            c_arr2.append(c_arr[i][j])
        if (i+j)%3 == 2: 
            c_arr3.append(c_arr[i][j])

tmp = 1000*500*500

def cost(arr, aft):
    sum = 0
    for i in range(len(arr)):
        sum += D[arr[i]-1][aft]
    return sum

ans_arr1 = []
ans_arr2 = []
ans_arr3 = []

for l in range(C):
    ans_arr1.append(cost(c_arr1, l))
for l in range(C):
    ans_arr2.append(cost(c_arr2, l))
for l in range(C):
    ans_arr3.append(cost(c_arr3, l))


ans_arr = []
for l in range(C):
    for m in range(C):
        for n in range(C):
            if l == n or n == m or m == l:
                pass
            else:
                ans_arr.append(ans_arr1[l]+ans_arr2[m]+ans_arr3[n])

print(min(ans_arr))

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
d = [list(map(int,input().split())) for j in range(c)]
cl = [list(map(int,input().split())) for j in range(n)]
check = 1;checkls = [[0 for i in range(c)] for j in range(3)]
for i in range(n):
    for j in range(n):
        check = ((i+1)+(j+1))%3
        checkls[check][cl[i][j]-1] += 1
ans = 1000000000000000000000000000000000000000000000000000000000000
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
                        add = 0;ls = [i,j,k]
                        for l in range(3):
                                for m in range(c):
                                        num = checkls[l][m]
                                        add += d[m][ls[l]] * num
                        ans = min(ans,add)
print(ans)

Submission status: Accepted

Solution code:
n, nc = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(nc)]
grid = [list(map(int, input().split())) for _ in range(n)]
dic = [{}, {}, {}]
for i in range(n):
    for j in range(n):
        if grid[i][j] not in dic[(i+j) % 3]:
            dic[(i+j) % 3][grid[i][j]] = 1
        else:
            dic[(i+j) % 3][grid[i][j]] += 1
minscore = 10 ** 10
def score(color, count):
    ret = 0
    for col, cnt in count.items():
        ret += d[col-1][color-1] * cnt
    return ret
for c0 in range(nc):
    for c1 in range(nc):
        for c2 in range(nc):
            if c0 != c1 and c1 != c2 and c2 != c0:
                minscore = min(minscore, score(c0,dic[0]) + score(c1,dic[1]) + score(c2,dic[2]))
print(minscore)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import permutations

n, c = map(int, input().split())
change_cost = [np.array(list(map(int, input().split()))) for i in range(c)]

iwakan = {}
for i in range(3):
    iwakan[i] = np.zeros(c)

for i in range(n):
    for j, color in enumerate(list(map(int, input().split()))):
        iwakan[(i+j)%3] += change_cost[color-1]

ans = float("inf")
for p in permutations(range(c), 3):
    cost = 0
    for i, color in enumerate(p):
        cost += iwakan[i][color]
    ans = min(ans, cost)
print(int(ans))

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,C = map(int, input().split())
D = [ [int(j) for j in input().split()] for _ in range(C)]
colorInit = [ [int(j) for j in input().split()] for _ in range(N)]

from collections import Counter

cset = [ [], [], [] ]

for i in range(1,N+1):
    for j in range(1,N+1):
        cset[(i+j)%3].append(  colorInit[i-1][j-1] ) 

# print("----")
# for i in range(1,N+1):
#     for j in range(1,N+1):
#         print("{:2d} ".format((i+j)%3), end = " ")
#     print("")


cs1 = Counter(cset[1])
cs2 = Counter(cset[2])
cs3 = Counter(cset[0])
        
# print(colorInit)
# print(cs1,cs2,cs3)
# for k in cs1.keys():
#     print("k: ", k  ) 

# exit(0)

ans = float("inf")
for c1 in range(1,C+1):
    for c2 in range(1,C+1):
        if c1 == c2: continue
        for c3 in range(1,C+1):
            if c1 == c3 or c2 == c3: continue
            tmp = 0
            for k in cs1.keys():
                tmp += cs1[k]* D[k-1][c1-1]
            for k in cs2.keys():
                tmp += cs2[k]* D[k-1][c2-1]
            for k in cs3.keys():
                tmp += cs3[k]* D[k-1][c3-1]
            # print("tmp: ", tmp)
            ans = min(ans, tmp)
            # exit(0)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
grid = [list(map(int,input().split())) for i in range(N)]
l1 = [0]*C
l2 = [0]*C
l3 = [0]*C
for i in range(1,N+1):
    for j in range(1,N+1):
        if (i+j) % 3 == 0:
            l1[grid[i-1][j-1]-1] += 1
        elif (i+j) % 3 == 1:
            l2[grid[i-1][j-1]-1] += 1
        elif (i+j) % 3 == 2:
            l3[grid[i-1][j-1]-1] += 1
color = list(range(1,C+1))
ans = float('inf')
for x,y,z in itertools.permutations(color,3):
    res = 0
    for i in range(C):
        res += D[i][x-1]*l1[i]
    for i in range(C):
        res += D[i][y-1]*l2[i]
    for i in range(C):
        res += D[i][z-1]*l3[i]
    if res < ans:
        ans = res
print(ans)

Submission status: Accepted

Solution code:
n,C = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(C)]
c = [[0]*C for _ in range(3)]
for i in range(n):
  for j,x in enumerate(map(int, input().split())):
    c[(i+j)%3][x-1]+=1
res = 10**10
for i in range(C):
  for j in range(C):
    if i!=j:
      for k in range(C):
        if i!=k and j!=k:
          t = 0
          for l in range(C): t+=d[l][i]*c[0][l]
          for l in range(C): t+=d[l][j]*c[1][l]
          for l in range(C): t+=d[l][k]*c[2][l]
          if t<res: res=t
print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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


# それぞれのグループで、color_iが何個あるかをカウント
mod_0 = [0]*C
mod_1 = [0]*C
mod_2 = [0]*C

for i in range(N):
    l = list(map(int, input().split()))
    for j in range(N):
        m = i+j
        color = l[j]-1
        if m % 3 == 0:
            mod_0[color] += 1
        elif m % 3 == 1:
            mod_1[color] += 1
        else:
            mod_2[color] += 1


# 書き換え方を全通ためして、min
def solve():
    ans = float('inf')
    per = permutations(range(C), 3)

    for c1, c2, c3 in per:
        cost = 0
        for i in range(C):
            cost += D[i][c1]*mod_0[i]
        for i in range(C):
            cost += D[i][c2]*mod_1[i]
        for i in range(C):
            cost += D[i][c3]*mod_2[i]
        ans = min(ans, cost)

    return ans


print(solve())

Submission status: Accepted

Solution code:
from itertools import permutations
# use faster method than input()
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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


# それぞれのグループで、color_iが何個あるかをカウント
mod_0 = [0]*C
mod_1 = [0]*C
mod_2 = [0]*C

for i in range(N):
    l = list(map(int, input().split()))
    for j in range(N):
        m = i+j
        color = l[j]-1
        if m % 3 == 0:
            mod_0[color] += 1
        elif m % 3 == 1:
            mod_1[color] += 1
        else:
            mod_2[color] += 1


# もしかしたら、貪欲かも
# 書き換え方を全通ためして、min
def brute_force():
    ans = float('inf')
    per = permutations(range(C), 3)

    for c1, c2, c3 in per:
        cost = 0
        for i in range(C):
            cost += D[i][c1]*mod_0[i]
        for i in range(C):
            cost += D[i][c2]*mod_1[i]
        for i in range(C):
            cost += D[i][c3]*mod_2[i]
        ans = min(ans, cost)

    return ans


print(brute_force())