/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
長さが N^2 の正整数列 A=(A_1,\ A_2,\ \dots,\ A_{N^2}) と正整数 S があります。この正整数列については正整数 i\ (1\leq i \leq N^2-N) に対し A_i=A_{i+N} が成り立ち、A_1,\ A_2,\ \dots,\ A_N のみが入力で与えられます。
総和が S であるような任意の正整数列 B が正整数列 (A_1,\ A_2,\ \dots,\ A_L) の（連続とは限らない）部分列となるような最小の整数 L を求めてください。
この問題の制約のもとでそのような L が 1 つ以上存在することが示せます。
制約
- 1 \leq N \leq 1.5 \times 10^6
- 1 \leq S \leq \min(N,2 \times 10^5)
- 1 \leq A_i \leq S
- 任意の正整数 x\ (1\leq x \leq S) について、(A_1,\ A_2,\ \dots,\ A_N) は x を 1 つ以上含む
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N S A_1 A_2 \dots A_N
出力
答えを出力してください。
入力例 1
6 4 1 1 2 1 4 3
出力例 1
9
B として考えるべきなのは B=(1,\ 1,\ 1,\ 1),\ (1,\ 1,\ 2),\ (1,\ 2,\ 1),\ (1,\ 3),\ (2,\ 1,\ 1),\ (2,\ 2),\ (3,\ 1),\ (4) です。
例えば L=8 とすると B=(2,\ 2) は (A_1,A_2,\ \dots,\ A_8)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1) の部分列となりません。
一方で L=9 とするとすべての B が (A_1,A_2,\ \dots,\ A_9)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1,\ 2) の部分列となります。
入力例 2
14 5 1 1 1 2 3 1 2 4 5 1 1 2 3 1
出力例 2
11
入力例 3
19 10 1 6 2 7 4 8 5 9 1 10 4 1 3 1 3 2 2 2 1
出力例 3
39
Score : 1000 points
Problem Statement
We have a sequence of positive integers of length N^2, A=(A_1,\ A_2,\ \dots,\ A_{N^2}), and a positive integer S. For this sequence of positive integers, A_i=A_{i+N} holds for positive integers i\ (1\leq i \leq N^2-N), and only A_1,\ A_2,\ \dots,\ A_N are given as the input.
Find the minimum integer L such that every sequence B of positive integers totaling S is a (not necessarily contiguous) subsequence of the sequence (A_1,\ A_2,\ \dots,\ A_L) of positive integers.
It can be shown that at least one such L exists under the Constraints of this problem.
Constraints
- 1 \leq N \leq 1.5 \times 10^6
- 1 \leq S \leq \min(N,2 \times 10^5)
- 1 \leq A_i \leq S
- For every positive integer x\ (1\leq x \leq S), (A_1,\ A_2,\ \dots,\ A_N) contains at least one occurrence of x.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N S A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
6 4 1 1 2 1 4 3
Sample Output 1
9
There are eight sequences B to consider: B=(1,\ 1,\ 1,\ 1),\ (1,\ 1,\ 2),\ (1,\ 2,\ 1),\ (1,\ 3),\ (2,\ 1,\ 1),\ (2,\ 2),\ (3,\ 1),\ (4).
For L=8, for instance, B=(2,\ 2) is not a subsequence of (A_1,A_2,\ \dots,\ A_8)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1).
For L=9, on the other hand, every B is a subsequence of (A_1,A_2,\ \dots,\ A_9)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1,\ 2).
Sample Input 2
14 5 1 1 1 2 3 1 2 4 5 1 1 2 3 1
Sample Output 2
11
Sample Input 3
19 10 1 6 2 7 4 8 5 9 1 10 4 1 3 1 3 2 2 2 1
Sample Output 3
39