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

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

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

「前処理」を学べる問題なんな。

問題へのリンク

問題概要 (ABC 099 D)

色が全部で  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;
}