Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 人の生徒からなるクラスがあり、i\,(1 \leq i \leq N) 番目の生徒の身長は A_i です。
j=1,2,\ldots,Q について、以下の質問に答えてください。
- N 人のうち、身長が x_j 以上の生徒は何人か？
制約
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
出力
Q 行出力せよ。
j\,(1 \leq j \leq Q) 行目には身長が x_j 以上の生徒の数を出力せよ。
入力例 1
3 1 100 160 130 120
出力例 1
2
身長が 120 以上の生徒は 2 番目の生徒と 3 番目の生徒です。
入力例 2
5 5 1 2 3 4 5 6 5 4 3 2
出力例 2
0 1 2 3 4
入力例 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
出力例 3
5 3 5 5 5
Score : 300 points
Problem Statement
There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.
For each j=1,2,\ldots,Q, answer the following question.
- How many of the N students have a height of at least x_j?
Constraints
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
Output
Print Q lines.
The j-th line (1 \leq j \leq Q) should contain the number of students with a height of at least x_j.
Sample Input 1
3 1 100 160 130 120
Sample Output 1
2
The students with a height of at least 120 are the 2-nd and 3-rd ones.
Sample Input 2
5 5 1 2 3 4 5 6 5 4 3 2
Sample Output 2
0 1 2 3 4
Sample Input 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
Sample Output 3
5 3 5 5 5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 4
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
入力例 2
31 41 592
出力例 2
798416518
答えを 998244353 で割った余りを出力してください。
Score : 300 points
Problem Statement
How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
Since the count can get enormous, find it modulo 998244353.
Constraints
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 3 4
Sample Output 1
6
The following six sequences satisfy the conditions.
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
Sample Input 2
31 41 592
Sample Output 2
798416518
Be sure to print the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
数列 (A_1,\ldots,A_K) を使って、高橋君と青木君が石取りゲームをします。
最初、山には N 個の石があります。高橋君から順に、二人が交互に次の操作を行います。
- 現在山にある石の個数以下であるような A_i を 1 つ選ぶ。山から A_i 個の石を取り除く。
山から石がなくなったとき、ゲームは終了します。
二人がともに、ゲーム終了までに自分が取り除いた石の個数を最大化しようとするとき、高橋君は何個の石を取り除くことができますか？
制約
- 1 \leq N \leq 10^4
- 1 \leq K \leq 100
- 1 = A_1 < A_2 < \ldots < A_K \leq N
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_K
出力
答えを出力せよ。
入力例 1
10 2 1 4
出力例 1
5
ゲームの進行の一例は以下の通りです。
- 高橋君が山から 4 個の石を取り除く。
- 青木君が山から 4 個の石を取り除く。
- 高橋君が山から 1 個の石を取り除く。
- 青木君が山から 1 個の石を取り除く。
この例では高橋君は 5 個の石を取り除くことができます。高橋君が 6 個以上の石を取り除くことはできないためこれが最大です。
高橋君は 5 個の石を取り除くことができるゲームの進行の例には、他にも次のようなものがあります。
- 高橋君が山から 1 個の石を取り除く。
- 青木君が山から 4 個の石を取り除く。
- 高橋君が山から 4 個の石を取り除く。
- 青木君が山から 1 個の石を取り除く。
入力例 2
11 4 1 2 3 6
出力例 2
8
ゲームの進行の一例は以下の通りです。
- 高橋君が山から 6 個の石を取り除く。
- 青木君が山から 3 個の石を取り除く。
- 高橋君が山から 2 個の石を取り除く。
この例では高橋君は 8 個の石を取り除くことができます。高橋君が 9 個以上の石を取り除くことはできないためこれが最大です。
入力例 3
10000 10 1 2 4 8 16 32 64 128 256 512
出力例 3
5136
Score : 400 points
Problem Statement
Takahashi and Aoki will play a game of taking stones using a sequence (A_1, \ldots, A_K).
There is a pile that initially contains N stones. The two players will alternately perform the following operation, with Takahashi going first.
- Choose an A_i that is at most the current number of stones in the pile. Remove A_i stones from the pile.
The game ends when the pile has no stones.
If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?
Constraints
- 1 \leq N \leq 10^4
- 1 \leq K \leq 100
- 1 = A_1 < A_2 < \ldots < A_K \leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_K
Output
Print the answer.
Sample Input 1
10 2 1 4
Sample Output 1
5
Below is one possible progression of the game.
- Takahashi removes 4 stones from the pile.
- Aoki removes 4 stones from the pile.
- Takahashi removes 1 stone from the pile.
- Aoki removes 1 stone from the pile.
In this case, Takahashi removes 5 stones. There is no way for him to remove 6 or more stones, so this is the maximum.
Below is another possible progression of the game where Takahashi removes 5 stones.
- Takahashi removes 1 stone from the pile.
- Aoki removes 4 stones from the pile.
- Takahashi removes 4 stones from the pile.
- Aoki removes 1 stone from the pile.
Sample Input 2
11 4 1 2 3 6
Sample Output 2
8
Below is one possible progression of the game.
- Takahashi removes 6 stones.
- Aoki removes 3 stones.
- Takahashi removes 2 stones.
In this case, Takahashi removes 8 stones. There is no way for him to remove 9 or more stones, so this is the maximum.
Sample Input 3
10000 10 1 2 4 8 16 32 64 128 256 512
Sample Output 3
5136
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。
A の部分列であって、隣接する 2 項の差の絶対値が D 以下であるようなものの長さの最大値を求めてください。
ただし、数列 A の部分列とは、A の要素を 0 個以上選んで削除し、残った要素を元の順序を保って並べた数列のことを指します。
制約
- 1 \leq N \leq 5 \times 10^5
- 0 \leq D \leq 5 \times 10^5
- 1 \leq A_i \leq 5 \times 10^5
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
4 2 3 5 1 2
出力例 1
3
A の部分列 (3, 1, 2) は隣接する 2 項の差の絶対値が 2 以下です。
入力例 2
5 10 10 20 100 110 120
出力例 2
3
入力例 3
11 7 21 10 3 19 28 12 11 3 3 15 16
出力例 3
6
Score: 525 points
Problem Statement
You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N.
Find the maximum length of a subsequence of A such that the absolute difference between any two adjacent terms is at most D.
A subsequence of a sequence A is a sequence that can be obtained by deleting zero or more elements from A and arranging the remaining elements in their original order.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 0 \leq D \leq 5 \times 10^5
- 1 \leq A_i \leq 5 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 2 3 5 1 2
Sample Output 1
3
The subsequence (3, 1, 2) of A has absolute differences of at most 2 between adjacent terms.
Sample Input 2
5 10 10 20 100 110 120
Sample Output 2
3
Sample Input 3
11 7 21 10 3 19 28 12 11 3 3 15 16
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 個のサイコロがあります。 i = 1, 2, \ldots, N について、i 番目のサイコロを振ると 1 以上 A_i 以下の整数の出目がそれぞれ等確率でランダムにでます。
N 個のサイコロすべてを同時に振るとき、その結果が下記の条件を満たす確率を \text{mod } 998244353 で求めてください。
N 個のサイコロの中からいくつか（ N 個全部でも良い）を選ぶ方法であって、選んだサイコロの出目の和がちょうど 10 であるようなものが存在する。
確率 \text{mod } 998244353 の定義
この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
制約
- 1 \leq N \leq 100
- 1 \leq A_i \leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
4 1 7 2 9
出力例 1
942786334
例えば、1, 2, 3, 4 個目のサイコロの出目が順に 1, 3, 2, 7 だった場合、この結果は問題文中の条件を満たします。 実際、2, 4 番目のサイコロを選択すると、選んだサイコロの出目の和が 3 + 7 = 10 になります。 また、1, 3, 4 番目のサイコロを選択しても、選んだサイコロの出目の和が 1 + 2 + 7 = 10 になります。
一方、1, 2, 3, 4 個目のサイコロの出目が順に 1, 6, 1, 5 だった場合、 どのようにサイコロを選んでも選んだサイコロの出目の和が 10 にならないため、この結果は問題文中の条件を満たしません。
この入力例では、N 個のサイコロを振った結果が問題文中の条件を満たす確率は \frac{11}{18} です。 よって、その \text{mod } 998244353 における値である 942786334 を出力します。
入力例 2
7 1 10 100 1000 10000 100000 1000000
出力例 2
996117877
Score : 500 points
Problem Statement
We have N dice. For each i = 1, 2, \ldots, N, when the i-th die is thrown, it shows a random integer between 1 and A_i, inclusive, with equal probability.
Find the probability, modulo 998244353, that the following condition is satisfied when the N dice are thrown simultaneously.
There is a way to choose some (possibly all) of the N dice so that the sum of their results is 10.
How to find a probability modulo 998244353
It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction \frac{y}{x}, then x is not divisible by 998244353.
Here, there is a unique integer z such that xz \equiv y \pmod{998244353}. Report this z.
Constraints
- 1 \leq N \leq 100
- 1 \leq A_i \leq 10^6
- 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
4 1 7 2 9
Sample Output 1
942786334
For instance, if the first, second, third, and fourth dice show 1, 3, 2, and 7, respectively, these results satisfy the condition. In fact, if the second and fourth dice are chosen, the sum of their results is 3 + 7 = 10. Alternatively, if the first, third, and fourth dice are chosen, the sum of their results is 1 + 2 + 7 = 10.
On the other hand, if the first, second, third, and fourth dice show 1, 6, 1, and 5, respectively, there is no way to choose some of them so that the sum of their results is 10, so the condition is not satisfied.
In this sample input, the probability of the results of the N dice satisfying the condition is \frac{11}{18}. Thus, print this value modulo 998244353, that is, 942786334.
Sample Input 2
7 1 10 100 1000 10000 100000 1000000
Sample Output 2
996117877