SRM723Div1Easy TopXorer - ちゃっくのメモ帳

概要

要素数nの配列xが与えられる。
$0 \leq i \lt n$ に対して $0 \leq a[i] \leq x[i]$ を満たすような配列aに対して
$a[0] xor\ ... xor\ a[n-1]$ の最大値を求めよ

解法

基本的に最大の数の最上位bitを1にして、残った数でそれ以下のbitを1にしていくみたいな気持ち。例えば1100,0100があれば1100->1100,0100->0011にすれば排他的論理和は1111になって最大。
これをするために、左のbitから確定していき、もし左からi番目のbitが1である要素がxに複数あった場合は1つをi番目のbitを1にし、別の要素をi番目のbitを0にしてi+1番目以降を全て1にすれば排他的論理和が最大になる

class TopXorer {
    public:
    int maximalRating(vector <int> x) { // x[i] <= 10^9
        int n = x.size();   // n <= 50
        sort(all(x));
        reverse(all(x));

        vector<int> cnt(40,0);
        for(int i=0;i<n;i++){
            rep(j,31) if(x[i] & (1 << j)) cnt[j]++;
        }

        for(int i=31;i>=0;i--){
            if(cnt[i] > 1){
                cnt[i]--;
                for(int j=0;j<i;j++){
                    cnt[j]++;
                }
                break;
            }
        }

        int ans = 0;
        for(int i=0;i<32;i++){
            if(cnt[i] > 0) ans |= (1 << i);
        }

        //rep(i,n){
        //    cout << x[i] << "\t" << static_cast<bitset<11>>(x[i]) << endl;
        //}
        return ans;
    }
};