No.390 最長の数列
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 282
作問者 : ぴろず / テスター : 37zigen
タグ : / 解いたユーザー数 282
作問者 : ぴろず / テスター : 37zigen
問題文最終更新日: 2017-06-25 01:46:32
問題文
$N$個の正の整数を含む空でない集合$S= \{ x_1,x_2, \dots ,x_N \}$が与えられます。
$S$に対して、次の$2$つの性質をもつ長さ$M(\geq 1)$の数列$(a_1,a_2, \dots ,a_M)$を「良い」数列と言うことにします。
- 任意の$i(1 \leq i \leq M)$に対して$a_i \in S$
- 任意の$i(1 \leq i \leq M - 1)$に対して、$a_i < a_{i+1}$かつ$a_{i+1}$ は $a_i$ の倍数
最も長い「良い」数列の長さを求めるプログラムを作成してください。
入力
$N$ $x_1$ $x_2$ $\dots$ $x_N$
$1$行目に$N$が与えられます。
$2$行目にスペース区切りで$N$個の整数$x_1,x_2, \dots ,x_N$が与えられます。
$1 \leq N \leq 10^5$
$1 \leq x_i \leq 10^6 \; (1 \leq i \leq N)$
$x_i \neq x_j \; (1 \leq i < j \leq N)$
出力
最も長い「良い」数列の長さを$1$行に出力してください。 最後に改行してください。
サンプル
サンプル1
入力
5 1 2 3 4 5
出力
3
「良い」数列として、$(1,2)$や$(2,4)$や$(5)$などが考えられます。
長さが$3$の「良い」数列は$(1,2,4)$のみで、これが最大値です。
サンプル2
入力
7 3 4 8 9 16 27 432
出力
4
長さが最大となる「良い」数列は$(3,9,27,432)$と$(4,8,16,432)$の$2$つあります。
「良い」数列の長さの最大を出力するので、$4$を出力します。
サンプル3
入力
7 1 2 22 88 8 4 440
出力
6
$x_1, x_2, \dots x_N$は昇順に並んでいないこともあります。
サンプル4
入力
5 2 3 5 7 11
出力
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。