hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 723 Div1 Easy: TopXorer

するめうめ

tsutaj.hatenablog.com

問題概要

 N 個の非負整数列  x_{1}, x_{2}, \dots, x_{N} がある。

 0 から  x_{1} までの範囲で非負整数  a_{1} を、  0 から  x_{2} までの範囲で非負整数  a_{2} を、・・・以下同様に合計  N 個の非負整数を決め、それらの XOR をとるとき、 XOR 値の最大値を求めよ。

解説

XOR を最大化したいのですから、大きいビットはなるべく取りたいです。

任意の自然数  N について、 N 以下の非負整数をなにか  1 つ取りたいと考える時、 N の MSB を使うとその次に大きいビットまでは使うことができませんが、MSB を使わなかった場合、それ以下のビットについては任意に選べます。よって、以下の方針で解くことができます。

  • 大きいビットから走査する
  •  k ビット目に注目しているとき、  k ビット目が立っている最大の要素を探し、それを  x_{m} とする
  •  x_{m} k ビット目を使う。それ以外の要素に関しては  k ビット目を使わないため、もしも  k ビット目が立っているならば  k-1 ビット目以下を全て使える状態にしておく

ソースコード

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;
    }
};