yukicoder : No.1954 CHECKER×CHECKER(2)

Mの値で誤解法に導かれそう。
https://yukicoder.me/problems/no/1954

問題

白黒で塗られたグリッドが与えられる。
加えて、行えるM通りの処理が指定される。
各処理では、ある指定されたいくつかの列のprefixを白黒反転させるか、いくつかの行のprefixを白黒反転させるかのいずれかである。
このグリッドを市松模様状にできるか判定せよ。

解法

まず初期状態で、市松模様状の位置のマスを白黒反転させておく。
そうすると、あとは全マスの色を一致させられるかという問題になる。

まず、可能な処理の列・行で座標圧縮しておこう。
圧縮後1マスになる矩形区間内が、そもそも1色で統一されていなければ解なし。

まず列の処理を利用して、1行目の色をそろえよう。
行単位の白黒反転は任意に行えるので、あとは各行の色が一致しているかを判定すればよい。

int H,W,M;
string S[505];
vector<int> Rs,Cs;
int RT[202],CT[202];
int A[505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			S[y][x]=(S[y][x]=='#')^((y+x)%2);
		}
	}
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		if(x==1) {
			if(y<H) Rs.push_back(y);
		}
		else {
			if(y<W) Cs.push_back(y);
		}
	}
	Rs.push_back(H);
	Cs.push_back(W);
	int NR=Rs.size();
	int NC=Cs.size();
	sort(ALL(Rs));
	sort(ALL(Cs));
	FOR(y,H) RT[y]=lower_bound(ALL(Rs),y+1)-Rs.begin();
	FOR(x,W) CT[x]=lower_bound(ALL(Cs),x+1)-Cs.begin();
	FOR(y,H) FOR(x,W) A[RT[y]][CT[x]]=S[y][x];
	FOR(y,H) FOR(x,W) if(A[RT[y]][CT[x]]!=S[y][x]) {
		cout<<"No"<<endl;
		return;
	}
	FOR(x,NC) if(A[0][x]) {
		FOR(y,NR) A[y][x]^=1;
	}
	
	FOR(y,NR) {
		FOR(x,NC) if(A[y][x]!=A[y][0]) {
			cout<<"No"<<endl;
			return;
		}
	}
	
	cout<<"Yes"<<endl;
	
}

まとめ

O(2^M)というわけでも無いようだ。