AtCoder ABC #276 : Ex - Construct a Matrix

うーむ手間取った。
https://atcoder.jp/contests/abc276/tasks/abc276_h

問題

N*Nの行列Xを考える。行列の各要素は、0,1,2のいずれかの値を取るものとする。
以下の条件をすべて満たす行列が存在すれば、1つ構成せよ。

• 部分行列が指定され、その中の値の積はE[i]である。

解法

まず各要素0かそうでないかを考える。
部分行列内の値の積が1または2の場合、その範囲は0を含んではならない。

累積和を用いて、各要素0が許容されるかされないかを判定しよう。
0が許容されるところはすべて0としておいて問題ない。

こうして各要素0かそうでないかを求めたところで、再度累積和を取り、条件のうちE[i]=0のものについて、部分行列内に1個以上0を含むかを判定する。もし1個も0を含まないなら、解なし。

あとは残された要素について1と2のいずれかであるかを考える。
1,2の代わりに、0,1を割り当てることを考える。元の部分行列内で積が1,2であるという条件は、0,1を割り当てた部分行列内の要素のxorがE[i]-1と一致するかという問題と等しくなる。これを解こう。

愚直に行うと、最大でN*N個の0/1値を取る変数が現れるQ個の方程式ができてしまい、とても間に合わない。
ただし、0,1を割り当てる行列の累積和を考えると、各条件毎に高々4つの変数の値が定まればよいことになる。
よって、高々4Q変数のQ個の方程式ができる。これは愚直に掃き出し法で解くとO(Q^3)かかるが、bitsetを使うと間に合う。

int N,Q;
int Y1[2020],Y2[2020],X1[2020],X2[2020],E[2020];
int A[2020][2020];
int B[2020][2020];
int C[2020][2020];

const int MAT=8080;
bitset<8080> BS[8080];
int V[8080],R[8080];

int Gauss(int R,int C,bitset<8080> BS[MAT],int v[MAT],int r[MAT]) {
	int i,j,k;
	int nex=0;
	FOR(i,R) {
		while(nex<C) {
			for(j=i;j<R;j++) if(BS[j][nex]) break;
			if(j!=R) break;
			nex++;
		}
		if(nex>=C) break;
		swap(BS[i],BS[j]);
		swap(v[i],v[j]);
		FOR(j,R) if(i!=j && BS[j][nex]) {
			v[j]^=v[i];
			BS[j]^=BS[i];
		}
		nex++;
	}
	FOR(i,C) r[i]=0;
	int num=0;
	FOR(i,R) {
		
		FOR(j,C) if(BS[i][j]) break;
		if(j<C) {
			r[j]=v[i];
			num++;
		}
		else if(v[i]) {
			return -1;
		}
	}
	
	return num;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>Y1[i]>>Y2[i]>>X1[i]>>X2[i]>>E[i];
		if(E[i]) {
			A[Y1[i]][X1[i]]++;
			A[Y2[i]+1][X1[i]]--;
			A[Y1[i]][X2[i]+1]--;
			A[Y2[i]+1][X2[i]+1]++;
		}
	}
	FOR(y,N+2) FOR(x,N+2) {
		if(y) A[y][x]+=A[y-1][x];
		if(x) A[y][x]+=A[y][x-1];
		if(x&&y) A[y][x]-=A[y-1][x-1];
		if(A[y][x]) B[y][x]=1;
		if(y) B[y][x]+=B[y-1][x];
		if(x) B[y][x]+=B[y][x-1];
		if(x&&y) B[y][x]-=B[y-1][x-1];
		
	}
	vector<int> X;
	FOR(i,Q) {
		if(E[i]==0) {
			//0が1個もないと不可
			k=B[Y2[i]][X2[i]]-B[Y1[i]-1][X2[i]]-B[Y2[i]][X1[i]-1]+B[Y1[i]-1][X1[i]-1];
			if(k==(Y2[i]-Y1[i]+1)*(X2[i]-X1[i]+1)) {
				cout<<"No"<<endl;
				return;
			}
		}
		else {
			X.push_back((Y1[i]-1)*2020+(X1[i]-1));
			X.push_back((Y1[i]-1)*2020+(X2[i]-0));
			X.push_back((Y2[i]-0)*2020+(X1[i]-1));
			X.push_back((Y2[i]-0)*2020+(X2[i]-0));
		}
	}
	sort(ALL(X));
	X.erase(unique(ALL(X)),X.end());
	int nex=0;
	FOR(i,Q) if(E[i]>0) {
		x=lower_bound(ALL(X),(Y1[i]-1)*2020+(X1[i]-1))-X.begin();
		BS[nex][x]=1;
		x=lower_bound(ALL(X),(Y1[i]-1)*2020+(X2[i]-0))-X.begin();
		BS[nex][x]=1;
		x=lower_bound(ALL(X),(Y2[i]-0)*2020+(X1[i]-1))-X.begin();
		BS[nex][x]=1;
		x=lower_bound(ALL(X),(Y2[i]-0)*2020+(X2[i]-0))-X.begin();
		BS[nex][x]=1;
		V[nex]=E[i]>1;
		nex++;
	}
	i=Gauss(nex,X.size(),BS,V,R);
	if(i==-1) {
		cout<<"No"<<endl;
		return;
	}
	FOR(i,X.size()) {
		y=X[i]/2020;
		x=X[i]%2020;
		C[y][x]=R[i];
	}
	
	cout<<"Yes"<<endl;
	
	FOR(y,N) {
		FOR(x,N) {
			int a=B[y+1][x+1]-B[y][x+1]-B[y+1][x]+B[y][x];
			if(a==0) cout<<"0 ";
			else {
				a=C[y+1][x+1]^C[y][x+1]^C[y+1][x]^C[y][x];
				cout<<(a+1)<<" ";
			}
		}
		cout<<endl;
	}
			
	
}

まとめ

bitset使う形の掃き出し法、今まで実装してなかったな…。