するめうめ
問題概要
個の非負整数列 がある。
から までの範囲で非負整数 を、 から までの範囲で非負整数 を、・・・以下同様に合計 個の非負整数を決め、それらの XOR をとるとき、 XOR 値の最大値を求めよ。
解説
XOR を最大化したいのですから、大きいビットはなるべく取りたいです。
任意の自然数 について、 以下の非負整数をなにか つ取りたいと考える時、 の MSB を使うとその次に大きいビットまでは使うことができませんが、MSB を使わなかった場合、それ以下のビットについては任意に選べます。よって、以下の方針で解くことができます。
- 大きいビットから走査する
- ビット目に注目しているとき、 ビット目が立っている最大の要素を探し、それを とする
- の ビット目を使う。それ以外の要素に関しては ビット目を使わないため、もしも ビット目が立っているならば ビット目以下を全て使える状態にしておく
ソースコード
class TopXorer { public: int maximalRating(vector<int> x) { int N = x.size(), ret = 0; for(int k=29; k>=0; k--) { int last = -1; for(int i=0; i<N; i++) { if(x[i] >> k & 1) { if(last == -1 || x[last] < x[i]) { last = i; } } } if(last < 0) continue; ret |= (1 << k); x[last] ^= (1 << k); for(int i=0; i<N; i++) { if(x[i] >> k & 1) { x[i] = (1 << k) - 1; } } } return ret; } };