E - Adjacent Xor Game

Contest Duration: 2023-09-09(Sat) 04:00 - 2023-09-09(Sat) 09:00 (local time) (300 minutes) Back to Home

E - Adjacent Xor Game Editorial

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : $2500$ 点

問題文

$N$ 個の非負整数 $A_1,A_2,\cdots,A_N$ が与えられます．各 $k=1,2,\cdots,N$ について，以下の問題を解いてください．

Alice と Bob が以下のようなゲームをします．

Alice が $A_1,A_2,\cdots,A_N$ の中から $k$ 個の数を選ぶ．選んだ数を $x_1,x_2,\cdots,x_k$ (順不同)とおく．
Bob が長さ $2k$ の非負整数列 $y=(y_1,y_2,\cdots,y_{2k})$ を作る．ここで， $y$ は以下の条件を満たす必要がある．
- $0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}$
- $z_i=y_{2i-1} \oplus y_{2i}$ と定義する．このとき， $\{z_1,z_2,\cdots,z_k\}$ は多重集合として $\{x_1,x_2,\cdots,x_k\}$ と一致する．

なお， $\oplus$ はビット単位 $\mathrm{XOR}$ 演算を表します．

このゲームのスコアを $y_{2k}$ の値とします． Bob はスコアを最小化するように行動します．その上で Alice はスコアを最大化するように行動します．このとき，スコアはいくつになるでしょうか？

ビット単位 $\mathrm{XOR}$ 演算とは

非負整数 $A, B$ のビット単位 $\mathrm{XOR}$ 、 $A \oplus B$ は、以下のように定義されます。

$A \oplus B$ を二進表記した際の $2^k$ ( $k \geq 0$ ) の位の数は、 $A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。

例えば、 $3 \oplus 5 = 6$ となります (二進表記すると: $011 \oplus 101 = 110$ )。
一般に $k$ 個の非負整数 $p_1, p_2, p_3, \dots, p_k$ のビット単位 $\mathrm{XOR}$ は $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ と定義され、これは $p_1, p_2, p_3, \dots, p_k$ の順番によらないことが証明できます。

制約

$1 \leq N \leq 250000$
$1 \leq A_i \leq 10^9$
入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

 $N$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

出力

答えを出力せよ．

入力例 1Copy

Copy

3
1 2 3

出力例 1Copy

Copy

2
6
6

$k=1$ の場合を考えます．

Alice が $x_1=1$ を選んだ場合: Bob は $y=(0,1)$ を作り，スコアは $1$ になります．
Alice が $x_1=2$ を選んだ場合: Bob は $y=(0,2)$ を作り，スコアは $2$ になります．
Alice が $x_1=3$ を選んだ場合: Bob は $y=(1,2)$ を作り，スコアは $2$ になります．

よって Alice は $x_1=2$ または $x_1=3$ を選び，スコアは $2$ になります．

$k=2$ の場合を考えます． Alice が $(x_1,x_2)=(2,3)$ を選び，Bob が $y=(1,2,4,6)$ を作ると，スコアは $6$ になります．これは両者の最適な行動の一例であり，求める答えは $6$ です．

$k=3$ の場合を考えます． Alice が $(x_1,x_2,x_3)=(1,2,3)$ を選び，Bob が $y=(0,1,1,2,4,6)$ を作ると，スコアは $6$ になります．これは両者の最適な行動の一例であり，求める答えは $6$ です．

入力例 2Copy

Copy

5
1 1 1 1 1

出力例 2Copy

Copy

入力例 3Copy

Copy

5
1 2 4 8 16

出力例 3Copy

Copy

入力例 4Copy

Copy

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

出力例 4Copy

Copy

Score : $2500$ points

Problem Statement

You are given $N$ non-negative integers $A_1,A_2,\cdots,A_N$ . For each $k=1,2,\cdots,N$ , solve the following problem.

Alice and Bob play the following game.

Alice chooses $k$ numbers from $A_1,A_2,\cdots,A_N$ . Let $x_1,x_2,\cdots,x_k$ be the chosen numbers (in arbitrary order).
Bob makes a sequence of $2k$ non-negative integers $y=(y_1,y_2,\cdots,y_{2k})$ , which must satisfy the following conditions.
- $0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}$ .
- Let $z_i=y_{2i-1} \oplus y_{2i}$ . Then, $\{z_1,z_2,\cdots,z_k\}$ coincides with $\{x_1,x_2,\cdots,x_k\}$ as a multiset.

Here, $\oplus$ denotes bitwise $\mathrm{XOR}$ .

Let the score of the game be the value of $y_{2k}$ . Bob plays to minimize the score. With this in mind, Alice plays to maximize the score. What will the score be?

What is bitwise $\mathrm{XOR}$ ?

The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$ , $A\ \mathrm{XOR}\ B$ , is defined as follows.

When $A\ \mathrm{XOR}\ B$ is written in binary, the $k$ -th lowest bit ( $k \geq 0$ ) is $1$ if exactly one of the $k$ -th lowest bits of $A$ and $B$ is $1$ , and $0$ otherwise.

For instance, $3\ \mathrm{XOR}\ 5 = 6$ (in binary: $011\ \mathrm{XOR}\ 101 = 110$ ).
Generally, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined to be $(\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k)$ , which one can prove to be independent of the order of $p_1, p_2, p_3, \dots p_k$ .

Constraints

$1 \leq N \leq 250000$
$1 \leq A_i \leq 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

Output

Print the answer.

Sample Input 1Copy

Copy

3
1 2 3

Sample Output 1Copy

Copy

2
6
6

Consider the case $k=1$ .

If Alice chooses $x_1=1$ : Bob makes $y=(0,1)$ , for the score of $1$ .
If Alice chooses $x_1=2$ : Bob makes $y=(0,2)$ , for the score of $2$ .
If Alice chooses $x_1=3$ : Bob makes $y=(1,2)$ , for the score of $2$ .

Thus, Alice will choose $x_1=2$ or $x_1=3$ , for the score of $2$ .

Consider the case $k=2$ . If Alice chooses $(x_1,x_2)=(2,3)$ and Bob makes $y=(1,2,4,6)$ , the score will be $6$ . This is an example of optimal play for both players, and the answer is $6$ .

Consider the case $k=3$ . If Alice chooses $(x_1,x_2,x_3)=(1,2,3)$ and Bob makes $y=(0,1,1,2,4,6)$ , the score will be $6$ . This is an example of optimal play for both players, and the answer is $6$ .

Sample Input 2Copy

Copy

5
1 1 1 1 1

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

5
1 2 4 8 16

Sample Output 3Copy

Copy

Sample Input 4Copy

Copy

20
167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186

Sample Output 4Copy

Copy