[ARC135] C - XOR to All
[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;
}