No.979 Longest Divisor Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 125
作問者 : ngtkanangtkana / テスター : noshi91noshi91
7 ProblemId : 3491 / 出題時の順位表
問題文最終更新日: 2020-01-31 22:19:09

問題文

長さ $N$ の数列 $A_0 \dots A_{N - 1}$ が与えられます。
その部分列 $ A_{i_0} \dots A_{i_{K - 1}}\ (0 \leq i_0 < \dots < i_{K - 1} < N) $ であって、

  • 各項が次の項を割り切る: $ A_{i_0} | A_{i_1} | \dots | A_{i_{K - 1}} $
  • 強単調増加である: $A_{i_0} < A_{i_1} < \dots < A_{i_{K - 1}}$
の 2 条件を満たすもののうち、最長のものの長さ $K$ を求めてください。
ただし、整数 $X, Y$ に対して、記号 $ X | Y $ は $ Y $ が $ X $ の倍数であることを表します。

(21:43 $a_i$ を $A_i$ に修正)

入力

$N$
$A_0 \dots A_{N - 1}$

入力は全部で 2 行となり、以下の制約を満たします。

  • 入力は全て整数
  • $1 \leq N \leq 3 \times 10 ^ 5$
  • $1 \leq A_i \leq 3 \times 10^5\ (0 \leq i < N)$

出力

条件を満たす部分列のうち最長なものの長さを一行で出力してください。

サンプル

サンプル1
入力
5
2 4 6 1 8
出力
3

添字 $ 0, 1, 4 $ に対応する部分列 $2, 4, 8$ が最長です。

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

$1, 3, 9$ が最長です。

サンプル3
入力
1
1
出力
1

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