CSAcademy Round #42 : E. Xor Submatrix

方針はすぐ立ったのに妙に手間取った。
https://csacademy.com/contest/round-42/task/xor-submatrix/

問題

N要素の数列U[i]とM要素の数列V[j]を考える。
これらの数列から、N*M行列Aを生成する。
このとき、A_ij = U[i] xor V[j]とする。

この行列のうち矩形範囲を任意に選択してできる部分行列について、内部の要素のxor sumの最大値を求めよ。

解法

[a,b]行かつ[c,d]列目を選択したとする。この時のxor sumを考えよう。

• 選択した行数も列数も偶数のとき、部分行列のxor sumは0である。
• 選択した行数が偶数で列数が奇数のとき、部分行列のxor sumはV[i]が偶数回計算されて打ち消すのでxor(U[a...b])である。
• 逆に行数が奇数で列数が偶数のとき、部分行列のxor sumはxor(V[c...d])である。
  • 選択行が偶数となる[a,b]または選択列が偶数となる[c,d]となるときのxor sumはO(N^2+M^2)で列挙できる。

のこりは行数も列数も奇数の場合である。
この時xor sumはxor(U[a...b]) xor xor(V[c...d])となる。
まずU[a...b]の候補AとV[c...d]の候補Bを列挙し、昇順ソートしておこう。

こうなると問題は単純で、2つの数列A,Bがあるとき、要素を1つずつa,bと選んでxorの最大値を求めるだけの問題になる。
これは上のbitから見ていって、xor後にそのbitを立てられる方にDFSしていけばよい。

int N,M;
int A[2020],B[2020];
vector<int> X,Y;
int ma;

void dfs(int d,int XL,int XR,int YL,int YR) {
	int XM=XL;
	int YM=YL;
	
	if(XR<=XL || YR<=YL) return;
	if(XR-XL==1 && YR-YL==1) {
		ma=max(ma,X[XL]^Y[YL]);
		return;
	}
	
	while(XM<XR && (X[XM]&(1<<d))==0) XM++;
	while(YM<YR && (Y[YM]&(1<<d))==0) YM++;
	dfs(d-1,XL,XM,YM,YR);
	dfs(d-1,XM,XR,YL,YM);
	if(ma>=(1<<d)) return;
	dfs(d-1,XL,XM,YL,YM);
	dfs(d-1,XM,XR,YM,YR);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	srand(i);
	
	FOR(i,N) cin>>A[i];
	FOR(x,N) {
		int t=0;
		for(j=1;x+j<=N;j++) {
			t^=A[x+j-1];
			if(j%2==0) ma=max(ma,t);
			else X.push_back(t);
		}
	}
	FOR(i,M) cin>>B[i];
	FOR(x,M) {
		int t=0;
		for(j=1;x+j<=M;j++) {
			t^=B[x+j-1];
			if(j%2==0) ma=max(ma,t);
			else Y.push_back(t);
		}
	}
	
	sort(ALL(X));
	sort(ALL(Y));
	X.erase(unique(ALL(X)),X.end());
	Y.erase(unique(ALL(Y)),Y.end());
	dfs(29,0,X.size(),0,Y.size());
	
	cout<<ma<<endl;

}

まとめ

2つの数列から要素を選んでxorを取るだけの問題、まで還元できればあとは楽。