Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
この問題は F 問題の簡易版です。
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A を 1 か所で区切って 2 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めてください。
より厳密には、1 \leq i \leq N-1 を満たす整数 i について (A_1,A_2,\ldots,A_i), (A_{i+1},A_{i+2},\ldots,A_N) のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq N (1 \leq i \leq N)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 3 1 4 1 5
出力例 1
5
- i=1 としたとき、(3) と (1,4,1,5) のそれぞれに含まれる整数の種類数は 1,3 で、これらの和は 4 です。
- i=2 としたとき、(3,1) と (4,1,5) のそれぞれに含まれる整数の種類数は 2,3 で、これらの和は 5 です。
- i=3 としたとき、(3,1,4) と (1,5) のそれぞれに含まれる整数の種類数は 3,2 で、これらの和は 5 です。
- i=4 としたとき、(3,1,4,1) と (5) のそれぞれに含まれる整数の種類数は 3,1 で、これらの和は 4 です。
よって、 i=2,3 のときに、最大値 5 を取ります。
入力例 2
10 2 5 6 5 2 1 7 9 7 2
出力例 2
8
Score : 350 points
Problem Statement
This problem is a simplified version of Problem F.
You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).
When splitting A at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.
More formally, find the maximum sum of the following two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq N (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
5
- For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
- For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
- For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
- For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.
Therefore, the maximum sum is 5 for i=2,3.
Sample Input 2
10 2 5 6 5 2 1 7 9 7 2
Sample Output 2
8
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
とある回転寿司に、1 から N までの番号が付けられた N 人の人が訪れています。 人 i の 美食度 は A_i です。
今からベルトコンベア上を M 個の寿司が流れます。 j 番目に流れる寿司の 美味しさ は B_j です。 それぞれの寿司は、人 1,2,\dots,N の前をこの順に流れていきます。 それぞれの人は、美味しさが自分の美食度以上である寿司が自分の前に流れてきたときはその寿司を取って食べ、それ以外のときは何もしません。 人 i が取って食べた寿司は、人 j\ (j > i) の前にはもう流れてきません。
M 個の寿司それぞれについて、その寿司を誰が食べるか、あるいは誰も食べないかどうかを求めてください。
制約
- 1\leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 2\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
出力
M 行出力せよ。
j\ (1\leq j \leq M) 行目には、j 番目に流れる寿司を食べる人がいるならばその人の番号を、そうでないならば -1 を出力せよ。
入力例 1
3 3 3 8 2 5 2 1
出力例 1
1 3 -1
- 1 番目の寿司について、
- まず人 1 の前を流れます。B_1 \geq A_1 なので、人 1 はこれを取って食べます。
- 人 2,3 の前にはこの寿司は流れてきません。
- 2 番目の寿司について、
- まず人 1 の前を流れます。B_2 < A_1 なので、人 1 は何もしません。
- 次に人 2 の前を流れます。B_2 < A_2 なので、人 2 は何もしません。
- 最後に人 3 の前を流れます。B_2 \geq A_3 なので、人 3 はこれを取って食べます。
- 3 番目の寿司について、
- まず人 1 の前を流れます。B_3 < A_1 なので、人 1 は何もしません。
- 次に人 2 の前を流れます。B_3 < A_2 なので、人 2 は何もしません。
- 最後に人 3 の前を流れます。B_3 < A_3 なので、人 3 は何もしません。
- よって、誰もこの寿司を食べません。
入力例 2
3 3 1 1 1 1 1 1
出力例 2
1 1 1
入力例 3
10 5 60 83 76 45 70 91 37 58 94 22 70 39 52 33 18
出力例 3
1 7 4 10 -1
Score: 350 points
Problem Statement
There are N people numbered from 1 to N visiting a conveyor belt sushi restaurant. The gourmet level of person i is A_i.
Now, M pieces of sushi will be placed on the conveyor belt. The deliciousness of the j-th sushi is B_j. Each piece of sushi passes in front of people 1, 2, \dots, N in this order. Each person, when a sushi whose deliciousness is not less than their gourmet level passes in front of them, will take and eat that sushi; otherwise, they do nothing. A sushi that person i takes and eats will no longer pass in front of person j\ (j > i).
For each of the M pieces of sushi, determine who eats that sushi, or if nobody eats it.
Constraints
- 1 \leq N, M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
Output
Print M lines.
The j-th line (1 \leq j \leq M) should contain the number representing the person who eats the j-th sushi, or -1 if nobody eats it.
Sample Input 1
3 3 3 8 2 5 2 1
Sample Output 1
1 3 -1
- For the 1st sushi:
- It first passes in front of person 1. Since B_1 \geq A_1, person 1 takes and eats it.
- It will not pass in front of person 2 and 3.
- For the 2nd sushi:
- It first passes in front of person 1. Since B_2 < A_1, person 1 does nothing.
- Next, it passes in front of person 2. Since B_2 < A_2, person 2 does nothing.
- Finally, it passes in front of person 3. Since B_2 \geq A_3, person 3 takes and eats it.
- For the 3rd sushi:
- It first passes in front of person 1. Since B_3 < A_1, person 1 does nothing.
- Next, it passes in front of person 2. Since B_3 < A_2, person 2 does nothing.
- Finally, it passes in front of person 3. Since B_3 < A_3, person 3 does nothing.
- Therefore, nobody eats this sushi.
Sample Input 2
3 3 1 1 1 1 1 1
Sample Output 2
1 1 1
Sample Input 3
10 5 60 83 76 45 70 91 37 58 94 22 70 39 52 33 18
Sample Output 3
1 7 4 10 -1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 組のカップルが一列に座っています。
2 組のカップルであって、もともと両方のカップルは隣り合わせで座っておらず、かつ 4 人の間で席を交換することで両方のカップルが隣り合わせで座れるようになる組の個数を数えてください。
長さ 2N の数列 A=(A_1,A_2,\dots,A_{2N}) があります。A には 1, 2, \dots, N がそれぞれ 2 回ずつ登場します。
1 \leq a \lt b \leq N を満たす整数対 (a, b) であって以下の条件を全て満たすものの個数を求めてください。
- A 内において a 同士は隣接していない。
- A 内において b 同士は隣接していない。
- 次の操作を 1 回以上自由な回数行うことで、A 内において a 同士が隣接していて、かつ b 同士が隣接している状態にすることができる。
- A_i = a, A_j = b を満たす整数対 (i, j) (1 \leq i \leq 2N, 1 \leq j \leq 2N) を選び、A_i と A_j を入れ替える。
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
制約
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A には 1, 2, \dots, N がそれぞれ 2 回ずつ登場する
- 全てのテストケースに対する N の総和は 2 \times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで、\mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N
A_1 A_2 \dots A_{2N}
出力
T 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。
入力例 1
3 3 1 2 3 3 1 2 4 1 1 2 2 3 3 4 4 5 1 2 3 4 5 1 2 3 4 5
出力例 1
1 0 4
1 番目のテストケースについて考えます。
(a, b)=(1, 2) は問題文の条件を満たします。理由は次の通りです。
- A 内において 1 同士は隣接していない。
- A 内において 2 同士は隣接していない。
- (i,j)=(1, 6) として A_1 と A_6 を入れ替える操作を行うことで、1 同士が隣接していて、かつ 2 同士が隣接している状態にすることができる。
問題文の条件を満たす (a, b) は (1, 2) のみです。
Score : 400 points
Problem Statement
N couples are seated in a line.
Count the number of pairs of couples such that neither couple was originally sitting next to each other, and both couples can end up sitting next to each other by swapping seats among those four people.
There is a sequence A = (A_1, A_2, \dots, A_{2N}) of length 2N. Each of the integers 1, 2, \dots, N appears exactly twice in A.
Find the number of integer pairs (a, b) satisfying 1 \leq a < b \leq N and all of the following conditions:
- The two occurrences of a in A are not adjacent.
- The two occurrences of b in A are not adjacent.
- By performing the following operation one or more times in any order, it is possible to reach a state where the two occurrences of a in A are adjacent and the two occurrences of b in A are also adjacent.
- Choose an integer pair (i, j) (1 \leq i \leq 2N, 1 \leq j \leq 2N) such that A_i = a and A_j = b, and swap A_i with A_j.
You are given T test cases; solve each of them.
Constraints
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- Each of 1, 2, \dots, N appears exactly twice in A.
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N
A_1 A_2 \dots A_{2N}
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 3 1 2 3 3 1 2 4 1 1 2 2 3 3 4 4 5 1 2 3 4 5 1 2 3 4 5
Sample Output 1
1 0 4
Consider the first test case.
(a, b) = (1, 2) satisfies the conditions in the problem statement, for the following reasons:
- The two occurrences of 1 in A are not adjacent.
- The two occurrences of 2 in A are not adjacent.
- By performing the operation where (i, j) = (1, 6) and swapping A_1 with A_6, you can reach a state where the two occurrences of 1 are adjacent and the two occurrences of 2 are also adjacent.
(1, 2) is the only pair (a, b) that satisfies the conditions.
Time Limit: 10 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
正整数 n の 桁和 を、n を 10 進法で表したときの各桁の和として定義します。例えば 2024 の桁和は 2+0+2+4=8 です。
正整数 n が n の桁和で割り切れる時、n を 良い整数 と呼びます。例えば 2024 はその桁和である 8 で割り切れるので良い整数です。
正整数 N が与えられます。N 以下の良い整数は全部で何個ありますか？
制約
- 1 \leq N \leq 10^{14}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 以下の良い整数の個数を出力せよ。
入力例 1
20
出力例 1
13
20 以下の良い整数は 1,2,3,4,5,6,7,8,9,10,12,18,20 の 13 個です。
入力例 2
2024
出力例 2
409
入力例 3
9876543210
出力例 3
547452239
Score: 525 points
Problem Statement
The digit sum of a positive integer n is defined as the sum of the digits in the decimal notation of n. For example, the digit sum of 2024 is 2+0+2+4=8.
A positive integer n is called a good integer when n is divisible by its digit sum. For example, 2024 is a good integer because it is divisible by its digit sum of 8.
You are given a positive integer N. How many good integers are less than or equal to N?
Constraints
- 1 \leq N \leq 10^{14}
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the number of good integers less than or equal to N.
Sample Input 1
20
Sample Output 1
13
There are 13 good integers less than or equal to 20: 1,2,3,4,5,6,7,8,9,10,12,18,20.
Sample Input 2
2024
Sample Output 2
409
Sample Input 3
9876543210
Sample Output 3
547452239
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
N 個のマスが 1 列に並んでおり、順に 1, 2, \ldots, N の番号が付けられています。
M 個の整数組 (L_1, R_1), \ldots, (L_M, R_M) が与えられます。
マス j はある i に対して L_i \leq j \leq R_i を満たすとき、またそのときに限り 悪いマス であると定めます。
マス 1 から以下の行動を繰り返すことでマス N に移動できるか判定してください。
- 現在位置しているマスをマス x とする。以下の条件をすべて満たすような整数 i を選び、マス x + i に移動する。
- A \leq i \leq B
- x + i \leq N
- マス x + i は悪いマスでない
制約
- 2 \leq N \leq 10^{12}
- 0 \leq M \leq 2 \times 10^4
- 1 \leq A \leq B \leq 20
- 1 < L_i \leq R_i < N (1 \leq i \leq M)
- R_i < L_{i + 1} (1 \leq i \leq M - 1)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A B L_1 R_1 L_2 R_2 \vdots L_M R_M
出力
問題文中の行動を繰り返すことでマス N に移動できる場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
24 2 3 5 7 8 17 20
出力例 1
Yes
マス 1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24 のように移動することでマス N に移動することができます。
入力例 2
30 1 5 8 4 24
出力例 2
No
入力例 3
100 4 10 11 16 18 39 42 50 55 93 99
出力例 3
Yes
Score : 550 points
Problem Statement
There are N squares arranged in a row, labeled 1, 2, \ldots, N from left to right.
You are given M pairs of integers (L_1, R_1), \ldots, (L_M, R_M).
A square j is defined to be bad if and only if there exists some i such that L_i \leq j \leq R_i.
Determine whether you can move from square 1 to square N by repeatedly performing the following action:
- Let your current square be x. Choose an integer i that satisfies all of the following conditions, and move to square x + i.
- A \leq i \leq B
- x + i \leq N
- Square x + i is not bad.
Constraints
- 2 \leq N \leq 10^{12}
- 0 \leq M \leq 2 \times 10^4
- 1 \leq A \leq B \leq 20
- 1 < L_i \leq R_i < N \ (1 \leq i \leq M)
- R_i < L_{i+1} \ (1 \leq i \leq M - 1)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A B L_1 R_1 L_2 R_2 \vdots L_M R_M
Output
If it is possible to reach square N by repeating the action described in the problem statement, print Yes. Otherwise, print No.
Sample Input 1
24 2 3 5 7 8 17 20
Sample Output 1
Yes
You can move to square N in this way: 1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24.
Sample Input 2
30 1 5 8 4 24
Sample Output 2
No
Sample Input 3
100 4 10 11 16 18 39 42 50 55 93 99
Sample Output 3
Yes