atcoder ABC 099 D - Good Grid

問題

解法

$ (i+j) \% 3 $ なので条件を満たすために使う色は3色のみ
事前に $ (i+j) \% 3 $ を3パターンに塗ったときのそれぞれのコストを計算しておく
全ての色の組み合わせについて調べる(全探索)。$O(N{^3})$ となるが $ C=30 $ の制約には十分間に合う

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int N,C;
int d[30][30],c[500][500];
int cost[3][30];
int ans=1e9;

int main() {
  cin >> N >> C;
  REP(i,C) REP(j,C) cin >> d[i][j];
  REP(i,N) REP(j,N) cin >> c[i][j], c[i][j]--;

  REP(x,C) REP(i,N) REP(j,N) {
    cost[(i+j)%3][x] += d[c[i][j]][x];
  }

  REP(i,C) REP(j,C) REP(k,C) {
    if (i==j || j==k || k==i) continue;
    ans = min(ans, cost[0][i]+cost[1][j]+cost[2][k]);
  }

  cout << ans << endl;
}

雑感

問題文を理解するのに時間がかかった
事前計算が大事