Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
正整数 N, L, R と長さ N の正整数列 A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N}) が与えられます。
空で初期化された数列 Q と、 0 で初期化された変数 C と、 1 で初期化された変数 i を用いて以下の操作を 2N 回行います。
- 以下の行動 1, 2 のうち、いずれかを選んで行う。
- 行動 1 : Q の末尾に i を挿入し、C を \max(0, C - A_{i}) に置き換える。その後、i を 1 増やす。この行動は、操作前の i が N 以下のときのみ行える。
- 行動 2 : Q の先頭の数を x として、C に B_{x} を加算する。その後、Q の先頭の要素を削除する。この行動は、操作前の Q が空でないときのみ行える。
2N 回の操作の方法であって、最終的な C が L 以上 R 以下であるようなものの場合の数を 998244353 で割ったあまりを求めてください。
制約
- 1\leq N\leq 5000
- 1\leq L \leq R \leq \sum B
- 1\leq A_{i}\leq 5000
- 1\leq B_{i}\leq 5000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N L R
A_{1} A_{2} \dots A_{N}
B_{1} B_{2} \dots B_{N}
出力
答えを出力してください。
入力例 1
2 100 1000 2001 167 924 178
出力例 1
1
例えば以下のように 4 回の操作を行うことができます。
- 行動 1 をする。Q = (1), C = 0, i = 2 と変化する。
- 行動 2 をする。Q = (), C = 924, i = 2 と変化する。
- 行動 1 をする。Q = (2), C = 757, i = 3 と変化する。
- 行動 2 をする。Q = (), C = 935, i = 3 と変化する。
上記のように操作すると、最終的な C が 100 以上 1000 以下になります。そのような操作方法はこれしかないので、1 を出力します。
入力例 2
3 10 10 1 6 7 9 2 4
出力例 2
0
入力例 3
15 167 924 122 122 111 85 97 108 115 82 84 82 105 103 113 102 135 116 122 110 106 71 85 70 94 86 110 73 97 101 86 73
出力例 3
9576277
Score : 700 points
Problem Statement
You are given positive integers N, L, R and length-N positive integer sequences A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N}).
Using a sequence Q initialized as empty, a variable C initialized to 0, and a variable i initialized to 1, perform the following operation 2N times.
- Choose one of the following actions 1, 2 and perform it.
- Action 1 : Insert i at the end of Q, replace C with \max(0, C - A_{i}). Then, increase i by 1. This action can only be performed when i before the operation is at most N.
- Action 2 : Let x be the first number in Q, and add B_{x} to C. Then, remove the first element of Q. This action can only be performed when Q before the operation is not empty.
Find the number, modulo 998244353, of ways to perform 2N operations such that the final value of C is between L and R, inclusive.
Constraints
- 1\leq N\leq 5000
- 1\leq L \leq R \leq \sum B
- 1\leq A_{i}\leq 5000
- 1\leq B_{i}\leq 5000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L R
A_{1} A_{2} \dots A_{N}
B_{1} B_{2} \dots B_{N}
Output
Output the answer.
Sample Input 1
2 100 1000 2001 167 924 178
Sample Output 1
1
For example, you can perform four operations as follows.
- Perform action 1. Then, Q = (1), C = 0, i = 2.
- Perform action 2. Then, Q = (), C = 924, i = 2.
- Perform action 1. Then, Q = (2), C = 757, i = 3.
- Perform action 2. Then, Q = (), C = 935, i = 3.
Performing operations as above makes the final value of C between 100 and 1000 (inclusive). This is the only such way to perform operations, so output 1.
Sample Input 2
3 10 10 1 6 7 9 2 4
Sample Output 2
0
Sample Input 3
15 167 924 122 122 111 85 97 108 115 82 84 82 105 103 113 102 135 116 122 110 106 71 85 70 94 86 110 73 97 101 86 73
Sample Output 3
9576277
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
正整数 N, K と、(1, 2, \dots, NK) の順列 P = (P_{1}, P_{2}, \dots, P_{NK}) が与えられます。
Alice は以下の操作を繰り返し、P を昇順ソートします。
- 1 以上 NK 以下の整数 i, j(i\neq j) を選び、P_{i} と P_{j} を入れ替える。このとき、|i - j| が N の倍数なら、Alice は 1 ポイントもらえる。
Alice は最小の操作回数で P を昇順ソートし、その上でもらえるポイントの和を最大化する行動をします。
Alice が得るポイントの和を出力してください。
制約
- 1\leq N\leq 500
- 1\leq K\leq 10
- (P_{1}, P_{2}, \dots , P_{NK}) は (1, 2, \dots, NK) の順列
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N K
P_{1} P_{2} \dots P_{NK}
出力
答えを出力してください。
入力例 1
3 2 1 6 5 3 2 4
出力例 1
2
例えば以下のように 4 回操作すると P を昇順ソートできます。
- (i, j) = (2, 5) として操作する。操作後、P = (1, 2, 5, 3, 6, 4) となる。
- (i, j) = (4, 6) として操作する。操作後、P = (1, 2, 5, 4, 6, 3) となる。
- (i, j) = (3, 5) として操作する。操作後、P = (1, 2, 6, 4, 5, 3) となる。
- (i, j) = (3, 6) として操作する。操作後、P = (1, 2, 3, 4, 5, 6) となる。
上記の 4 回の操作のうち、1 回目と 4 回目の操作で Alice はそれぞれ 1 ポイントもらえるため、Alice は合計で 2 ポイントもらえます。
このように操作することが最小の操作回数で P を昇順ソートし、その上でもらえるポイントの和を最大化する行動のひとつであるため、2 を出力します。
入力例 2
1 1 1
出力例 2
0
入力例 3
4 6 10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11
出力例 3
7
Score : 800 points
Problem Statement
You are given positive integers N, K and a permutation P = (P_{1}, P_{2}, \dots, P_{NK}) of (1, 2, \dots, NK).
Alice repeatedly performs the following operation to sort P in ascending order.
- Choose integers i and j (i\neq j) where 1 \leq i, j \leq NK, and swap P_{i} and P_{j}. If |i - j| is a multiple of N, Alice gets 1 point.
Alice sorts P in ascending order with the minimum number of operations, and under that condition, she maximizes the sum of points she gets.
Output the sum of points Alice gets.
Constraints
- 1\leq N\leq 500
- 1\leq K\leq 10
- (P_{1}, P_{2}, \dots , P_{NK}) is a permutation of (1, 2, \dots, NK)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
P_{1} P_{2} \dots P_{NK}
Output
Output the answer.
Sample Input 1
3 2 1 6 5 3 2 4
Sample Output 1
2
For example, P can be sorted in ascending order with four operations as follows.
- Perform the operation with (i, j) = (2, 5). After the operation, P = (1, 2, 5, 3, 6, 4).
- Perform the operation with (i, j) = (4, 6). After the operation, P = (1, 2, 5, 4, 6, 3).
- Perform the operation with (i, j) = (3, 5). After the operation, P = (1, 2, 6, 4, 5, 3).
- Perform the operation with (i, j) = (3, 6). After the operation, P = (1, 2, 3, 4, 5, 6).
Among the above four operations, Alice gets 1 point from each of the 1st and 4th operations, so Alice gets a total of 2 points.
This sequence of operations is one of the ways to sort P in ascending order with the minimum number of operations and maximize the sum of points under that condition, so output 2.
Sample Input 2
1 1 1
Sample Output 2
0
Sample Input 3
4 6 10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
正整数 N と (1, 2, \dots , N) の順列 P = (P_{1}, P_{2}, \dots, P_{N})が与えられます。
Q 個のクエリを処理してください。各クエリでは非負整数 A_{0}, A_{1}, A_{2} が与えられるので以下の問題の答えを出力してください。なお、A_{0} + A_{1} + A_{2} = N であることが保証されます。
長さ N の数列 B であって、以下の条件をすべて満たす数列を good な数列とします。
- B_{i} = 0 が成り立つ 1 以上 N 以下の整数 i はちょうど A_{0} 個
- B_{i} = 1 が成り立つ 1 以上 N 以下の整数 i はちょうど A_{1} 個
- B_{i} = 2 が成り立つ 1 以上 N 以下の整数 i はちょうど A_{2} 個
長さ N の数列 B に対して、スコアを以下のように定義します。
- \displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})
ただし、\mathrm{MEX}(x, y) は x でも y でもない最小の非負整数であると定義します。
good な数列全てに対するスコアの最大値を求めてください。
制約
- 1\leq N\leq 3\times 10^{5}
- (P_{1}, P_{2}, \dots , P_{N}) は (1, 2, \dots , N) の順列
- 1\leq Q\leq 3\times 10^{5}
- 0\leq A_{i}
- それぞれのクエリに対して A_{0} + A_{1} + A_{2} = N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N
P_{1} P_{2} \dots P_{N}
Q
query_{1}
query_{2}
\cdots
query_{Q}
ここで query_{i} は i 番目のクエリであり、以下の形式で与えられます。
A_{0} A_{1} A_{2}
出力
Q 行出力してください。i 行目には i 番目のクエリの答えを出力してください。
入力例 1
3 2 3 1 2 1 1 1 1 0 2
出力例 1
3 2
1 番目のクエリについて、B = (0, 1, 2) は good な数列です。この数列のスコアは \mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3 より 3 です。3 よりスコアが大きい good な数列は存在しないので、1 行目には 3 を出力します。
入力例 2
7 6 3 4 5 2 1 7 4 2 2 3 4 1 2 0 3 4 1 2 4
出力例 2
8 9 0 4
入力例 3
9 1 6 7 3 5 8 9 2 4 10 5 3 1 0 7 2 0 6 3 1 3 5 4 0 5 4 2 3 1 5 3 4 5 0 2 2 5 2 5 2
出力例 3
14 0 0 4 7 11 4 13 8 8
Score : 900 points
Problem Statement
You are given a positive integer N and a permutation P = (P_{1}, P_{2}, \dots, P_{N}) of (1, 2, \dots , N).
Process Q queries. In each query, non-negative integers A_{0}, A_{1}, A_{2} are given, so output the answer to the following problem. It is guaranteed that A_{0} + A_{1} + A_{2} = N.
A sequence B of length N is called a good sequence if and only if it satisfies all of the following conditions:
- There are exactly A_{0} integers i with 1 \leq i \leq N such that B_{i} = 0.
- There are exactly A_{1} integers i with 1 \leq i \leq N such that B_{i} = 1.
- There are exactly A_{2} integers i with 1 \leq i \leq N such that B_{i} = 2.
For a sequence B of length N, the score is defined as follows:
- \displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})
Here, \mathrm{MEX}(x, y) is defined as the minimum non-negative integer that is neither x nor y.
Find the maximum value of the score over all good sequences.
Constraints
- 1\leq N\leq 3\times 10^{5}
- (P_{1}, P_{2}, \dots , P_{N}) is a permutation of (1, 2, \dots , N).
- 1\leq Q\leq 3\times 10^{5}
- 0\leq A_{i}
- For each query, A_{0} + A_{1} + A_{2} = N.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
P_{1} P_{2} \dots P_{N}
Q
query_{1}
query_{2}
\cdots
query_{Q}
Here query_{i} is the i-th query, given in the following format:
A_{0} A_{1} A_{2}
Output
Output Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
3 2 3 1 2 1 1 1 1 0 2
Sample Output 1
3 2
For the first query, B = (0, 1, 2) is a good sequence. The score of this sequence is \mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3, which is 3. There is no good sequence with a score greater than 3, so output 3 on the first line.
Sample Input 2
7 6 3 4 5 2 1 7 4 2 2 3 4 1 2 0 3 4 1 2 4
Sample Output 2
8 9 0 4
Sample Input 3
9 1 6 7 3 5 8 9 2 4 10 5 3 1 0 7 2 0 6 3 1 3 5 4 0 5 4 2 3 1 5 3 4 5 0 2 2 5 2 5 2
Sample Output 3
14 0 0 4 7 11 4 13 8 8
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1000 点
問題文
整数 N, L, R が与えられます。
これらの整数について、以下が成り立ちます。
- 2 \leq N
- 0\leq L < R \leq N
- (L, R)\neq (0, N)
長さ N の数列 A = (A_{0}, A_{1}, \dots , A_{N - 1}) を A = (0, 1, \dots, N - 1) と初期化します。
(R - L, R - L + 1, \dots , N - 1) の順列 P = (P_{0}, P_{1}, \dots, P_{N - (R - L) - 1}) をひとつ選び、i = 0, 1, \dots N - (R - L) - 1 の順に以下の操作を行います。
- P_{i} を |A| で割ったあまりを a とし、A_{a} を A から削除する(要素の削除後、数列 A の添え字は 0 から振り直されるものとする)
最終的に A = (L, L + 1, \dots , R - 1) となるような P が存在するか判定し、存在するならばそのような P をひとつ出力してください。
制約
- 2\leq N\leq 2\times 10^{5}
- 0\leq L < R\leq N
- (L, R) \neq (0, N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N L R
出力
A = (L, L + 1, \dots , R - 1) となるような P が存在しない場合は No と出力してください。
存在する場合は以下の形式で答えを出力してください。
Yes
P_{0} P_{1} \cdots P_{N - (R - L) - 1}
形式的には、1 行目に Yes を出力し、2 行目に P_{0}, P_{1}, \dots , P_{N - (R - L) - 1} を空白区切りで出力してください。
解が複数存在する場合はどれを出力しても正解とみなされます。
入力例 1
6 3 5
出力例 1
Yes 2 4 5 3
P = (2, 4, 5, 3) を選んだとき、A = (0, 1, 2, 3, 4, 5) から以下のように 4 回操作します。
-
P_{0} = 2 を |A| = 6 で割ったあまりは 2 なので、A_{2} = 2 を A から削除します。すると、A = (A_{0}, A_{1}, A_{2}, A_{3}, A_{4}) = (0, 1, 3, 4, 5) となります。
-
P_{1} = 4 を |A| = 5 で割ったあまりは 4 なので、A_{4} = 5 を A から削除します。すると、A = (A_{0}, A_{1}, A_{2}, A_{3}) = (0, 1, 3, 4) となります。
-
P_{2} = 5 を |A| = 4 で割ったあまりは 1 なので、A_{1} = 1 を A から削除します。すると、A = (A_{0}, A_{1}, A_{2}) = (0, 3, 4) となります。
-
P_{3} = 3 を |A| = 3 で割ったあまりは 0 なので、A_{0} = 0 を A から削除します。すると、A = (A_{0}, A_{1}) = (3, 4) となります。
よって、P = (2, 4, 5, 3) とすることで目標を達成できます。また、P = (5, 2, 4, 3) を出力しても良いです。
入力例 2
9 2 4
出力例 2
Yes 4 5 6 7 3 8 2
入力例 3
178 68 167
出力例 3
No
Score : 1000 points
Problem Statement
You are given integers N, L, R.
These integers satisfy the following:
- 2 \leq N
- 0\leq L < R \leq N
- (L, R)\neq (0, N)
Initialize a length-N sequence A = (A_{0}, A_{1}, \dots , A_{N - 1}) as A = (0, 1, \dots, N - 1).
Choose a permutation P = (P_{0}, P_{1}, \dots, P_{N - (R - L) - 1}) of (R - L, R - L + 1, \dots , N - 1), and perform the following operation for i = 0, 1, \dots N - (R - L) - 1 in this order.
- Let a be the remainder when P_{i} is divided by |A|, and remove A_{a} from A (after removing an element, the indices of sequence A are renumbered starting from 0).
Determine whether there exists a P such that A = (L, L + 1, \dots , R - 1) in the end, and if it exists, output one such P.
Constraints
- 2\leq N\leq 2\times 10^{5}
- 0\leq L < R\leq N
- (L, R) \neq (0, N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L R
Output
If there is no P that makes A = (L, L + 1, \dots , R - 1), output No.
If it exists, output a solution in the following format:
Yes
P_{0} P_{1} \cdots P_{N - (R - L) - 1}
Formally, output Yes on the first line, and output P_{0}, P_{1}, \dots , P_{N - (R - L) - 1} separated by spaces on the second line.
If there are multiple solutions, any of them will be considered correct.
Sample Input 1
6 3 5
Sample Output 1
Yes 2 4 5 3
When choosing P = (2, 4, 5, 3), perform four operations on A = (0, 1, 2, 3, 4, 5) as follows.
-
The remainder when P_{0} = 2 is divided by |A| = 6 is 2, so remove A_{2} = 2 from A. Then, A = (A_{0}, A_{1}, A_{2}, A_{3}, A_{4}) = (0, 1, 3, 4, 5).
-
The remainder when P_{1} = 4 is divided by |A| = 5 is 4, so remove A_{4} = 5 from A. Then, A = (A_{0}, A_{1}, A_{2}, A_{3}) = (0, 1, 3, 4).
-
The remainder when P_{2} = 5 is divided by |A| = 4 is 1, so remove A_{1} = 1 from A. Then, A = (A_{0}, A_{1}, A_{2}) = (0, 3, 4).
-
The remainder when P_{3} = 3 is divided by |A| = 3 is 0, so remove A_{0} = 0 from A. Then, A = (A_{0}, A_{1}) = (3, 4).
Therefore, the goal can be achieved by setting P = (2, 4, 5, 3). It is also acceptable to output P = (5, 2, 4, 3).
Sample Input 2
9 2 4
Sample Output 2
Yes 4 5 6 7 3 8 2
Sample Input 3
178 68 167
Sample Output 3
No