Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
(1,2,\cdots,2N) の順列 P=(P_1,P_2,\cdots,P_{2N}) が与えられます.
あなたは,以下の操作を 0 回以上 N 回以下行うことができます.
- 整数 x (1 \leq x \leq 2N-1) を選ぶ. P_x と P_{x+1} の値を入れ替える.
操作後の P が以下の条件を満たすような操作列を 1 つ示してください.
- 各 i=1,3,5,\cdots,2N-1 について,P_i<P_{i+1} である.
- 各 i=2,4,6,\cdots,2N-2 について,P_i>P_{i+1} である.
なお,条件を満たすような操作列が必ず存在することが証明できます.
制約
- 1 \leq N \leq 10^5
- (P_1,P_2,\cdots,P_{2N}) は (1,2,\cdots,{2N}) の順列
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N P_1 P_2 \cdots P_{2N}
出力
以下の形式で操作列を出力せよ.
K x_1 x_2 \cdots x_K
ここで,K は行う操作の回数 (0 \leq K \leq N) であり,x_i (1 \leq x_i \leq 2N-1) は i 回目の操作で選ぶ x の値である. 条件を満たす解が複数存在する場合,どれを出力しても正解とみなされる.
入力例 1
2 4 3 2 1
出力例 1
2 1 3
操作後は P=(3,4,1,2) となり,条件を満たします.
入力例 2
1 1 2
出力例 2
0
Score : 400 points
Problem Statement
You are given a permutation P=(P_1,P_2,\cdots,P_{2N}) of (1,2,\cdots,2N).
The following operation may be performed between 0 and N times (inclusive).
- Choose an integer x (1 \leq x \leq 2N-1). Swap the values of P_x and P_{x+1}.
Present a sequence of operations that make P satisfy the following conditions.
- P_i<P_{i+1} for each i=1,3,5,\cdots,2N-1;
- P_i>P_{i+1} for each i=2,4,6,\cdots,2N-2.
It can be proved that such a sequence of operations always exists.
Constraints
- 1 \leq N \leq 10^5
- (P_1,P_2,\cdots,P_{2N}) is a permutation of (1,2,\cdots,{2N}).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \cdots P_{2N}
Output
Print a desired sequence of operations in the following format:
K x_1 x_2 \cdots x_K
Here, K is the number of operations performed (0 \leq K \leq N), and x_i is the value of x chosen in the i-th operation (1 \leq x_i \leq 2N-1). If there are multiple solutions satisfying the condition, printing any of them will be accepted.
Sample Input 1
2 4 3 2 1
Sample Output 1
2 1 3
These operations make P=(3,4,1,2), which satisfies the conditions.
Sample Input 2
1 1 2
Sample Output 2
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます.
あなたは,以下の操作を 0 回以上行うことができます.
- 整数 i (1 \leq i \leq N-1) を選ぶ. v=\max(P_i,P_{i+1}) として,P_i と P_{i+1} の値を v で置き換える.
操作後の P としてあり得る数列が何通りあるかを 998244353 で割った余りを求めてください.
制約
- 2 \leq N \leq 5000
- (P_1,P_2,\cdots,P_N) は (1,2,\cdots,N) の順列
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N P_1 P_2 \cdots P_N
出力
答えを出力せよ.
入力例 1
3 1 3 2
出力例 1
4
操作後の P としてありうる数列は (1,3,2),(3,3,2),(1,3,3),(3,3,3) の 4 通りです.
入力例 2
4 2 1 3 4
出力例 2
11
入力例 3
10 4 9 6 3 8 10 1 2 7 5
出力例 3
855
Score : 700 points
Problem Statement
You are given a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).
You may perform the following operation zero or more times.
- Choose an integer i (1 \leq i \leq N-1). Let v=\max(P_i,P_{i+1}) and replace the values of P_i and P_{i+1} with v.
How many sequences are there that P can be after your operations? Find the count modulo 998244353.
Constraints
- 2 \leq N \leq 5000
- (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \cdots P_N
Output
Print the answer.
Sample Input 1
3 1 3 2
Sample Output 1
4
The four sequences that P can become are (1,3,2), (3,3,2), (1,3,3), and (3,3,3).
Sample Input 2
4 2 1 3 4
Sample Output 2
11
Sample Input 3
10 4 9 6 3 8 10 1 2 7 5
Sample Output 3
855
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
ある円環上に N 個の頂点が並んでいます. 頂点には時計回りに 1 から N の番号がついており,頂点 i には整数 A_i が書かれています. ここで,A_i は 1,2,3,4 のいずれかです. また A は 1,2,3,4 をそれぞれ 1 つ以上含みます.
これらの N 個の頂点を結ぶ辺を N-1 本追加し,木を作ることを考えます. ただしこの時,以下の条件を満たす必要があります.
-
頂点 x,y が直接辺で結ばれているならば,|A_x-A_y|=1 である.
-
追加した辺を線分として描いた時,どの 2 つも端点以外で交わらない.
例えば,以下の図は条件を満たす木の例です.
条件を満たすような木を作ることが可能かどうか判定してください.
1 つの入力ファイルにつき,T 個のテストケースを解いてください.
制約
- 1 \leq T \leq 75000
- 4 \leq N \leq 300000
- 1 \leq A_i \leq 4
- A は 1,2,3,4 をそれぞれ 1 つ以上含む
- 1 つの入力ファイルにつき,N の総和は 300000 を超えない
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
T case_1 case_2 \vdots case_T
各ケースは以下の形式で与えられる.
N A_1 A_2 \cdots A_N
出力
各ケースに対し,条件を満たす木を作ることができるならば Yes
を,できないならば No
を出力せよ.
入力例 1
3 4 1 2 3 4 4 1 3 4 2 4 1 4 2 3
出力例 1
Yes Yes No
入力例 2
3 8 4 2 3 4 1 2 2 1 8 3 2 2 3 1 3 3 4 8 2 3 3 2 1 4 1 4
出力例 2
Yes Yes No
最初のテストケースは,問題文中の図に対応しています.
Score : 900 points
Problem Statement
There are N vertices on a circumference. The vertices are numbered 1 to N in clockwise order, and Vertex i has an integer A_i written on it, where A_i is 1, 2, 3, or 4. Here, A contains each of 1, 2, 3, and 4 at least once.
Consider making a tree by adding N-1 edges connecting these N vertices. Here, the following conditions must be satisfied.
-
If Vertices x and y are directly connected by an edge, |A_x-A_y|=1.
-
When the edges are drawn as segments, no two of them intersect except at an endpoint.
For instance, the figure below shows a tree that satisfies the conditions:
Determine whether it is possible to construct a tree that satisfies the conditions.
Solve T test cases for each input file.
Constraints
- 1 \leq T \leq 75000
- 4 \leq N \leq 300000
- 1 \leq A_i \leq 4
- A contains each of 1, 2, 3, and 4 at least once.
- The sum of N in one input file does not exceed 300000.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N A_1 A_2 \cdots A_N
Output
For each case, print Yes
if it is possible to construct a tree that satisfies the conditions, and No
otherwise.
Sample Input 1
3 4 1 2 3 4 4 1 3 4 2 4 1 4 2 3
Sample Output 1
Yes Yes No
Sample Input 2
3 8 4 2 3 4 1 2 2 1 8 3 2 2 3 1 3 3 4 8 2 3 3 2 1 4 1 4
Sample Output 2
Yes Yes No
The first test case corresponds to the figure in the Problem Statement.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
整数 A,B,C が与えられます.
A
, B
, C
からなる文字列 S であって,以下の条件をすべて満たすものの個数を 998244353 で割った余りを求めてください.
- S に含まれる
A
,B
,C
の個数はそれぞれ A,B,C 個である. - S は(連続する)部分文字列として,
ABC
,BCA
,CAB
のいずれも含まない.
制約
- 1 \leq A,B,C \leq 10^6
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
A B C
出力
答えを出力せよ.
入力例 1
1 1 1
出力例 1
3
条件を満たす文字列は,ACB
, CBA
, BAC
の 3 つです.
入力例 2
2 2 2
出力例 2
42
入力例 3
96 11 46
出力例 3
818015722
入力例 4
125132 102271 152064
出力例 4
128086069
Score : 1000 points
Problem Statement
You are given integers A, B, and C.
How many strings S consisting of A
, B
, and C
satisfy all of the following conditions? Find the count modulo 998244353.
- The number of occurrences of
A
,B
, andC
in S are A, B, and C, respectively. - S contains none of
ABC
,BCA
, andCAB
as a (contiguous) substring.
Constraints
- 1 \leq A,B,C \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C
Output
Print the answer.
Sample Input 1
1 1 1
Sample Output 1
3
The three strings that satisfy the conditions are ACB
, CBA
, and BAC
.
Sample Input 2
2 2 2
Sample Output 2
42
Sample Input 3
96 11 46
Sample Output 3
818015722
Sample Input 4
125132 102271 152064
Sample Output 4
128086069
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1400 点
問題文
この問題では,順列と言った際には,(1,2,\cdots,N) の順列を指すものとします.
2 つの順列 p,q に対し,それらの距離 d(p,q) を次のように定義します.
- p の中で隣接 2 項を swap することを繰り返し,p を q に一致させることを考える.この時必要な最小の操作回数を d(p,q) とする.
さらに,順列 x に対し,順列 f(x) を次のように定義します.
- y=(1,2,\cdots,N) とする.ここで,順列 z であって,d(x,z) \leq d(y,z) を満たすものを考える. これらの中で辞書順最小のものを f(x) とする.
例えば,x=(2,3,1) の場合,d(x,z) \leq d(y,z) を満たす順列としては,z=(2,1,3),(2,3,1),(3,1,2),(3,2,1) が考えられます. このうち辞書順最小なのは (2,1,3) なので, f(x)=(2,1,3) となります.
順列 A=(A_1,A_2,\cdots,A_N) が与えられます. f(x)=A を満たす順列 x が存在するかどうか判定してください.
1 つの入力ファイルにつき,T 個のテストケースを解いてください.
数列の辞書順とは?
相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します。
以下では S の i 番目の要素を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j が T_j より(数として)小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- 1 \leq T \leq 150000
- 2 \leq N \leq 300000
- (A_1,A_2,\cdots,A_N) は (1,2,\cdots,N) の順列
- 1 つの入力ファイルにつき,N の総和は 300000 を超えない
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
T case_1 case_2 \vdots case_T
各ケースは以下の形式で与えられる.
N A_1 A_2 \cdots A_N
出力
各ケースに対し,f(x)=A を満たす順列 x が存在するならば Yes
を,存在しないならば No
を出力せよ.
入力例 1
2 2 1 2 2 2 1
出力例 1
Yes Yes
例えば A=(2,1) の場合は,x=(2,1) とすると f(x)=A となります.
入力例 2
6 3 1 2 3 3 1 3 2 3 2 1 3 3 2 3 1 3 3 1 2 3 3 2 1
出力例 2
Yes Yes Yes Yes No No
例えば A=(2,3,1) の場合は,x=(3,2,1) とすると,f(x)=A となります.
入力例 3
24 4 1 2 3 4 4 1 2 4 3 4 1 3 2 4 4 1 3 4 2 4 1 4 2 3 4 1 4 3 2 4 2 1 3 4 4 2 1 4 3 4 2 3 1 4 4 2 3 4 1 4 2 4 1 3 4 2 4 3 1 4 3 1 2 4 4 3 1 4 2 4 3 2 1 4 4 3 2 4 1 4 3 4 1 2 4 3 4 2 1 4 4 1 2 3 4 4 1 3 2 4 4 2 1 3 4 4 2 3 1 4 4 3 1 2 4 4 3 2 1
出力例 3
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No No No No No No No No No No No No No
Score : 1400 points
Problem Statement
In this problem, a "permutation" always means a permutation of (1,2,\cdots,N).
For two permutations p and q, let us define the distance between them, d(p,q), as follows.
- Consider making p equal q by repeatedly swapping two adjacent terms in p. Let d(p,q) be the minimum number of swaps required here.
Additionally, for a permutation x, let us define another permutation f(x) as follows.
- Let y=(1,2,\cdots,N). Consider permutations z such that d(x,z) \leq d(y,z). Let f(x) be the lexicographically smallest of those permutations.
For example, when x=(2,3,1), the permutations z such that d(x,z) \leq d(y,z) are z=(2,1,3),(2,3,1),(3,1,2),(3,2,1). The lexicographically smallest of them is (2,1,3), so we have f(x)=(2,1,3).
You are given a permutation A=(A_1,A_2,\cdots,A_N). Determine whether there is a permutation x such that f(x)=A.
Solve T test cases for each input file.
What is lexicographical order on sequences?
The algorithm described here determines the lexicographical order between distinct sequences S and T.
Below, let S_i denote the i-th element of S. Additionally, let S \lt T and S \gt T mean "S is lexicographical smaller than T" and "S is lexicographical larger than T," respectively.
- Let L be the length of the shorter of S and T. For each i=1,2,\dots,L, let us check whether S_i and T_i are equal.
- If there is i such that S_i \neq T_i, let j be the smallest such i, and compare S_j and T_j. If S_j is smaller than T_j (as a number), we conclude S \lt T and exit; if S_j is larger than T_j, we conclude S \gt T and exit.
- If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we conclude S \lt T and exit; if S is longer than T, we conclude S \gt T and exit.
Constraints
- 1 \leq T \leq 150000
- 2 \leq N \leq 300000
- (A_1,A_2,\cdots,A_N) is a permutation of (1,2,\cdots,N).
- The sum of N in one input file does not exceed 300000.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N A_1 A_2 \cdots A_N
Output
For each case, print Yes
if there is a permutation x such that f(x)=A, and No
otherwise.
Sample Input 1
2 2 1 2 2 2 1
Sample Output 1
Yes Yes
For instance, when A=(2,1), one can let x=(2,1) to satisfy f(x)=A.
Sample Input 2
6 3 1 2 3 3 1 3 2 3 2 1 3 3 2 3 1 3 3 1 2 3 3 2 1
Sample Output 2
Yes Yes Yes Yes No No
For instance, when A=(2,3,1), one can let x=(3,2,1) to satisfy f(x)=A.
Sample Input 3
24 4 1 2 3 4 4 1 2 4 3 4 1 3 2 4 4 1 3 4 2 4 1 4 2 3 4 1 4 3 2 4 2 1 3 4 4 2 1 4 3 4 2 3 1 4 4 2 3 4 1 4 2 4 1 3 4 2 4 3 1 4 3 1 2 4 4 3 1 4 2 4 3 2 1 4 4 3 2 4 1 4 3 4 1 2 4 3 4 2 1 4 4 1 2 3 4 4 1 3 2 4 4 2 1 3 4 4 2 3 1 4 4 3 1 2 4 4 3 2 1
Sample Output 3
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No No No No No No No No No No No No No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 2000 点
問題文
無向木 t に対して,有理数 f(t) を次のように定義します.
- t の頂点数を n とする.
- n=1 のとき:f(t)=1 とする.
- n \geq 2 のとき:
- t の辺 e について,t から e を削除することで得られる 2 つの木を t_x(e),t_y(e) (順不同)で表す.
- f(t)=(\sum_{e \in t} f(t_x(e)) \times f(t_y(e)))/n とする.
1 から N までの番号のついた N 頂点からなる木 T が与えられます. i 番目の辺は頂点 A_i と頂点 B_i を結ぶ辺です.
f(T) の値を \text{mod }{998244353} で求めてください.
有理数 \text{mod }{998244353} の定義
この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 2 \leq N \leq 5000
- 1 \leq A_i,B_i \leq N
- 入力されるグラフは木である
入力
入力は以下の形式で標準入力から与えられる.
N A_1 B_1 A_2 B_2 \vdots A_{N-1} B_{N-1}
出力
答えを出力せよ.
入力例 1
2 1 2
出力例 1
499122177
f(T)=1/2 です.
入力例 2
3 1 2 2 3
出力例 2
332748118
f(T)=1/3 です.
入力例 3
4 1 2 2 3 3 4
出力例 3
103983787
入力例 4
10 4 5 1 9 6 1 8 4 5 9 4 7 3 10 5 2 4 3
出力例 4
462781191
Score : 2000 points
Problem Statement
For an undirected tree t, let us define a rational number f(t) as follows.
- Let n be the number of vertices in t.
- If n=1: Let f(t)=1.
- If n \geq 2:
- For an edge e in t, we denote by t_x(e) and t_y(e) the two trees that result from deleting e from t (in arbitrary order).
- Let f(t)=(\sum_{e \in t} f(t_x(e)) \times f(t_y(e)))/n.
You are given a tree T with N vertices numbered 1 to N. The i-th edge connects Vertex A_i and Vertex B_i.
Find the value f(T) \text{mod }{998244353}.
What is a rational number \text{mod }{998244353}?
Under the Constraints of this problem, when the sought rational number is represented as \frac{P}{Q}, it can be proved that Q \neq 0 \pmod{998244353}. Therefore, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.
Constraints
- 2 \leq N \leq 5000
- 1 \leq A_i,B_i \leq N
- The given graph is a tree.
Input
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 the answer.
Sample Input 1
2 1 2
Sample Output 1
499122177
We have f(T)=1/2.
Sample Input 2
3 1 2 2 3
Sample Output 2
332748118
We have f(T)=1/3.
Sample Input 3
4 1 2 2 3 3 4
Sample Output 3
103983787
Sample Input 4
10 4 5 1 9 6 1 8 4 5 9 4 7 3 10 5 2 4 3
Sample Output 4
462781191