Atcoder ABC99-D GoodGrid
問題
色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の3重ループを0〜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; }