問題一覧 > 通常問題

No.1900 Don't be Powers of 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : ShirotsumeShirotsume / テスター : 37zigen37zigen 👑 ygussanyygussany
6 ProblemId : 7762 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 13:25:04

問題文

整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。