ABC099D Good Grid - raoZ’s diary

問題概要

N行N列のグリッドを色1~Cで塗り分け、(i,j)を最初c_i,jで塗っている。(i+j)%3 = (x + y)%3ならば(i,j)の色は同じ、そうでなければ異なるように塗り替える。X→Yの色に変えた時、そのマスに対して感じる違和感をD_x,yとする。この違和感の和の取りうる最小値を求めよ。

制約

1 <= N <= 500
3 <= C <= 30
1 <= D_i,j(i!=j) <= 1000

方針・所感

設定が小難しくて問題文を読んでから飲み込むのに時間がかかる。

方針としては2つある。

1つ目は、mod3でマス目をグループ分けすることさえ考えれば、各グループ(O(3))の元の色(C)が何個ずつあるか分かってしまえばあとは色の変化パターンを全探索O(C^3)して十分間に合いそうだ。 (公式解説と同じ)

もう一つは、事前にmod3で分けられるマスごとに、事前に色をある色cに変えた時の違和感をO(N^2C)で求めてしまえば、あとは色の塗り方をO(C^3)で求められ、全体として計算量はO(N^2C + C^3)となりこれでも間に合う。以下の実装はこの方針である。

細かいところ・デバッグの記録など

制約によって前者・後者の解法が生きたり死んだりするので問題設定に注意したい。

実装

 
#include <bits/stdc++.h>
#define rep(i, N) for(int i = 0; i < N; i++)
#define FOR(i, a, b) for(int i = a; i < b; i++)
using namespace std;
const int INF = 1e9;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }


int main(){
    int N, C; cin >> N >> C;
    unordered_map<int,int> MP[3]; // (i+j)%3が同じものについて、色kに変えた時の違和感の和

    vector<vector<int>> D(C+1, vector<int>(C+1)), c(N, vector<int>(N));

    FOR(i,1,C+1) FOR(j, 1, C + 1) cin >> D[i][j];
    rep(i, N) rep(j, N) cin >> c[i][j];

    //vector<vector<int>> dis(N, vector<int>(3,INF));

    rep(i, N) rep(j, N) FOR(k, 1, C+1){
        MP[(i + j) % 3][k] += D[c[i][j]][k];
    }

    int ans = INF;
    FOR(c1, 1, C+1) FOR(c2, 1, C+1) FOR(c3, 1, C+1){
        if(c1 == c2 || c2 == c3 || c3 == c1) continue;
        int tmp = 0;
        tmp += MP[0][c1] + MP[1][c2] + MP[2][c3];
        chmin(ans, tmp);
    }
    cout << ans << endl;
    
}