問題一覧 > 通常問題

No.3269 Leq-K Partition

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : apricity / テスター : 遭難者
ProblemId : 12520 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-08-23 22:19:47

問題文

長さ $N$ の整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます． $k = 1,2, \dots, N$ について以下の問題を解いてください．

  • $A$ を空でない 連続 部分列に分割することを考えます． $A$ の各要素はちょうど $1$ つの部分列に属している必要があります． 全ての部分列について，現れる値の種類数が $k$ 以下となるように分割する際に，最小で何個の部分列に分割する必要があるか求めてください．

入力

$N$
$A_1\ A_2\ \dots\ A_N$

  • 入力は全て整数
  • $1 \le N \le 10^5$
  • $1 \le A_i \le N$

出力

$N$ 行出力してください． $i$ 行目 $(1 \le i \le N)$ には， $k = i$ に対する答えを出力してください．

サンプル

サンプル1
入力
10
1 2 2 3 4 6 5 7 5 4
出力
9
5
3
2
2
2
1
1
1
1

  • $k=1$ の場合，例えば $(1),(2,2),(3),(4),(6),(5),(7),(5),(4)$ のように $9$ 個の部分列に分割することができます．
  • $k=2$ の場合，例えば $(1,2),(2,3),(4,6),(5,7),(5,4)$ のように $5$ 個の部分列に分割することができます．
  • $k=3$ の場合，例えば $(1,2,2,3),(4,6,5),(7,5,4)$ のように $3$ 個の部分列に分割することができます．
  • $k=4$ の場合，例えば $(1,2,2,3,4),(6,5,7,5,4)$ のように $2$ 個の部分列に分割することができます．
  • $k=5$ の場合，例えば $(1,2,2,3,4,6),(5,7,5,4)$ のように $2$ 個の部分列に分割することができます．
  • $k=6$ の場合，例えば $(1,2,2,3,4,6,5),(7,5,4)$ のように $2$ 個の部分列に分割することができます．
  • $k\ge 7$ の場合，例えば $(1,2,2,3,4,6,5,7,5,4)$ のように $1$ 個の部分列に分割することができます．

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

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

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