するめうめ
問題概要
個の非負整数列
がある。
から
までの範囲で非負整数
を、
から
までの範囲で非負整数
を、・・・以下同様に合計
個の非負整数を決め、それらの 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; } };