AtCoder ABC 099 D

April 27, 2020

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

D - Good Grid

マスを条件を満たすように塗り替えたときの、最小コスト(「違和感」)を求める問題。

コストに影響するのは、塗り替える前後の色のみで、マスの位置は関係ない。実際に、 $(i + j) \% 3 = 0$ のマスを色Cに塗り替えたときのコストを数式で表すとわかるが、これらのマスについての色の分布さえわかればいい。こういった問題では、余分な情報を取り除いて、統計量で表すなどしてまとめる方針で考える。

色の数は高々30なので、 $(i + j) \% 3 = 0,1,2$ それぞれのマスを塗り替える色のパターンを全探索する。

実装

#define MAX_N 500
#define MAX_C 30

i64 G[MAX_N][MAX_N];
i64 D[MAX_C][MAX_C];
i64 dist[3][MAX_C];

int main() {
    i64 N, C; cin >> N >> C;
    REP(i, C) REP(j, C) cin >> D[i][j];
    REP(i, N) REP(j, N) { cin >> G[i][j]; G[i][j]--; };

    REP(i, 3) REP(j, C) dist[i][j] = 0;

    REP(i, N) REP(j, N) {
        dist[(i + j) % 3][G[i][j]]++;
    }

    i64 minc = 1152921504606846976;
    REP(c0, C) REP(c1, C) REP(c2, C) {
        if (c0 == c1 || c1 == c2 || c2 == c0) continue;
        vector<i64> colors = {c0, c1, c2};
        i64 cost = 0;
        REP(rem, 3) {
            REP(c, C) {
                cost += D[c][colors[rem]] * dist[rem][c];
            }
        }
        chmin(minc, cost);
    }
    cout << minc << endl;

    return 0;
}