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目として取る値であり、大きい方の和を答えとしてカウントする。
あとは2分割したvector群において(D-1)桁以下を再帰的に処理する。
この手法だと毎回vectorを2分割するので、最終的に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でも似た問題が出たよね。