Codeforces #1021 : Div1 D. Homework

D問題の割にコードは少な目。
https://codeforces.com/contest/2097/problem/D

問題

バイナリ文字列Aがあったとき、以下の処理を繰り返すことができるとする。

• Aが偶数長の時、前半分Xと後ろ半分Yに分割する。その後、以下を行う。
  • X[i]=X[i] ^ Y[i] とする
  • Y[i]=X[i] ^ Y[i] とする
  • XまたはYについて、再帰的に分割して処理を行い、終わったらまたくっつける

N文字の2つのバイナリ文字列A,Bが与えられる。
Aに対し上記処理を繰り返し、Bを構成できるか判定せよ。

解法

N = m*2^n (mは2以外)と表現できるとする。
するとAから構成できるのは、Aをm bitずつに分割した2^n個のbit vectorの基底ベクトルからなるのxorを、また2^n個並べたものとなる。
よって、A,Bから得られる基底ベルトルが成す空間が等しいかチェックすればよい。

int TT,N;
string S,T;


int gf2_rank(vector<vector<int>>& A) { /* input */
	int i,j,k;
	int H=A.size(),W=A[0].size();
	FOR(i,H) {
		int be=i,mi=W;
		for(j=i;j<H;j++) {
			FOR(k,W) if(A[j][k]) break;
			if(k<mi) be=j,mi=k;
		}
		if(mi>=W) break;
		swap(A[i],A[be]);
		
		FOR(j,H) if(i!=j&&A[j][mi]) {
			FOR(k,W) A[j][k] ^= A[i][k];
		}
	}
	return i;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>TT;
	while(TT--) {
		cin>>N>>S>>T;
		x=N;
		while(x%2==0) x/=2;
		vector<vector<int>> A,B;
		vector<int> C,D;
		FOR(i,N) {
			C.push_back(S[i]-'0');
			D.push_back(T[i]-'0');
			if(C.size()==x) {
				A.push_back(C);
				C.clear();
				B.push_back(D);
				D.clear();
			}
		}
		A.resize(gf2_rank(A));
		B.resize(gf2_rank(B));
		
		if(A==B) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
		
		
	}
}

まとめ

ちょっと手間取ったけど、まぁまぁな時間で思いつけて良かったね。