実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
正整数 N,K が与えられます．
1 以上 N 以下の整数がそれぞれ K 回ずつ登場する長さ NK の整数列を good な整数列と呼ぶことにします．
good な整数列の個数を S とおきます． 辞書順で \operatorname{floor}((S+1)/2) 番目の good な整数列を求めてください． なお，\operatorname{floor}(x) は x を超えない最大の整数を表します．
数列の辞書順とは？
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは，下記の 1. と 2. のどちらかが成り立つことを言います． ここで，|S|, |T| はそれぞれ S, T の長さを表します．
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})．
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して，下記の 2 つがともに成り立つ．
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい．
制約
- 1 \leq N \leq 500
- 1 \leq K \leq 500
- 入力される値はすべて整数
入力
入力は標準入力から以下の形式で与えられる．
N K
出力
答えの整数列を，要素を空白区切りにして出力せよ．
入力例 1
2 2
出力例 1
1 2 2 1
good な整数列は以下の 6 通りです．
- (1,1,2,2)
- (1,2,1,2)
- (1,2,2,1)
- (2,1,1,2)
- (2,1,2,1)
- (2,2,1,1)
よって，この中で辞書順で 3 番目の (1,2,2,1) が答えになります．
入力例 2
1 5
出力例 2
1 1 1 1 1
入力例 3
6 1
出力例 3
3 6 5 4 2 1
入力例 4
3 3
出力例 4
2 2 2 1 3 3 3 1 1
Score : 400 points
Problem Statement
You are given positive integers N and K.
An integer sequence of length NK where each integer from 1 to N appears exactly K times is called a good integer sequence.
Let S be the number of good integer sequences. Find the \operatorname{floor}((S+1)/2)-th good integer sequence in lexicographical order. Here, \operatorname{floor}(x) represents the largest integer not exceeding x.
What is lexicographical order for sequences?
A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if either 1. or 2. below holds. Here, |S| and |T| represent the lengths of S and T, respectively.
- |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i is (numerically) smaller than T_i.
Constraints
- 1 \leq N \leq 500
- 1 \leq K \leq 500
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print the desired integer sequence, with elements separated by spaces.
Sample Input 1
2 2
Sample Output 1
1 2 2 1
There are six good integer sequences:
- (1,1,2,2)
- (1,2,1,2)
- (1,2,2,1)
- (2,1,1,2)
- (2,1,2,1)
- (2,2,1,1)
Therefore, the answer is the 3rd sequence in lexicographical order, (1,2,2,1).
Sample Input 2
1 5
Sample Output 2
1 1 1 1 1
Sample Input 3
6 1
Sample Output 3
3 6 5 4 2 1
Sample Input 4
3 3
Sample Output 4
2 2 2 1 3 3 3 1 1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
長さ N の整数列 A=(A_1,A_2,\cdots,A_N),B=(B_1,B_2,\cdots,B_N) 及び整数 K が与えられます．
あなたは次の操作を 0 回以上行うことができます．
- 整数 i,j (1 \leq i,j \leq N) を選ぶ． ただしここで |i-j| \leq K を満たす必要がある． そして A_i の値を A_j に変更する．
A を B に一致させることが可能かどうか判定してください．
1 つの入力につきテストケースは T 個あります．
制約
- 1 \leq T \leq 125000
- 1 \leq K < N \leq 250000
- 1 \leq A_i,B_i \leq N
- ひとつの入力の中のテストケースすべてにわたる N の総和は 250000 以下である
- 入力される値はすべて整数
入力
入力は標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各テストケースは以下の形式で与えられる。
N K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
各テストケースに対し，A を B に一致させることが可能なら Yes，不可能なら No と出力せよ．
入力例 1
4 3 1 1 1 2 1 2 2 5 4 2 4 5 1 3 2 1 3 2 2 13 1 3 1 3 3 5 3 3 4 2 2 2 5 1 5 3 3 3 4 2 2 2 2 5 5 1 3 20 14 10 6 6 19 13 16 15 15 2 10 2 16 9 12 2 6 13 5 5 9 5 9 6 2 10 19 16 15 13 12 10 2 9 6 5 16 19 12 15 13
出力例 1
Yes Yes No Yes
1 つめのテストケースについて考えます． i=2,j=3 を選んで操作すると，A_2 の値が A_3=2 に変更され，A=(1,2,2) になります．
Score : 600 points
Problem Statement
You are given integer sequences of length N: A=(A_1,A_2,\cdots,A_N) and B=(B_1,B_2,\cdots,B_N), and an integer K.
You can perform the following operation zero or more times.
- Choose integers i and j (1 \leq i,j \leq N). Here, |i-j| \leq K must hold. Then, change the value of A_i to A_j.
Determine whether it is possible to make A identical to B.
There are T test cases for each input.
Constraints
- 1 \leq T \leq 125000
- 1 \leq K < N \leq 250000
- 1 \leq A_i,B_i \leq N
- The sum of N across all test cases in each input is at most 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each test case is given in the following format:
N K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
Output
For each test case, print Yes if it is possible to make A identical to B, and No otherwise.
Sample Input 1
4 3 1 1 1 2 1 2 2 5 4 2 4 5 1 3 2 1 3 2 2 13 1 3 1 3 3 5 3 3 4 2 2 2 5 1 5 3 3 3 4 2 2 2 2 5 5 1 3 20 14 10 6 6 19 13 16 15 15 2 10 2 16 9 12 2 6 13 5 5 9 5 9 6 2 10 19 16 15 13 12 10 2 9 6 5 16 19 12 15 13
Sample Output 1
Yes Yes No Yes
Consider the first test case. If we operate with i=2 and j=3, the value of A_2 will be changed to A_3=2, resulting in A=(1,2,2).
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) であって，次の M 個の条件をすべて満たすものの個数を 998244353 で割ったあまりを求めてください．
- i 番目の条件: P_{L_i},P_{L_i+1},\cdots,P_{R_i} の中の最大値は P_{X_i} ではない． ここで，L_i,R_i,X_i は入力で与えられる整数である．
制約
- 1 \leq N \leq 500
- 1 \leq M \leq 10^5
- 1 \leq L_i \leq X_i \leq R_i \leq N
- 入力される値はすべて整数
入力
入力は標準入力から以下の形式で与えられる。
N M L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_M R_M X_M
出力
答えを出力せよ．
入力例 1
3 2 1 3 2 1 2 1
出力例 1
1
条件を満たすのは P=(1,2,3) の 1 通りのみです．
入力例 2
5 1 1 1 1
出力例 2
0
入力例 3
10 5 3 8 4 3 10 4 1 7 2 1 8 3 3 8 7
出力例 3
1598400
入力例 4
15 17 2 11 9 2 15 13 1 14 2 5 11 5 3 15 11 1 6 2 4 15 12 3 11 6 9 13 10 2 14 6 10 15 11 1 8 6 6 14 8 2 10 2 6 12 6 3 14 12 2 6 2
出力例 4
921467228
Score : 600 points
Problem Statement
Find the number, modulo 998244353, of permutations P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) that satisfy all of the following M conditions.
- The i-th condition: The maximum among P_{L_i},P_{L_i+1},\cdots,P_{R_i} is not P_{X_i}. Here, L_i, R_i, and X_i are integers given in the input.
Constraints
- 1 \leq N \leq 500
- 1 \leq M \leq 10^5
- 1 \leq L_i \leq X_i \leq R_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_M R_M X_M
Output
Print the answer.
Sample Input 1
3 2 1 3 2 1 2 1
Sample Output 1
1
Only one permutation, P=(1,2,3), satisfies the conditions.
Sample Input 2
5 1 1 1 1
Sample Output 2
0
Sample Input 3
10 5 3 8 4 3 10 4 1 7 2 1 8 3 3 8 7
Sample Output 3
1598400
Sample Input 4
15 17 2 11 9 2 15 13 1 14 2 5 11 5 3 15 11 1 6 2 4 15 12 3 11 6 9 13 10 2 14 6 10 15 11 1 8 6 6 14 8 2 10 2 6 12 6 3 14 12 2 6 2
Sample Output 4
921467228
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
1 から N までの番号のついた N 頂点からなる木があります． i 番目の辺は頂点 A_i と頂点 B_i を結ぶ辺です． ここで N は偶数で，さらにこの木は完全マッチングを持ちます． 具体的には，各 i (1 \leq i \leq N/2) に対し，A_i=i \times 2-1,B_i=i \times 2 が保証されます．
あなたは以下の操作を N/2 回行います．
- 葉 (次数がちょうど 1 の頂点) を 2 つ選び，木から削除する． ただしここで，削除したあとの木も完全マッチングを持つ必要がある． なお，この問題では頂点が 0 個の場合も木と呼ぶことにする．
各操作について，そのスコアを「選んだ 2 つの頂点の間の距離 (その 2 つの頂点を結ぶ単純パス上の辺の個数) 」とします．
スコアの合計を最大化するような手順を 1 つ示してください． なお，この問題の制約下で N/2 回の操作を完了する手順が常に存在することが証明できます．
制約
- 2 \leq N \leq 250000
- N は偶数
- 1 \leq A_i < B_i \leq N (1 \leq i \leq N-1)
- A_i=i \times 2 -1,B_i=i \times 2 (1 \leq i \leq N/2)
- 与えられるグラフは木である
- 入力される値はすべて整数
入力
入力は標準入力から以下の形式で与えられる。
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
出力
答えを以下の形式で出力せよ．
X_1 Y_1
X_2 Y_2
\vdots
X_{N/2} Y_{N/2}
ここで，X_i,Y_i は i 回目の操作で選ぶ 2 つの頂点である． 解が複数存在する場合，どれを出力しても構わない．
入力例 1
4 1 2 3 4 2 3
出力例 1
4 1 2 3
出力例の手順は以下の通りです．
- 1 回目の操作: 頂点 4,1 を消す．残る木は頂点 2,3 からなり，完全マッチングを持つ．操作のスコアは 3 である．
- 2 回目の操作: 頂点 2,3 を消す．残る木は 0 頂点からなり，完全マッチングを持つ．操作のスコアは 1 である．
- スコアの合計は 3+1=4 になる．
スコアの合計を 4 より大きくすることはできないので，この入力例はこの出力で正解できます．
入力例 2
8 1 2 3 4 5 6 7 8 2 3 1 5 1 7
出力例 2
4 8 7 6 5 3 2 1
入力例 3
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 8 4 11 5 12 7 13 11 14 9 13
出力例 3
1 6 5 2 8 12 3 7 10 4 11 9 13 14
入力例 4
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 8 10 16 18 16 19 5 9 10 17 2 13 7 14 3 7 3 12
出力例 4
6 1 2 15 20 13 14 19 16 4 11 18 17 12 3 5 9 7 8 10
Score : 800 points
Problem Statement
There is a tree with N vertices numbered from 1 to N. The i-th edge connects vertices A_i and B_i. Here, N is even, and furthermore, this tree has a perfect matching. Specifically, for each i (1 \leq i \leq N/2), it is guaranteed that A_i=i \times 2-1 and B_i=i \times 2.
You will perform the following operation N/2 times:
- Choose two leaves (vertices with degree exactly 1) and remove them from the tree. Here, the tree after removal must still have a perfect matching. In this problem, we consider a graph with zero vertices to be a tree as well.
For each operation, its score is defined as the distance between the two chosen vertices (the number of edges on the simple path connecting the two vertices).
Show one procedure that maximizes the total score. It can be proved that there always exists a procedure to complete N/2 operations under the constraints of this problem.
Constraints
- 2 \leq N \leq 250000
- N is even.
- 1 \leq A_i < B_i \leq N (1 \leq i \leq N-1)
- A_i=i \times 2 -1, B_i=i \times 2 (1 \leq i \leq N/2)
- The given graph is a tree.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
Output
Print a solution in the following format:
X_1 Y_1
X_2 Y_2
\vdots
X_{N/2} Y_{N/2}
Here, X_i and Y_i are the two vertices chosen in the i-th operation. If there are multiple solutions, you may print any of them.
Sample Input 1
4 1 2 3 4 2 3
Sample Output 1
4 1 2 3
The procedure in the sample output is as follows:
- 1st operation: Remove vertices 4 and 1. The remaining tree has vertices 2 and 3, and a perfect matching. The score of this operation is 3.
- 2nd operation: Remove vertices 2 and 3. The remaining tree has zero vertices and a perfect matching. The score of this operation is 1.
- The total score is 3 + 1 = 4.
It is impossible to make the total score greater than 4, so this output solves this sample input.
Sample Input 2
8 1 2 3 4 5 6 7 8 2 3 1 5 1 7
Sample Output 2
4 8 7 6 5 3 2 1
Sample Input 3
14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 8 4 11 5 12 7 13 11 14 9 13
Sample Output 3
1 6 5 2 8 12 3 7 10 4 11 9 13 14
Sample Input 4
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 8 10 16 18 16 19 5 9 10 17 2 13 7 14 3 7 3 12
Sample Output 4
6 1 2 15 20 13 14 19 16 4 11 18 17 12 3 5 9 7 8 10
実行時間制限: 7 sec / メモリ制限: 1024 MiB
配点 : 900 点
問題文
1 から N までの番号のついた N 頂点からなる根付き木があります． 根は頂点 1 で，頂点 i (2 \leq i \leq N) の親は頂点 P_i (P_i<i) です．
また，1 以上 N 以下の整数からなる長さ M の整数列 A=(A_1,A_2,\cdots,A_M),B=(B_1,B_2,\cdots,B_M) があります．
A が good であるとは，各 i に対し，頂点 A_i が頂点 B_i の先祖であるかまたは A_i=B_i を満たすことを意味します． 最初，A は good です．
A に対する以下の操作を考えます．
- 整数 i (1 \leq i \leq M-1) を選び，A_i と A_{i+1} の値を入れ替える． ただし，操作後の A も good である必要がある．
A に 0 回以上操作を行った結果としてあり得る数列の個数を 998244353 で割ったあまりを求めてください．
制約
- 2 \leq N \leq 250000
- 2 \leq M \leq 250000
- 1 \leq P_i <i
- 1 \leq A_i \leq B_i \leq N
- 頂点 A_i は頂点 B_i の先祖であるかまたは A_i=B_i
- 入力される値はすべて整数
入力
入力は標準入力から以下の形式で与えられる。
N M P_2 P_3 \cdots P_N A_1 A_2 \cdots A_M B_1 B_2 \cdots B_M
出力
答えを出力せよ．
入力例 1
3 3 1 2 1 2 1 1 2 3
出力例 1
2
i=1 を選ぶことを考えます．操作後の A=(2,1,1) は good でないので，この操作は実行不可能です．
i=2 を選ぶことを考えます．操作後の A=(1,1,2) は good なので，この操作は実行可能です．
A に 0 回以上操作を行った結果としてあり得る数列は A=(1,2,1),(1,1,2) の 2 つです．
入力例 2
4 3 1 1 1 2 3 4 2 3 4
出力例 2
1
入力例 3
8 13 1 2 2 3 4 4 3 5 3 2 5 4 6 2 8 2 6 7 4 7 5 5 8 5 6 6 5 8 3 6 7 4 7
出力例 3
8
入力例 4
30 27 1 2 1 1 5 1 7 1 5 10 1 12 12 13 15 16 12 18 19 18 21 21 23 13 18 18 27 27 13 1 18 1 5 11 12 1 1 1 12 1 12 1 15 1 1 21 1 12 10 2 8 3 1 1 30 12 14 27 30 5 11 17 1 18 24 27 29 27 19 15 28 5 21 21 29 11 2 8 3 4 10 30 22
出力例 4
60
Score : 900 points
Problem Statement
There is a rooted tree with N vertices numbered from 1 to N. The root is vertex 1, and the parent of vertex i (2 \leq i \leq N) is vertex P_i (P_i<i).
There are also integer sequences of length M: A=(A_1,A_2,\cdots,A_M) and B=(B_1,B_2,\cdots,B_M), consisting of integers between 1 and N, inclusive.
A is said to be good if and only if for each i, vertex A_i is an ancestor of vertex B_i or A_i=B_i. Initially, A is good.
Consider the following operation on A.
- Choose an integer i (1 \leq i \leq M-1) and swap the values of A_i and A_{i+1}. Here, A must remain good after the operation.
Find the number, modulo 998244353, of sequences that can result from performing this operation on A zero or more times.
Constraints
- 2 \leq N \leq 250000
- 2 \leq M \leq 250000
- 1 \leq P_i <i
- 1 \leq A_i \leq B_i \leq N
- Vertex A_i is an ancestor of vertex B_i or A_i=B_i.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M P_2 P_3 \cdots P_N A_1 A_2 \cdots A_M B_1 B_2 \cdots B_M
Output
Print the answer.
Sample Input 1
3 3 1 2 1 2 1 1 2 3
Sample Output 1
2
Consider choosing i=1. The A=(2,1,1) after the operation is not good, so this operation is invalid.
Consider choosing i=2. The A=(1,1,2) after the operation is good, so this operation is valid.
There are two sequences that can result from performing zero or more operations on A: A=(1,2,1) and (1,1,2).
Sample Input 2
4 3 1 1 1 2 3 4 2 3 4
Sample Output 2
1
Sample Input 3
8 13 1 2 2 3 4 4 3 5 3 2 5 4 6 2 8 2 6 7 4 7 5 5 8 5 6 6 5 8 3 6 7 4 7
Sample Output 3
8
Sample Input 4
30 27 1 2 1 1 5 1 7 1 5 10 1 12 12 13 15 16 12 18 19 18 21 21 23 13 18 18 27 27 13 1 18 1 5 11 12 1 1 1 12 1 12 1 15 1 1 21 1 12 10 2 8 3 1 1 30 12 14 27 30 5 11 17 1 18 24 27 29 27 19 15 28 5 21 21 29 11 2 8 3 4 10 30 22
Sample Output 4
60
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 1100 点
問題文
正整数 A,B,X,Y,N が与えられます． ここで，以下が保証されます．
- A<B
- \gcd(A,B)=1
- 1 \leq N \leq A+B-1
整数 n に対し，f(n) を以下のように定義します．
- 整数 x=0 を持った状態からスタートし，以下の操作を繰り返して x=n を達成するのにかかるコストの合計の最小値を f(n) とする．
- x の値を x+A で置き換える．コストが X かかる．
- x の値を x-A で置き換える．コストが X かかる．
- x の値を x+B で置き換える．コストが Y かかる．
- x の値を x-B で置き換える．コストが Y かかる．
なお，A,B の制約より，任意の整数 n に対して f(n) が定義できることが証明できます．
\sum_{1 \leq n \leq N} f(n) の値を 998244353 で割ったあまりを求めてください．
1 つの入力につきテストケースは T 個あります．
制約
- 1 \leq T \leq 1000
- 1 \leq A<B \leq 10^9
- \gcd(A,B)=1
- 1 \leq X,Y \leq 10^9
- 1 \leq N \leq A+B-1
- 入力される値はすべて整数
入力
入力は標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各テストケースは以下の形式で与えられる。
A B X Y N
出力
各テストケースに対して答えを出力せよ．
入力例 1
4 1 2 1 1 2 3 5 2 4 6 79 85 72 95 4 80980429 110892168 22712439 520643153 66132787
出力例 1
2 34 18111 785776602
1 つめのテストケースでは，f(1)=1,f(2)=1 です．
2 つめのテストケースでは，f(1)=8,f(2)=6,f(3)=2,f(4)=10,f(5)=4,f(6)=4 です．
Score : 1100 points
Problem Statement
You are given positive integers A, B, X, Y, and N. Here, the following is guaranteed:
- A<B
- \gcd(A,B)=1
- 1 \leq N \leq A+B-1
For an integer n, define f(n) as follows:
- You start with an integer x=0. f(n) is the minimum total cost to achieve x=n by repeatedly performing the following operations.
- Replace the value of x with x+A. The cost of this operation is X.
- Replace the value of x with x-A. The cost of this operation is X.
- Replace the value of x with x+B. The cost of this operation is Y.
- Replace the value of x with x-B. The cost of this operation is Y.
It can be proved from the constraints on A and B that f(n) is defined for any integer n.
Find the value of \sum_{1 \leq n \leq N} f(n), modulo 998244353.
There are T test cases for each input.
Constraints
- 1 \leq T \leq 1000
- 1 \leq A<B \leq 10^9
- \gcd(A,B)=1
- 1 \leq X,Y \leq 10^9
- 1 \leq N \leq A+B-1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each test case is given in the following format:
A B X Y N
Output
Print the answer for each test case.
Sample Input 1
4 1 2 1 1 2 3 5 2 4 6 79 85 72 95 4 80980429 110892168 22712439 520643153 66132787
Sample Output 1
2 34 18111 785776602
In the first test case, f(1)=1 and f(2)=1.
In the second test case, f(1)=8, f(2)=6, f(3)=2, f(4)=10, f(5)=4, and f(6)=4.