No.3269 Leq-K Partition
問題文最終更新日: 2025-08-23 22:19:47
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 482
(順位表)
の他の問題:
Problem Statement
You are given an integer sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$. Solve the following problem for each of $k = 1,2, \dots, N$.
- Consider partitioning $A$ into non-empty contiguous subsequences. Each element of $A$ must belong to exactly $1$ subsequence. Find the minimum number of subsequences required for a partition in which every subsequence contains at most $k$ distinct values.
Input
$N$ $A_1\ A_2\ \dots\ A_N$
- All input values are integers.
- $1 \le N \le 10^5$
- $1 \le A_i \le N$
Output
Output $N$ lines. On the $i$-th line $(1 \le i \le N)$, output the answer for $k = i$.
Sample
Sample 1
Input
10 1 2 2 3 4 6 5 7 5 4
Output
9 5 3 2 2 2 1 1 1 1
- For $k=1$, it can be partitioned into $9$ subsequences, for example $(1),(2,2),(3),(4),(6),(5),(7),(5),(4)$.
- For $k=2$, it can be partitioned into $5$ subsequences, for example $(1,2),(2,3),(4,6),(5,7),(5,4)$.
- For $k=3$, it can be partitioned into $3$ subsequences, for example $(1,2,2,3),(4,6,5),(7,5,4)$.
- For $k=4$, it can be partitioned into $2$ subsequences, for example $(1,2,2,3,4),(6,5,7,5,4)$.
- For $k=5$, it can be partitioned into $2$ subsequences, for example $(1,2,2,3,4,6),(5,7,5,4)$.
- For $k=6$, it can be partitioned into $2$ subsequences, for example $(1,2,2,3,4,6,5),(7,5,4)$.
- For $k\ge 7$, it can be partitioned into $1$ subsequence, for example $(1,2,2,3,4,6,5,7,5,4)$.
Sample 2
Input
1 1
Output
1
Sample 3
Input
8 1 2 3 4 5 6 7 8
Output
8 4 3 2 2 2 2 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
apricity