Codeforces #1010 : Div1 C. Quaternary Matrix

意外にコード量が多い。
https://codeforces.com/contest/2081/problem/C

問題

0～3で構成される行列が良いとは、各列・各行のxorの値がそれぞれ0となることをいう。
行列Aが与えられるので、Aが良い行列となるために値を変更すべき要素数と、変更後のAの例を示せ。

解法

値を変更するとは、ある整数x、行r、列cを指定すると、r行目とc列目のxorがxだけ変化することを意味する。
R(x) := 初期状態で行のxorがxとなる行の数
C(x) := 初期状態で列のxorがxとなる列の数

あとは、極力少ない手数で行・列の値を0にしていこう。
上ほど効率が良いので、上から順に貪欲に対応すればよい。

• R(x)とC(x)は、1手で合わせてデクリメントできる。
• R(x)とR(y)とC(x^y)、もしくはR(x^y)とC(x)とC(y)は2手でそれぞれデクリメントできる。
• R(x)2つC(y)2つは、3手でそれぞれデクリメントできる。

int T;
int H,W;
int A[1010][1010];
vector<int> R[4],C[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		FOR(i,4) {
			R[i].clear();
			C[i].clear();
		}
		cin>>H>>W;
		FOR(y,H) {
			cin>>s;
			k=0;
			FOR(x,W) {
				A[y][x]=s[x]-'0';
				k^=A[y][x];
			}
			R[k].push_back(y);
		}
		FOR(x,W) {
			k=0;
			FOR(y,H) k^=A[y][x];
			C[k].push_back(x);
		}
		int ret=0;
		for(i=1;i<=3;i++) while(R[i].size()&&C[i].size()) {
			ret++;
			A[R[i].back()][C[i].back()]^=i;
			R[i].pop_back();
			C[i].pop_back();
		}
		for(i=1;i<=3;i++) for(j=i+1;j<=3;j++) {
			k=i^j;
			while(R[i].size()&&R[j].size()&&C[k].size()) {
				ret+=2;
				A[R[i].back()][C[k].back()]^=i;
				A[R[j].back()][C[k].back()]^=j;
				R[i].pop_back();
				R[j].pop_back();
				C[k].pop_back();
			}
			while(C[i].size()&&C[j].size()&&R[k].size()) {
				ret+=2;
				A[R[k].back()][C[i].back()]^=i;
				A[R[k].back()][C[j].back()]^=j;
				R[k].pop_back();
				C[i].pop_back();
				C[j].pop_back();
			}
		}
		for(i=1;i<=3;i++) for(j=1;j<=3;j++) if(i!=j) {
			while(R[i].size()>=2&&C[j].size()>=2) {
				ret+=3;
				A[R[i].back()][C[j].back()]^=i;
				A[R[i][R[i].size()-2]][C[j][C[j].size()-2]]^=j;
				A[R[i][R[i].size()-2]][C[j].back()]^=i^j;
				R[i].pop_back();
				R[i].pop_back();
				C[j].pop_back();
				C[j].pop_back();
			}
		}
		for(i=1;i<=3;i++) {
			FORR(r,R[i]) A[r][0]^=i, ret++;
			FORR(c,C[i]) A[0][c]^=i, ret++;
		}
		cout<<ret<<endl;
		FOR(y,H) {
			FOR(x,W) cout<<A[y][x];
			cout<<endl;
		}
	}
		
}

まとめ

わかってしまえば簡単なのだが。