Good Grid [AtCoder Beginner Contest 099 D]

https://beta.atcoder.jp/contests/abc099/tasks/abc099_d

解説

https://beta.atcoder.jp/contests/abc099/submissions/2671723

(x+y)%3の0,1,2の3種類の色の組み合わせを全て全探索しよう。
(x+y)%3=0であるマスの色をc0、同様にc1,c2と定義する。
若干愚直にやるとこのような感じになる。
これは色の組み合わせにO(C^3)、違和感計算にO(N^2)なのでO(C^3N^2)で間に合わない。
違和感計算を高速化することにしよう。
　
事前計算でpre配列を用意しておく。
pre[pat][col] := (x+y)%3=patであるマス全てをcol色にしたときに違和感の総和
これはO(CN^2)で計算できる。
これを利用すると違和感計算がO(1)まで落ちるのでO(CN^2 + C^3)で間に合う。

int N, C, D[30][30], c[505][505];
int pre[3][30];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(y, 0, C) rep(x, 0, C) cin >> D[y][x];
    rep(y, 0, N) rep(x, 0, N) cin >> c[y][x], c[y][x]--;
 
    rep(col, 0, C) rep(y, 0, N) rep(x, 0, N) pre[(y + x) % 3][col] += D[c[y][x]][col];
 
    int ans = inf;
    rep(c0, 0, C) rep(c1, 0, C) rep(c2, 0, C) {
        if (c0 == c1) continue;
        if (c0 == c2) continue;
        if (c1 == c2) continue;
 
        chmin(ans, pre[0][c0] + pre[1][c1] + pre[2][c2]);
    }
    cout << ans << endl;
}