hogecoder

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

TopCoder SRM 723 Div1 Easy: TopXorer

TopCoder

するめうめ

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