kmjp's blog

競技プログラミング参加記です

CSAcademy Round #55 : D. Matrix Palindromes

Dまでは良かったけどEがダメダメでした。
https://csacademy.com/contest/round-55/task/matrix-palindromes/

問題

N*Mの二次元グリッドがあり、各マスそれぞれ文字が埋められている。
この文字をいくつか差し替え、以下を満たすようにしたい。

  • 各行はすべて回文である。
  • M列中K列以上が回文である。

最低何文字文字を差し替える必要があるか。

解法

行が回文ということは(0-indexで)c列目と(M-1-c)列目は同じにならなければならない。

そこで

  • c列目と(M-1-c)列目を等しくするコスト
  • さらにc列目内を回文にするための追加コスト

をそれぞれ求めよう。これは各文字にたいし上下左右対称な位置にある計4文字ずつを見ていけばよい。
さて、1つめの条件より、前者は必ず払うべきコストであり、2列分列の回文を生成するためには、後者-前者の分の追加コストを払う必要がある。
よってこの追加コストを全列に対して求め、小さい順にK列分選ぼう。

なお、N,Mが奇数の場合に注意。

int H,W,K;
string S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) cin>>S[y];
	vector<int> cand;
	int need=0;
	FOR(x,W/2) {
		int a=0,b=0;
		FOR(y,H) a+=S[y][x]!=S[y][W-1-x];
		FOR(y,H/2) {
			map<char,int> m;
			m[S[y][x]]++;
			m[S[y][W-1-x]]++;
			m[S[H-1-y][x]]++;
			m[S[H-1-y][W-1-x]]++;
			int mi=4;
			FORR(r,m) mi=min(mi,4-r.second);
			b+=mi;
		}
		if(H%2==1) b+=S[H/2][x]!=S[H/2][W-1-x];
		need+=a;
		cand.push_back(b-a);
	}
	sort(ALL(cand));
	reverse(ALL(cand));
	while(K>=2) {
		need+=cand.back();
		cand.pop_back();
		K-=2;
	}
	if(W%2) {
		int dif=0;
		FOR(y,H/2) dif+=S[y][W/2]!=S[H-1-y][W/2];
		cand.push_back(dif);
		sort(ALL(cand));
		reverse(ALL(cand));
	}
	if(K) {
		need+=cand.back();
	}
	cout<<need<<endl;
	
}

まとめ

ちょっと手間取ったけどまぁ周りも少し時間かかってたしこんなもんか。