Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 135 C問題 XOR to All

AtCoder ARC ARC135 C問題 500 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

非負整数列 A に対して, 次の操作を 0 回以上行う.

  • x \in \{A_1, A_2, \dots, A_N\} を選ぶ.
  • A \gets (A_i \oplus x)

このとき, 操作後の \displaystyle \sum_{i=1}^N A_i の最大値を求めよ.

制約

  • 1 \leq N \leq 3 \times 10^5
  • 0 \leq A_i \leq 2^{30}

解法1 (操作後の整数列)

操作後の A にどのような特徴があるかをみる. まず, 1回も操作しないことで, A 自身が実現可能である.

1回以上操作した場合において, 実は以下が成立する.

操作後の整数列 B=(B_i) に対して, ある 1 以上 N 以下の整数 k が存在して, B_i=A_i \oplus A_k である.

証明
2 回の操作の結果について示せば十分である. まず, x=A_l とすると, 整数列は (A_i \oplus A_l)_i になる. その後, x=A_k \oplus A_l (元の第 k 項) を選ぶと, 第 i 項は (A_i \oplus A_l) \oplus (A_k \oplus A_l)=A_i \oplus A_k となる. これが任意の i で成立するので, 2回の操作の場合については示せた. 3回以上についてもこれを繰り返し用いることによって示すことができる.

解法2 (最大値を求める)

よって, 求めるべきは

\displaystyle \max \left(\sum_{i=1}^N A_i, \max_{k=1,2, \dots, N} \sum_{i=1}^N (A_i \oplus A_k) \right)

となる.

\displaystyle \max_{k=1,2, \dots, N} \sum_{i=1}^N (A_i \oplus A_k) について考える. ここで, 一般的に非負整数 \displaystyle \sum_{i=1}^N X_i において, X_i の2進表記を \displaystyle X_i=\sum_{j=0}^\infty x_{i,j} 2^j としたとき,

\displaystyle \sum_{i=1}^N X_i=\sum_{j=0}^\infty \left(\sum_{i=1}^N x_{i,j} \right) 2^j

が成り立つ. ただし, j の上限が \infty となっているが, X_1, X_2, \dots, X_N は有限であることから, \infty は十分大きい整数に置き換えても良いことに注意する. 例えば, \lceil \log_2 \max A \rceil で置き換えれば良い.

この等式から, X_1, X_2, \dots, X_N において, いくつ 2^j の位が 1 であるかを見れば総和を求めることができる.

A_1, A_2, \dots, A_N のうち 2^j の位が 0,1 である整数の個数を p_{j,0}, p_{j,1} とする. すると, 1回の操作において第 k 項を選んだ場合の 2^j の位が 0,1であるような項の個数を q_{k,j,0}, q_{k,j,1} は A_k の2進表記を \displaystyle A_k=\sum_{j=0}^\infty a_{k,j} 2^j としたとき,

q_{k,j,0}=\begin{cases} p_{j,0} & (a_{k,j}=0) \\ p_{j,1} & (a_{k,j}=1) \end{cases}, \quad q_{k,j,1}=\begin{cases} p_{j,1} & (a_{k,j}=0) \\ p_{j,0} & (a_{k,j}=1) \end{cases}

である.

よって, \displaystyle \sum_{i=1}^N (A_i \oplus A_k)=\sum_{j=0}^\infty q_{k,j,1} 2^j であり, 各 k において総和は O(\log \max A) で求められる.

以上から,

\displaystyle \max \left(\sum_{i=1}^N A_i, \max_{k=1,2, \dots, N} \sum_{i=1}^N (A_i \oplus A_k) \right)=\max \left(\sum_{i=1}^N A_i, \max_{k=1,2, \dots, N} \sum_{j=0}^\infty q_{k,j,1} 2^j \right)

は O(N \log \max A) で求められることができる.