TopCoder SRM 649 Div1 Medium XorSequence、Div2 Hard XorSequenceEasy

Codeforcesで出がちな典型問題と思ったけど、なぜか550ptだった。
http://community.topcoder.com/stat?c=problem_statement&pm=13249
http://community.topcoder.com/stat?c=problem_statement&pm=13657

問題

2の累乗であるNと、0～(N-1)の何れかの整数で構成されるS要素の数列A[i]がある。

ここである整数Bを決め、C[i] = A[i] xor Bの計算で数列C[i]を作成する。
最適なBを用いた場合、i＜jかつC[i]＜C[j]となる整数の対(i,j)の最大値を求めよ。

Div1 MediumとDiv2 Hardの違いはAの要素数Sの制限のみである。

解法

bit演算と、数値の大小が出たら2進数桁DP(orメモ化再帰)、という定番テクで解ける。

2進数で上の桁から処理していく。
例えば今D桁目を処理するとする。
まずD+1以上の値でAの要素を分類し、vectorのvectorを作る。

各vectorにおいて、D桁目の0/1で2つのvectorにさらに分けると同時に、BのDbit目を0にした場合と1にした場合の(i,j)の対の数をそれぞれ求める。
各vectorにおいてBのDbit目を0にした場合と1にした場合の(i,j)の対の数の和の大きい方が、BのDbit目として取る値であり、大きい方の和を答えとしてカウントする。

あとは２分割したvector群において(D-1)桁以下を再帰的に処理する。
この手法だと毎回vectorを２分割するので、最終的にvectorのvectorがN要素になってMLEしまうので、0または1要素のvectorは以後の処理を行わないようにすると良い。

ll A[300000];

class XorSequence {
	public:
	ll ret;
	
	ll dfs(int D,vector<vector<int> >& V) {
		if(D<0 || V.empty()) return 0;
		int i,j;
		vector<vector<int> > NV;
		ll ret0=0,ret1=0;
		
		FOR(i,V.size()) {
			vector<int> v[2];
			int n0=0,n1=0;
			FOR(j,V[i].size()) {
				if(V[i][j]&(1<<D)) {
					n1++;
					ret1 += n0;
					v[1].push_back(V[i][j]);
				}
				else {
					n0++;
					ret0 += n1;
					v[0].push_back(V[i][j]);
				}
			}
			if(v[0].size()>1) NV.push_back(v[0]);
			if(v[1].size()>1) NV.push_back(v[1]);
		}
		return max(ret0,ret1)+dfs(D-1,NV);
		
	}
	
	long long getmax(int N, int sz, int A0, int A1, int P, int Q, int R) {
		int i;
		
		A[0]=A0;
		A[1]=A1;
		for(i=2;i<sz;i++) A[i]=(A[i-2]*P+A[i-1]*Q+R)%N;
		
		vector<vector<int> > V;
		V.push_back(vector<int>());
		FOR(i,sz) V.back().push_back(A[i]);
		return dfs(29,V);
		
	}
}

まとめ

yukicoderでも似た問題が出たよね。