「前処理」を学べる問題ですね。

問題概要

色が全部で $C$ 色ある。
$N$ × $N$ の盤面がそれぞれ $C$ 色のいずれかに塗られている。今この盤面の色を塗り替えて

マス ( $i, j$ ) について $(i+j)$ % 3 の値によって色を類別された状態 (その値が同じマスは同じ色に、違うマスは違う色に)

にしたい。色 $a$ のマスを色 $b$ にするのにかかるコストは $D_{ab}$ として与えられている。最小コストで目的を達成せよ。

制約

$3 \le C \le 30$
$1 \le N \le 500$

考えたこと

$(i+j)$ % 3 の値は 3 通りなので、調べるべき場合は $O(C^{3})$ 通りである。素直な全探索で解ける問題なのだが...

愚直にやろうと思うと、 $O(C^{3})$ 通りそれぞれについて、 $N^{2}$ 個のマスにかかるコストを総和をとるような処理をしたくなり、これでは計算量は $O(C^{3}N^{2})$ かかってしまう。

これでは間に合わないので、 $(i+j)$ % 3 の 3 通りの値それぞれについて、その値のマスすべてを $c$ 色にするのに必要な総コストを前処理しておく。この前処理にかかる時間は $O(CN^{2})$ である。

この前処理をしておくと、上述の全探索の $O(C^{3})$ 通りそれぞれについてのコスト計算は $O(1)$ でできるので $O(C^{3})$ でできる。まとめると

前処理: $O(CN^{2})$
全探索: $O(C^{3})$

ともにちゃんと間に合う

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int N, C; cin >> N >> C;
    vector<vector<int> > D(C, vector<int>(C, 0));
    for (int i = 0; i < C; ++i) for (int j = 0; j < C; ++j) cin >> D[i][j];
    vector<vector<int> > fi(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> fi[i][j], --fi[i][j];
    
    // 前処理
    vector<vector<int> > cost(3, vector<int>(C, 0));
    for (int c = 0; c < C; ++c) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cost[(i+j)%3][c] += D[fi[i][j]][c];
            }
        }
    }
    
    // 求める
    int res = 1<<30;
    int c[3];
    for (c[0] = 0; c[0] < C; ++c[0]) {
        for (c[1] = 0; c[1] < C; ++c[1]) {
            if (c[1] == c[0]) continue;
            for (c[2] = 0; c[2] < C; ++c[2]) {
                if (c[2] == c[0] || c[2] == c[1]) continue;
                int tmp = 0;
                for (int it = 0; it < 3; ++it) tmp += cost[it][c[it]];
                res = min(res, tmp);
            }
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 099 D - Good Grid (水色, 400 点)

問題概要

制約

考えたこと