TopCoder SRM 723 Div1 Easy: TopXorer

するめうめ

tsutaj.hatenablog.com

問題概要

個の非負整数列 がある。

から までの範囲で非負整数 を、 から までの範囲で非負整数 を、・・・以下同様に合計 個の非負整数を決め、それらの 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;
    }
};