Atcoder ABC99-D GoodGrid

問題

D - Good Grid

色iを色jに塗り替える時に感じる違和感と、色が塗られたマス目の情報が与えられる。この時、(i+j)%3=(x+y)%3となるような(i,j),(x,y)のマス目は全て同じ色に塗らなければならない。感じる違和感の最小値を求める。

解説

全探索をします。
前準備として、v[0,1,2][0,1,2,,c]の配列において、「v[i][j]:=(x+y)%3==i のマス目における色j の出現回数」とすることで、(x+y)%3=0,1,2それぞれについて、最初はどの色が何個あるのかを持っておきます。

次に、i,j,kの３重ループを０〜cで回し、i≠j≠kの時、(x+y)%3=0のマス目をi, =1のマス目をj, =2のマス目をkで塗るような全探索をします。これによって最小値を調べ、出力すれば良いです。i,j,kを決めれば、あとは(x+y)%3のそれぞれについて、「今塗られている色の個数」*「その色をi,j,kに変える時の違和感」の総和をとります。

以下、コードです（#includeは省略）

int main (){
    int n,c;cin>>n>>c;
    vector<vector<int>> v(3,vector<int>(c)),cost(c,vector<int>(c));
    rep(i,0,c)rep(j,0,c)cin>>cost[i][j]; //違和感
    rep(i,0,n)rep(j,0,n){
        int x;cin>>x;
        v[((i+1)+(j+1))%3][x-1]++;
    }

    int ans=1e18;
    rep(i,0,c){ //%3==0をiに
        rep(j,0,c){  //%3==1をjに
            if(i==j)continue;
            rep(k,0,c){ //%3==2をkにするとき
                if(i==k || j==k)continue; 
                int ret=0;
                rep(ind,0,3){ //%3の値
                    int x;
                    if(ind==0)x=i;
                    else if(ind==1)x=j;
                    else if(ind==2)x=k;
                    rep(val,0,c){
                        ret+=v[ind][val]*cost[val][x];
                    }
                }
                ans=min(ans,ret);
            }
        }
    }
    cout<<ans<<endl;
}