問題一覧 > 通常問題

No.1900 Don't be Powers of 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : Shirotsume / テスター : 37zigen 👑 ygussany
7 ProblemId : 7762 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-25 12:51:50

問題文

整数 XX がある非負整数 tt を用いて X=2tX = 2^t と表せるならば、 XX は 22 べきであると定義します。

長さ NN の数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) が与えられます。AA の（連続であるとは限らない）部分列 A′=(A1′,A2′,…,Ak′)A' = (A'_1, A'_2, \dots, A'_k) であって、以下の条件を満たすものの長さ kk として考えられる最大値を求めてください。

  • 任意の整数対 (i,j)(i, j) (1≤i≤j≤k)(1 \leq i \leq j \leq k) について、 Ai′⊕Aj′A'_i \oplus A'_j は 22 べきでない

ただし、 X⊕YX \oplus Y は XX と YY のBitwise XOR を表します。

Bitwise XOR とは（クリックで展開）

22 つの非負整数 X,YX, Y について、X⊕YX \oplus Y は以下のように定義されます。

  • X⊕YX \oplus Y を 22 進表記したときの 2k2^k (k≥0)(k \geq 0) の位は、XX の 22 進表記での 2k2^k の位と、 YY の 22 進表記での 2k2^k の位のうちちょうど一方が 11 である場合 11 、そうでない場合 00

例えば、 3⊕5=6,1⊕1=03 \oplus 5 = 6, 1 \oplus 1 = 0 です。

制約

  • 入力は全て整数
  • 1≤N≤20001 \leq N \leq 2000
  • 0≤Ai<2300 \leq A_i < 2^{30} (1≤i≤N1 \leq i \leq N)

入力

入力は以下の形式で標準入力から与えられる。 
NN
A1A_1 A2A_2 …\dots ANA_N

出力

問題文の条件を満たすような部分列 A′A' の長さ kk として考えられる最大値を出力せよ。

最後に改行すること。

サンプル

サンプル1
入力
5
1 3 5 7 9
出力
3

長さ 33 の部分列 (3,5,9)(3, 5, 9) は問題文の条件を満たします。しかし、長さ 44 の部分列 (3,5,7,9)(3, 5, 7, 9) は 5⊕7=25 \oplus 7 = 2 であり、 22 は 22 べきであるため問題文の条件を満たしません。

他の長さ 44 以上の部分列についても、問題文の条件を満たしません。よって、 33 が答えです。

サンプル2
入力
2
100 101
出力
1

100⊕101=1100 \oplus 101 = 1 であり、 11 は 22 べきであるため、どちらか一方しか部分列に含められません。

サンプル3
入力
11
77310887 35643444 185363588 336868833 68922279 453799044 438276915 244357663 500578121 370423265 320536255
出力
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。