TopCoder SRM 557 Div1 Hard XorAndSum

当日、EasyとMediumを(結果的にミスしたながらも)submitしたので、Hardも少し考えていた。
結局時間切れだったけど、せっかくなので改めて解いてみる。
http://community.topcoder.com/stat?c=problem_statement&pm=12197

少し考えると、最上位ビットが同じ数同士はxorすると損するので、一番大きな数がさらに大きくなるよう、最上位ビットが等しくない者同士を掛け合わせるのかな？と気づく。

とはいえ、そこで詰まってしまったのでEditorialを見ながら考えていく。
コード自体はEditorialとほぼ同じだけど、過程を理解して処理して行こう。
http://apps.topcoder.com/wiki/display/tc/SRM+557

まず、Editorialにある通り数値を各ビットからなるベクトルと考えて独立成分に分解して行こう。
この処理は、未処理の数値群の最大値を見つけ、それをベクトルの候補とする。
最大値以外の数字に対しては、最上位ビットが一致するなら、小さい方に最大値をXORする。
その結果、残された数値は最上位ビットが最大値より小さくなる。

この手順を繰り返すと、いずれ未処理の数値として0がいくつか残るのでそこで終了。
(0でない数値の数がいわゆるrankである)

この手順で、0以外の各数値は最上位ビットがそれぞれ異なるが、それ以外のビットは一致するものもある。
そこで、今度は数値を小さい順に見て、その最上位ビットがより大きい数も持ってたとすると、大きい数値に小さい数値をXORして大きい数値から小さい数値の最上位ビットを消していく。
(コード中のminimizeの処理)

この手順を行うと、各数値はいずれも独立＝同じビットが１にならない状態になる。
あとは、一番大きな数字にそれ以外の数字をXORして最大値を作り、それを他の(0を含めた)全数値にXORして合計をとればよい。

class XorAndSum {
	public:
	long long maxSum(vector<long long> number) {
		long long hv[50];
		int N = number.size();
		int i,j,dd,mx,rank;
		s64 res,v,mv,mb;
		
		rank=N;
		FOR(i,N) {
			hv[i]=0;
			sort(&number[i],&number[N]);
			reverse(&number[i],&number[N]);
			if(number[i]==0){
				rank=i;
				break;
			}
			v=1;
			while(v*2<=number[i]) v*=2;
			hv[i]=v;
			for(j=i+1;j<N;j++) if(number[j]&v) number[j]^=number[i];
		}
		
		// minimize
		for(i=rank-1;i>=0;i--) {
			FOR(j,i) if(number[j] & hv[i]) number[j] ^= number[i];
		}
		// maxmize
		for(i=1;i<rank;i++) number[0] ^= number[i];
		for(i=1;i<N;i++) number[i] ^= number[0];
		
		res = 0;
		FOR(i,N) res+=number[i];
		
		return res;
	}

};

まとめ

なかなか面白い問題だった。
Hardの割に難易度が低かったのか、今回は正解者が多いね。
とはいえ23人だけど。