No.1900 Don't be Powers of 2
タグ : / 解いたユーザー数 45
作問者 :
Shirotsume
/ テスター :
37zigen
👑 
ygussany
問題文
整数 $X$ がある非負整数 $t$ を用いて $X = 2^t$ と表せるならば、 $X$ は $2$ べきであると定義します。
長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。$A$ の（連続であるとは限らない）部分列 $A' = (A'_1, A'_2, \dots, A'_k)$ であって、以下の条件を満たすものの長さ $k$ として考えられる最大値を求めてください。
- 任意の整数対 $(i, j)$ $(1 \leq i \leq j \leq k)$ について、 $A'_i \oplus A'_j$ は $2$ べきでない
ただし、 $X \oplus Y$ は $X$ と $Y$ のBitwise XOR を表します。
Bitwise XOR とは（クリックで展開）
$2$ つの非負整数 $X, Y$ について、$X \oplus Y$ は以下のように定義されます。
- $X \oplus Y$ を $2$ 進表記したときの $2^k$ $(k \geq 0)$ の位は、$X$ の $2$ 進表記での $2^k$ の位と、 $Y$ の $2$ 進表記での $2^k$ の位のうちちょうど一方が $1$ である場合 $1$ 、そうでない場合 $0$
例えば、 $3 \oplus 5 = 6, 1 \oplus 1 = 0$ です。
制約
- 入力は全て整数
- $1 \leq N \leq 2000$
- $0 \leq A_i < 2^{30}$ ($1 \leq i \leq N$)
入力
入力は以下の形式で標準入力から与えられる。$N$ $A_1$ $A_2$ $\dots$ $A_N$
出力
問題文の条件を満たすような部分列 $A'$ の長さ $k$ として考えられる最大値を出力せよ。
最後に改行すること。サンプル
サンプル1
入力
5 1 3 5 7 9
出力
3
長さ $3$ の部分列 $(3, 5, 9)$ は問題文の条件を満たします。しかし、長さ $4$ の部分列 $(3, 5, 7, 9)$ は $5 \oplus 7 = 2$ であり、 $2$ は $2$ べきであるため問題文の条件を満たしません。
他の長さ $4$ 以上の部分列についても、問題文の条件を満たしません。よって、 $3$ が答えです。
サンプル2
入力
2 100 101
出力
1
$100 \oplus 101 = 1$ であり、 $1$ は $2$ べきであるため、どちらか一方しか部分列に含められません。
サンプル3
入力
11 77310887 35643444 185363588 336868833 68922279 453799044 438276915 244357663 500578121 370423265 320536255
出力
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。