Codeforces #530 Div1 B. Nice table

どっかで見たな。
https://codeforces.com/contest/1098/problem/B

問題

H*Wのグリッドがあり、各セルATGCのいずれかの文字が書かれている。
一部のセルの文字を書き換え、どの2*2領域をとってもATGCの文字が1個ずつ含まれているようにしたい。
そのような書き換え方のうち、書き換える文字数が最小となる例を構築せよ。

解法

最終系は以下のようになる。

• 1行おきに似たパターンが発生する。
  • 例えば1行目がATAT....とする。その時偶数行目はGCGC...またはCGCG...であり、奇数行目はATAT...またはTATA...である。
• 1列おきに似たパターンが発生する。
  • 例えば1列目がATAT....とする。その時偶数列目はGCGC...またはCGCG...であり、奇数列目はATAT...またはTATA...である。

よって、1行おきおよび1列おきのパターンをそれぞれ総当たりしよう。
例えば前者の例であれば、偶数行目に来る２文字と奇数行目にくる２文字を総当たりする。
各行でどちらの選択肢を取るかは、書き換え数が小さくなる方を独立に選ぶことができる。

int H,W;
string S[505050];
string T[505050];
string R[505050];

char dec(char c) {
	if(c=='A') return 0;
	if(c=='T') return 1;
	if(c=='C') return 2;
	if(c=='G') return 3;
}

char enc(char c) {
	if(c==0) return 'A';
	if(c==1) return 'T';
	if(c==2) return 'C';
	if(c==3) return 'G';
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FORR(c,S[y]) c=dec(c);
	}
	
	int mi=1<<30;
	for(int mask=0;mask<1<<4;mask++) if(__builtin_popcount(mask)==2) {
		vector<char> C[2];
		FOR(i,4) C[(mask>>i)&1].push_back(i);
		int tot=0;
		FOR(y,H) {
			int cnt[2]={};
			FOR(i,2) {
				FOR(x,W) cnt[i]+=S[y][x]!=C[y%2][(x%2)^i];
			}
			j=(cnt[1]<cnt[0]);
			tot+=cnt[j];
			T[y].clear();
			FOR(x,W) T[y].push_back(C[y%2][(x%2)^j]);
		}
		if(tot<mi) {
			mi=tot;
			FOR(y,H) R[y]=T[y];
		}
		
		tot=0;
		FOR(y,H) T[y].clear();
		FOR(x,W) {
			int cnt[2]={};
			FOR(i,2) {
				FOR(y,H) cnt[i]+=S[y][x]!=C[x%2][(y%2)^i];
			}
			j=(cnt[1]<cnt[0]);
			tot+=cnt[j];
			FOR(y,H) T[y].push_back(C[x%2][(y%2)^j]);
		}
		if(tot<mi) {
			mi=tot;
			FOR(y,H) R[y]=T[y];
		}
		
	}
	
	FOR(y,H) {
		FORR(c,R[y]) c=enc(c);
		cout<<R[y]<<endl;
	}
	
}

まとめ

01で構成されるグリッドで、1が2個入る、ってのをAtCoder系で見たな。