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: Time Limit Exceeded

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

def main():
    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 = [0]*n
    for i, c_ in enumerate(C_):
        c_ = [x-1 for x in c_]
        C[i] = c_

    #print(C)
    import itertools
    ans = 10**18
    for p in itertools.permutations(range(c), 3):
        temp = 0
        for i in range(n):
            for j in range(n):
                m = (i+j)%3
                x = C[i][j]
                y = p[m]
                temp += D[x][y]
        ans = min(ans, temp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
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):
    x = C[i][j] - 1
    r = (i+j)%3
    for y in range(c):
      A[r][y] += D[x][y]
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
      temp = A[0][i] + A[1][j] + A[2][k]
      ans = min(ans, temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    D = [[0] * (C + 1)]
    for _ in range(C):
        d = [0] + list(map(int, input().split()))
        D.append(d)

    grid = [[0] * (N + 1)]
    for _ in range(N):
        g = [0] + list(map(int, input().split()))
        grid.append(g)

    cost = {0: [], 1: [], 2: []}
    ans = INF
    for c in range(1, C + 1):
        cost0 = 0
        cost1 = 0
        cost2 = 0
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if (i + j) % 3 == 0:
                    cost0 += D[grid[i][j]][c]
                elif (i + j) % 3 == 1:
                    cost1 += D[grid[i][j]][c]
                elif (i + j) % 3 == 2:
                    cost2 += D[grid[i][j]][c]

        cost[0].append((c, cost0))
        cost[1].append((c, cost1))
        cost[2].append((c, cost2))

    cost[0].sort(key=lambda x: x[1])
    cost[1].sort(key=lambda x: x[1])
    cost[2].sort(key=lambda x: x[1])

    ans = INF
    for c0, cost0 in cost[0][:3]:
        for c1, cost1 in cost[1][:3]:
            for c2, cost2 in cost[2][:3]:
                if c0 == c1 or c1 == c2 or c2 == c0:
                    continue

                tmp = cost0 + cost1 + cost2
                if tmp < ans:
                    ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    D = [[0] * (C + 1)]
    for _ in range(C):
        d = [0] + list(map(int, input().split()))
        D.append(d)

    grid = [[0] * (N + 1)]
    for _ in range(N):
        g = [0] + list(map(int, input().split()))
        grid.append(g)

    perm = permutations(range(1, C + 1), 3)
    ans = INF
    for c0, c1, c2 in perm:
        tmp = 0
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if (i + j) % 3 == 0:
                    tmp += D[grid[i][j]][c0]
                elif (i + j) % 3 == 1:
                    tmp += D[grid[i][j]][c1]
                elif (i + j) % 3 == 2:
                    tmp += D[grid[i][j]][c2]

        if tmp < ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, cs = map(int, input().split())
d = [list(map(int, input().split())) for i in range(cs)]
c = [list(map(int, input().split())) for i in range(n)]
for i, j in itertools.product(range(n), repeat=2):
  c[i][j] -= 1
ans = 10**20
for i, j, k in itertools.permutations(range(cs), 3):
  s = 0
  for l, m in itertools.product(range(n), repeat=2):
    if (l + m) % 3 == 0:
      s += d[c[l][m]][i]
    elif (l + m) % 3 == 1:
      s += d[c[l][m]][j]
    else:
      s += d[c[l][m]][k]
  ans = min(ans, s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

ans=float("inf")
num=[i for i in range(1,C+1)]
for n,m,l in itertools.permutations(num,3):
    n,m,l=int(n),int(m),int(l)
    val=0
    for i in M[0]:
        val+=D[i-1][n-1]
    for j in M[1]:
        val+=D[j-1][m-1]
    for k in M[2]:
        val+=D[k-1][l-1]
    ans=min(ans,val)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
N, C = map(int, input().split())
D = list() #D[i][j]:=iからjに変える時の違和感
graph = list()
for i in range(C):
  D.append(list(map(int, input().split())))
for i in range(N):
  graph.append(list(map(int, input().split())))
ans = INF
for c0 in range(C):
  for c1 in range(C):
    for c2 in range(C):
      if(c0 == c1 or c1 == c2 or c2 == c0):
        continue
      tmp = 0
      for x in range(N):
        for y in range(N):
          p = (x+y+2)%3
          c = graph[x][y]-1
          if(p == 0):
            tmp += D[c][c0]
          elif(p == 1):
            tmp += D[c][c1]
          else:
            tmp += D[c][c2]
      ans = min(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

ans = 10 ** 8
for L in permutations([i for i in range(C)], 3):
    if len(set(L)) != 3:
        continue
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += D[c[i][j]-1][L[(i+j)%3]]
    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans = 10 ** 8
for L in product([i for i in range(C)], repeat=3):
    if len(set(L)) != 3:
        continue
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += D[c[i][j]-1][L[(i+j)%3]]
    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)]
grid1 = []
grid2 = []
grid3 = []
ans = float('inf')
for i in range(N):
    for k in range(N):
        tmp = grid[i][k]
        tmp2 = i + k
        if tmp2 % 3 == 1:
            grid1.append(tmp)
        elif tmp2 % 3 == 2:
            grid2.append(tmp)
        else:
            grid3.append(tmp)
sum1 = sum(grid1)
sum2 = sum(grid2)
sum3 = sum(grid3)
tmp1 = [sum1]*C
tmp2 = [sum2]*C
tmp3 = [sum3]*C
for i in range(C):
    for k in grid1:
        tmp1[i] = tmp1[i] - k + D[k-1][i]
for i in range(C):
    for k in grid2:
        tmp2[i] = tmp2[i] - k + D[k-1][i]
for i in range(C):
    for k in grid3:
        tmp3[i] = tmp3[i] - k + D[k-1][i]
for i in range(C):
    for k in range(C):
        if i == k:
            continue
        for l in range(C):
            if i == l or k == l:
                continue
            ans = min(ans,tmp1[i]+tmp2[k]+tmp3[l])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)]
grid1 = []
grid2 = []
grid3 = []
ans = float('inf')
for i in range(N):
    for k in range(N):
        tmp = grid[i][k]
        tmp2 = i + k
        if tmp2 % 3 == 1:
            grid1.append(tmp)
        elif tmp2 % 3 == 2:
            grid2.append(tmp)
        else:
            grid3.append(tmp)
sum1 = sum(grid1)
sum2 = sum(grid2)
sum3 = sum(grid3)
for i in range(C):
    tmp1 = sum1
    for ii in grid1:
        tmp1 = tmp1 - ii + D[ii-1][i]
    for k in range(C):
        if i == k:
            continue
        tmp2 = sum2
        for kk in grid2:
            tmp2 = tmp2 - kk + D[kk-1][k]
        for l in range(C):
            if i == l or k == l:
                continue
            tmp3 = sum3
            for ll in grid3:
                tmp3 = tmp3 - ll + D[ll-1][l]
            ans = min(ans,tmp1+tmp2+tmp3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)]
grid1 = []
grid2 = []
grid3 = []
ans = float('inf')
for i in range(N):
    for k in range(N):
        tmp = grid[i][k]
        tmp2 = i + k
        if tmp2 % 3 == 1:
            grid1.append(tmp)
        elif tmp2 % 3 == 2:
            grid2.append(tmp)
        else:
            grid3.append(tmp)
for i in range(C):
    sum1 = sum(grid1)
    for ii in grid1:
        sum1 = sum1 - ii + D[ii-1][i]
    for k in range(C):
        if i == k:
            continue
        sum2 = sum(grid2)
        for kk in grid2:
            sum2 = sum2 - kk + D[kk-1][k]
        for l in range(C):
            if i == l or k == l:
                continue
            sum3 = sum(grid3)
            for ll in grid3:
                sum3 = sum3 - ll + D[ll-1][l]
            ans = min(ans,sum1+sum2+sum3)
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N,C = map(int,input().split())
    D = [list(map(int,input().split())) for _ in range(C)]
    col = [list(map(int,input().split())) for _ in range(N)]
    
    mod_color = [[],[],[]]
    for i in range(N):
        for j in range(N):
            mod_color[(i+j)%3].append(col[i][j]-1)

    ans = 10**10
    for x,y,z in permutations(range(C),3):
        ret = 0
        for num in mod_color[0]:
            ret += D[num][x]
        for num in mod_color[1]:
            ret += D[num][y]
        for num in mod_color[2]:
            ret += D[num][z]
        ans = min(ans,ret)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = float("inf")

for c0 in range(c):
  for c1 in range(c):
    if c0 == c1: continue
    for c2 in range(c):
      if c0 == c2 or c1 == c2: continue
      tmp = 0
      C = [c0,c1,c2]
      for y in range(n):
        for x in range(n):
          if lc[y][x] != C[(y+x)%3]: tmp += d[lc[y][x]][C[(y+x)%3]]
      ans = min(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#然列挙では間に合わない
N,C = map(int,input().split())
ld = [[]]
for i in range(C):
  ld.append([0]+list(map(int,input().split())))
lc = [[]]  
for i in range(N):
  lc.append([0]+list(map(int,input().split())))

#前処理
lmae = [[0 for i in range(C+1)] for j in range(3)]
for p in range(1,N+1):
  for q in range(1,N+1):
    for i in range(1,C+1):
      X = lc[p][q]
      Y = i
      lmae[(p+q)%3][i] += ld[X][Y]

#こたえ作り
lans = []
for i in range(1,C+1):
  for j in range(i+1,C+1):
    for k in range(j+1,C+1):
      for cc in [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]:
        ans = lmae[cc[0]][i]+lmae[cc[1]][j]+lmae[cc[2]][k]
        lans.append(ans)
print(min(lans))

Submission status: Time Limit Exceeded

Solution code:
N,C = map(int,input().split())
ld = [[]]
for i in range(C):
  ld.append([0]+list(map(int,input().split())))
lc = [[]]  
for i in range(N):
  lc.append([0]+list(map(int,input().split())))

#こたえ作り
lans = []
for i in range(1,C+1):
  for j in range(i+1,C+1):
    for k in range(j+1,C+1):
      for cc in [[i,j,k],[i,k,j],[j,i,k],[j,k,i],[k,i,j],[k,j,i]]:
        ans = 0
        for p in range(1,N+1):
          for q in range(1,N+1):
            X = lc[p][q]
            Y = cc[(p+q)%3]
            ans += ld[X][Y]
        lans.append(ans)
print(min(lans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations, combinations

n, c = map(int, sys.stdin.readline().split())
d = [[int(x) for x in sys.stdin.readline().split()] for _ in range(c)]
grid = [[int(x) - 1 for x in sys.stdin.readline().split()] for _ in range(n)]

cost = [[0] * c for _ in range(3)]
for i in range(n):
  for j in range(n):
    k = (i + j) % 3
    for l in range(c):
      cost[k][l] += d[grid[i][j]][l]
  
def main():
  res = []
  for comb in combinations(range(c), 3):
    for i, j, k in permutations(comb):
      res.append(cost[0][i] + cost[1][j] + cost[2][k])
  print(min(res))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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)]
cnt = [[]for _ in range(3)]
ans = 10**8
for i in range(n):
    for j in range(n):
        cnt[(i+j+2)%3].append((i,j))
for c0 in range(1,C+1):
    for c1 in range(1,C+1):
        for c2 in range(1,C+1):
            res = 0
            
            cl = [c0,c1,c2]
            if c0 == c1 or c1 == c2 or c2 == c0:continue
            
            for i in range(3):
                for x,y in cnt[i]:
                    
                    res += d[c[x][y]-1][cl[i]-1]
                    
            ans = min(res,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,c = map(int,input().split())
d = [0]
for i in range(c):
    d.append([0] + list(map(int,input().split())))
li0 = []
li1 = []
li2 = []
for i in range(n):
    g = list(map(int,input().split()))
    for j in range(n):
        if (i + j) % 3 == 0:
            li0.append(g[j])
        if (i + j) % 3 == 1:
            li1.append(g[j])
        if (i + j) % 3 == 2:
            li2.append(g[j])
ans = 100000000
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 i == k:
                continue
            x = 0
            for color in li0:
                x += d[color][i]
            for color in li1:
                x += d[color][j]
            for color in li2:
                x += d[color][k]
            ans = min(x,ans)
print(ans)

Submission status: Time Limit Exceeded

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

cst = [[0,0,0] for i in range(C)]

for clr in range(1,C+1):
    for i in range(N):
        for j in range(N):
            cst[clr-1][(i+j+2)%3] += D[c[i][j]-1][clr-1]

ans = 10**10

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

print(ans)

Submission status: Time Limit Exceeded

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)]
g1 = []
g2 = []
g3 = []
for i in range(N):
    for j in range(N):
        G[i][j] -= 1
        if (i+j)%3 == 0:
            g1.append(G[i][j])
        if (i+j)%3 == 1:
            g2.append(G[i][j])
        if (i+j)%3 == 2:
            g3.append(G[i][j])
# print(g1) # グループ1の色リスト
# print(g2)
# print(g3)
# for k in range(C):
#     for i in range(C):
#         for j in range(C):
#             D[i][j] = min(D[i][j], D[i][k] + D[k][j])

ans = float('inf')
for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            temp = 0
            if c1 == c2 or c2 == c3 or c3 == c1:
                continue
            temp += sum(D[clr_g1][c1] for clr_g1 in g1)
            temp += sum(D[clr_g2][c2] for clr_g2 in g2)
            temp += sum(D[clr_g3][c3] for clr_g3 in g3)
            ans = min(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

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

cost0 = []
cost1 = []
cost2 = []
indices = [2, 0, 1]
for color in range(C):
  cost = [0, 0, 0]
  for i in range(N):
    idx = indices[i%3]
    for j in range(N):
      cost[idx] += D[c[i][j]-1][color]
      idx = (idx + 1) % 3
  cost0.append([cost[0], color])
  cost1.append([cost[1], color])
  cost2.append([cost[2], color])

cost0.sort()
cost1.sort()
cost2.sort()
ans = float('inf')
for i in range(3):
  for j in range(3):
    for k in range(3):
      if len(set([cost0[i][1], cost1[j][1], cost2[k][1]])) == 3:
        ans = min(ans, cost0[i][0]+cost1[j][0]+cost2[k][0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

# 全探索だと間に合わない
# 一旦実装だけしてみる
corres = list(itertools.permutations(range(C), 3))
ans = float('inf')
indices = [2, 0, 1]
for corr in corres:
  cost = 0
  for i in range(N):
    idx = indices[i%3]
    for j in range(N):
      cost += D[c[i][j]-1][corr[idx]]
      idx = (idx + 1) % 3
  ans = min(ans, cost)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,C=map(int, input().split())
    D=[tuple(map(int, input().split())) for _ in range(C)]
    c=[tuple(map(int, input().split())) for _ in range(N)]

    ans = 10**10
    from itertools import permutations
    for colors in permutations(range(C), 3):
        tmp = 0
        for i in range(N):
            for j in range(N):
                tmp += D[c[i][j]-1][colors[(i+j)%3]]
        ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, C = map(int, input().split())
    D = [[int(d) for d in input().split()] for _ in range(C)]
    col = [[int(i) - 1 for i in input().split()] for _ in range(N)]
    minD = 10 ** 20
    for i in range(C):
        for j in range(C):
            if i == j: continue
            for k in range(C):
                if j != k and k != i:
                    this_D = 0
                    changed = [i, j, k]
                    for ni in range(N):
                        for nj in range(N):
                            this_D += D[col[ni][nj]][changed[(ni + nj) % 3]]
                    minD = min(minD, this_D)
    print(minD)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, C = map(int, input().split())
    D = [[int(d) for d in input().split()] for _ in range(C)]
    col = [[int(i) - 1 for i in input().split()] for _ in range(N)]
    minD = 10 ** 20
    for i in range(C):
        for j in range(C):
            for k in range(C):
                if i != j and j != k and k != i:
                    this_D = 0
                    changed = [i, j, k]
                    for ni in range(N):
                        for nj in range(N):
                            if col[ni][nj] != changed[(ni + nj) % 3]:
                                this_D += D[col[ni][nj]][changed[(ni + nj) % 3]]
                    minD = min(minD, this_D)
    print(minD)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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)]
mod0=set()
mod1=set()
mod2=set()
for i in range(n):
  for j in range(n):
    if (i+j+2)%3==0:
      mod0.add((i,j))
    elif (i+j+2)%3==1:
      mod1.add((i,j))
    else:
      mod2.add((i,j))
cost1=[0]*c
for c1 in range(c):
  tmp=0
  for y,x in mod0:
    tmp+=d[g[y][x]-1][c1]
  cost1[c1]+=tmp
cost2=[0]*c
for c2 in range(c):
  tmp=0
  for y,x in mod1:
    tmp+=d[g[y][x]-1][c2]
  cost2[c2]+=tmp
cost3=[0]*c
for c3 in range(c):
  tmp=0
  for y,x in mod2:
    tmp+=d[g[y][x]-1][c3]
  cost3[c3]+=tmp
ans=10**18
for c1 in range(c):
  for c2 in range(c):
    for c3 in range(c):
      if c1==c2 or c2==c3 or c3==c1:
        continue
      ans=min(ans,cost1[c1]+cost2[c2]+cost3[c3])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [list(map(int,input().split())) for _ in range(n)]
mod0 = []
mod1 = []
mod2 = []
for i in range(n):
    for j in range(n):
        # indexのずれを考慮 ((i+1)+(j+1))%3が本来のmod値
        if (i+j)%3 == 1:
            mod0.append(C[i][j]-1)
        elif (i+j)%3 == 2:
            mod1.append(C[i][j]-1)
        else:
            mod2.append(C[i][j]-1)
color_range = list(range(c))
res = float('inf')
for x,y,z in itertools.permutations(color_range, 3):
    cnt = 0
    for i in range(len(mod0)):
        cnt += D[mod0[i]][x]
    for i in range(len(mod1)):
        cnt += D[mod1[i]][y]
    for i in range(len(mod2)):
        cnt += D[mod2[i]][z]
    res = min(cnt, res)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,C=map(int,input().split())
d=[list(map(int,input().split())) for i in range(C)]
c=[list(map(int,input().split())) for i in range(N)]
ans=10**18
mod0=[]
mod1=[]
mod2=[]
for i in range(N):
  for j in range(N):
    k=(i+j+2)%3
    if k==0:
      mod0.append((i,j))
    elif k==1:
      mod1.append((i,j))
    else:
      mod2.append((i,j))
cnt0=[0]*(C+1)
cnt1=[0]*(C+1)
cnt2=[0]*(C+1)
for c0 in range(1,C+1):
  for x,y in mod0:
    cnt0[c0]+=d[c[x][y]-1][c0-1]
for c1 in range(1,C+1):
  for x,y in mod1:
    cnt1[c1]+=d[c[x][y]-1][c1-1]
for c2 in range(1,C+1):
  for x,y in mod2:
    cnt2[c2]+=d[c[x][y]-1][c2-1]
ans=10**18
for c0 in range(1,C+1):
  for c1 in range(1,C+1):
    for c2 in range(1,C+1):
      if c1==c2 or c2==c0 or c0==c1:
        continue
      cnt=cnt0[c0]+cnt1[c1]+cnt2[c2]
      ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,C=map(int,input().split())
d=[list(map(int,input().split())) for i in range(C)]
c=[list(map(int,input().split())) for i in range(N)]
ans=10**18
mod0=[]
mod1=[]
mod2=[]
for i in range(N):
  for j in range(N):
    k=(i+j+2)%3
    if k==0:
      mod0.append((i,j))
    elif k==1:
      mod1.append((i,j))
    else:
      mod2.append((i,j))
ans=10**18
for c0 in range(1,C+1):
  for c1 in range(1,C+1):
    for c2 in range(1,C+1):
      if c1==c2 or c2==c0 or c0==c1:
        continue
      cnt=0
      for x,y in mod0:
        cnt+=d[c[x][y]-1][c0-1]
      for x,y in mod1:
        cnt+=d[c[x][y]-1][c1-1]
      for x,y in mod2:
        cnt+=d[c[x][y]-1][c2-1]
      ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]
color = [[] for i in range(3)]
for h in range(N):
    for w in range(N):
        color[(h+w+2)%3].append(c[h][w])

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

Submission status: Time Limit Exceeded

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

wrongness = [[0, 0, 0] for _ in range(C)]

for c in range(C):
    for i in range(N):
        for j in range(N):
            wrongness[c][(i + j) % 3] += D[color[i][j] - 1][c]

ans = 10**18

for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if c1 == c2 or c2 == c3 or c3 == c1:
                continue
            ans = min(ans, wrongness[c1][0] + wrongness[c2][1] + wrongness[c3][2])

print(ans)

Submission status: Time Limit Exceeded

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

X = [[] for i in range(3)]
for i in range(N):
    for j in range(N):
        X[(i+j+2)%3].append(G[i][j])
ans = float('inf')
for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            cost = 0
            for i,x in enumerate(X):
                for e in x:
                    if i == 0:
                        cost += D[e-1][c1]
                    elif i == 1:
                        cost += D[e-1][c2]
                    else:
                        cost += D[e-1][c3]
            ans = min(cost,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, C = map(int, input().split())
INF = float("inf")
D = []
for i in range(C):
    D.append(list(map(int, input().split())))
c = []
for i in range(N):
    c.append([n - 1 for n in list(map(int, input().split()))])

# 前計算
cost = make_multi_list(0, [3, C])
for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[(i + j) % 3][k] += D[c[i][j]][k]

ans = INF
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if k in (i, j):
                continue
            ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *

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

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

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


Revalue=10**18
for Color1,Color2,Color3 in list(permutations(list(range(1,C+1)),3)):
    value=0
    for i in lst[0]:
        value+=D[i-1][Color1-1]
    for i in lst[1]:
        value+=D[i-1][Color2-1]
    for i in lst[2]:
        value+=D[i-1][Color3-1]
    Revalue=min(Revalue,value)
print(Revalue)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

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