AtCoder Beginner Contest 099 D - Good Grid

• 問題

D - Good Grid

• 解法

色の塗替えの候補は30×29×28通り。
すべての色の塗り替え方について各マス目を見て違和感を計算する方法ではの時間計算量がかかりTLEになってしまう。
そこでに対してとなるマス目にどの色が何個あるかを事前に計算しておけば、色の塗り替え方に対しすべてのマス目を見る必要がなくなる。
結局の時間計算量でこの問題は解ける。

こういう問題に遭遇するとREPマクロ使いたくなる。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const int INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int N,C;
	cin >> N >> C;

	int d[31][31] = {0}, c[501][501]= {0};
	for(int i = 1; i <= C; i++){
		for(int j = 1; j <= C; j++){
			cin >> d[i][j];
		}
	}
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			cin >> c[i][j];
		}
	}

	map<int,int> color[3];
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			color[(i+j)%3][c[i][j]]++;
		}
	}

	int ans = INF;
	for(int i = 1; i <= C; i++){
		for(int j = 1; j <= C; j++){
			for(int k = 1; k <= C; k++){
				if(i != j && j != k && k != i){
					int res = 0;
					for(int l = 0; l < 3; l++){
						int m = i;
						if(l == 1) m = j;
						else if(l == 2) m = k;
						for(auto itr = color[l].begin(); itr != color[l].end(); ++itr){
							res += d[itr->first][m] * itr->second;
						}
					}
					ans = min(res,ans);
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}