Codeforces Global Round 2 : C. Ramesses and Corner Inversion

5完まではサクサク解けたので辛うじてレート増。
https://codeforces.com/contest/1119/problem/C

問題

0/1で構成されるマトリックスが２つ与えられる。
ここで２列・２行以上の部分行列を指定すると、４つの角の値を0/1反転させることができるとする。

２つの行列を一致できるか判定せよ。

解法

この操作は可逆なので、両マトリックスから同じ形状に持ち込もうとしてみて、同じ形状になれば一致するものとする。

部分行列として、右端は最終列、下端は最終行であるものとし、最終行・最終列以外で1を見つけたらそこを左上角とするような部分行列を設定しよう。
そうすると最終行・最終列以外1はなくなり、以後は操作できない状況になる。
この状態で一致判定をしよう。

int H,W;
int A[505][505],B[505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	FOR(y,H) FOR(x,W) cin>>B[y][x];
	FOR(y,H-1) FOR(x,W-1) {
		if(A[y][x]) {
			A[y][x]^=1;
			A[y][W-1]^=1;
			A[H-1][x]^=1;
			A[H-1][W-1]^=1;
		}
		if(B[y][x]) {
			B[y][x]^=1;
			B[y][W-1]^=1;
			B[H-1][x]^=1;
			B[H-1][W-1]^=1;
		}
	}
	FOR(y,H) FOR(x,W) if(A[y][x]!=B[y][x]) return _P("No\n");
	cout<<"Yes"<<endl;
	
}

まとめ

Div1A相当だとしてもちょっと易しめ。