[Q] https://atcoder.jp/contests/arc135/tasks/arc135_c

1. 全部の要素をbitで見て、
30bit目が立っているのは何本か
29bit目が立っているのは何本か
28bit目が立っているのは何本か...
を数えておく。

2. 問題通り全探索。1つ選んで全部にxorする。これを、O(N^2) ではなくて、O(N*30)で高速化。さっきもとめたbitの総和が使える。

N=5
A:1 2 3 4 5

1: 001
2: 010
3: 011
4: 100
5: 101
------
   223 bitが立っている本数の総和
   ~
   N=5なので、2本立っている場所に論理和をとると、5-2=3本が立つことになるのでお得。

x=1のとき
x:001(bit)
bit==0 の場所は、立っている本数を加算。
bit==1 の場所は、xorで反転するのでN-立っている本数を加算。

x:001
  ---
b:223
^:332
------
  222

score = (1<<2)*2 + (1<<1)*2 + (1<<0)*2 // 8+4+2=14
               ~          ~          ~

x=2 のとき

x:010
  ---
b:223
^:332
------
  233
score = (1<<2)*2 + (1<<1)*3 + (1<<0)*3 // 8+6+3=17
               ~          ~          ~

x=3 のとき

x:011
  ---
b:223
^:332
------
  232
score = (1<<2)*2 + (1<<1)*3 + (1<<0)*2 // 8+6+2=16
               ~          ~          ~

x=4 のとき

x:100
  ---
b:223
^:332
------
  323
score = (1<<2)*3 + (1<<1)*2 + (1<<0)*3 // 12+4+3=19
               ~          ~          ~


x=5のときもして、19がmax
   

Q. 上位bitから見て、優先的に候補を絞ってもいい？
A. ダメーー！(2WA)

bitで見て、こんな9要素があったとする。

00000000000
00000000000
00000000000
00000000000
00000000000
01111111111
10000000000
10000000000
10000000000
-----------
31111111111: bitが立っている本数の総和
~

最上位bitを見たときに、
N=9 だから、3 < 9/2 なので、最上位bitが立っている要素との排他的論理和をとると、
9-3の6本が最上位bitに立つことになってお得。

すなわち、最上位に1が立っているbit 10000000000 を優先的に採用する。
そして、最上位 bit 0 の要素を除外する？


でも、これがダメっっっ！！！

この場合は
01111111111 こそ至高。

下位bitの総和が上位を十分上回る場合もある。
すべての要素Ａについて、xorを試さないといけない。

実装

ll A[300030];
ll bits[33];

int main(){
 cincout();
 
 ll N;
 cin >> N;
 ll ans = 0;
 rep(i, N){
   ll a;
   cin >> a;
   A[i] = a;
   rep(j, 31){
     if (is_pop(a, j)) ++bits[j];
   }
   ans += a;
 }
 
 rep(i, N){
   ll score = 0;
   ll a = A[i];
   rep(j, 31){
     if (is_pop(a, j) == false){
       score += bits[j] * ((1LL)<<j);
     }
     else{
       score += (N-bits[j]) * ((1LL)<<j);
     }
   }
   chmax(ans, score);
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/arc135/submissions/29310216