Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
1 から N までの番号がつけられた N 人の人がある地点間を往復するレースを行いました。このレースについて、以下の情報が残されています。
- 往路のタイムの早い順に順位をつけると、どの 2 人のタイムも異なっており、人 i\ (1 \leq i \leq N) は i 位であった。
- 往復のタイム(往路のタイムと復路のタイムの合計)の早い順に順位をつけると、どの 2 人のタイムも異なっており、人 i\ (1 \leq i \leq N) は P_i 位であった。
- 復路のタイムが最も早かった人(複数人いる場合はその全員)に復路の区間賞が与えられた。
ここで、P_1, P_2, \dots, P_N は 1, 2, \dots, N の並べ替えです。
このとき、復路の区間賞を与えられた可能性のある人は何人いるでしょうか?
T 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- 1 \leq T \leq 500
- 2 \leq N \leq 10^3
- P_1, P_2, \dots, P_N は 1, 2, \dots, N の並べ替えである
- 入力される数値は全て整数
- 1 つの入力に含まれるテストケースについて、N の総和は 10^3 以下
入力
入力は以下の形式で標準入力から与えられる。
T \mathrm{case}_1 \vdots \mathrm{case}_T
各テストケース \mathrm{case}_i\ (1 \leq i \leq T) は以下の形式で与えられる。
N P_1 P_2 \cdots P_N
出力
T 行出力せよ。i 行目 (1 \leq i \leq T) には、 i 番目のテストケースの答えを出力せよ。
入力例 1
3 2 2 1 4 1 2 3 4 20 13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17
出力例 1
1 4 7
- 1 つ目のテストケースでは、2 人でレースを行い、復路において人 2 が人 1 を抜かしています。この場合、復路の区間賞は人 2 に与えられます。
- 2 つ目のテストケースでは、復路で順位が変動しておらず、どの人も復路の区間賞が与えられた可能性があります。
Score : 300 points
Problem Statement
There are N people, numbered from 1 to N, who participated in a round-trip race between two points. The following information is recorded about this race.
- The outward times of any two people were different, and person i (1 \leq i \leq N) had the i-th fastest outward time.
- The round-trip times (the sum of the outward and return times) of any two people were different, and person i (1 \leq i \leq N) had the P_i-th fastest round-trip time.
- The person (or persons) with the fastest return time was awarded the fastest return award.
Here, P_1, P_2, \dots, P_N is a permutation of 1, 2, \dots, N.
How many people could have received the fastest return award?
There are T test cases. Answer each of them.
Constraints
- 1 \leq T \leq 500
- 2 \leq N \leq 10^3
- P_1, P_2, \dots, P_N is a permutation of 1, 2, \dots, N.
- All input values are integers.
- The sum of N over all test cases in a single input is at most 10^3.
Input
The input is given from Standard Input in the following format:
T \mathrm{case}_1 \vdots \mathrm{case}_T
Each test case, \mathrm{case}_i\ (1 \leq i \leq T), is given in the following format:
N P_1 P_2 \cdots P_N
Output
Print T lines. The i-th line (1 \leq i \leq T) should contain the answer for the i-th test case.
Sample Input 1
3 2 2 1 4 1 2 3 4 20 13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17
Sample Output 1
1 4 7
- In the first test case, two people participated in the race, and person 2 overtook person 1 on the return leg. In this case, the fastest return award is awarded to person 2.
- In the second test case, the rankings did not change on the return leg, so any person could have received the fastest return award.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます。
P に対し以下の操作を 2\times 10^3 回以下行うことで P を昇順に並び替えられるか判定し、可能な場合は実際に操作手順を一つ示してください。
- 1\leq i \leq N-1,0 \leq j \leq N-2 を満たす整数 i,j を選ぶ。Q = (Q_1, Q_2,\ldots,Q_{N-2}) を P から (P_i,P_{i+1}) を抜き出して得られる列としたとき、P を (Q_1,\ldots,Q_j, P_i, P_{i+1}, Q_{j+1},\ldots,Q_{N-2}) で置き換える。
制約
- 2 \leq N \leq 10^3
- P は (1,2,\ldots,N) の順列
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
2\times 10^3 回以下の操作で P を昇順に並び替えられない場合 No
を出力せよ。昇順に並び替えられる場合、操作回数を M\ (0 \leq M \leq 2\times 10^3) とし、k 回目 (1\leq k \leq M) の操作で選んだ i,j を i_k,j_k として以下の形式で出力せよ。
Yes M i_1 j_1 i_2 j_2 \vdots i_M j_M
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
5 1 4 2 3 5
出力例 1
Yes 1 3 1
i=3,j=1 として操作を行います。
Q=(P_1,P_2,P_5)=(1,4,5) になるので、P=(Q_1,P_3,P_4,Q_2,Q_3) = (1,2,3,4,5) となります。
よって 1 回の操作で P を昇順に並び替えられます。
入力例 2
2 2 1
出力例 2
No
2\times 10^3 回以下の操作では P を昇順に並び替えられないことが証明できます。
入力例 3
4 3 4 1 2
出力例 3
Yes 3 3 0 1 2 3 0
操作回数を最小化する必要はありません。
Score : 500 points
Problem Statement
A permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) is given.
Determine whether it is possible to rearrange P in ascending order by performing the following operation at most 2\times 10^3 times, and if possible, show one such sequence of operations.
- Choose integers i and j such that 1\leq i \leq N-1,0 \leq j \leq N-2. Let Q = (Q_1, Q_2,\ldots,Q_{N-2}) be the sequence obtained by removing (P_i,P_{i+1}) from P. Replace P with (Q_1,\ldots,Q_j, P_i, P_{i+1}, Q_{j+1},\ldots,Q_{N-2}).
Constraints
- 2 \leq N \leq 10^3
- P is a permutation of (1,2,\ldots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
If P cannot be rearranged in ascending order within 2\times 10^3 operations, print No
. If it can be rearranged in ascending order, let M\ (0 \leq M \leq 2\times 10^3) be the number of operations, and i_k,j_k be the chosen i,j for the k-th operation (1\leq k \leq M), and print them in the following format:
Yes M i_1 j_1 i_2 j_2 \vdots i_M j_M
If there are multiple solutions, any of them will be considered correct.
Sample Input 1
5 1 4 2 3 5
Sample Output 1
Yes 1 3 1
Perform the operation with i=3,j=1.
Then, Q=(P_1,P_2,P_5)=(1,4,5), so you get P=(Q_1,P_3,P_4,Q_2,Q_3) = (1,2,3,4,5).
Thus, P can be rearranged in ascending order with one operation.
Sample Input 2
2 2 1
Sample Output 2
No
It can be proved that P cannot be rearranged in ascending order within 2\times 10^3 operations.
Sample Input 3
4 3 4 1 2
Sample Output 3
Yes 3 3 0 1 2 3 0
There is no need to minimize the number of operations.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
頂点に 1 から N の番号がついた N 頂点の根付き木が与えられます。頂点 1 が根であり、頂点 i\ (2\leq i \leq N) の親は P_i です。
根付き木の何個かの頂点には 0 以上 N 以下の整数が書かれています。この情報は数列 A=(A_1,A_2,\ldots,A_N) で与えられ、A_i \neq -1 の場合頂点 i に整数 A_i が書かれており、A_i=-1 の場合頂点 i には整数が書かれていないことを意味しています。
Alice と Bob でゲームをします。Alice が先手で、全ての頂点に整数が書かれるまで以下の操作を交互に繰り返します。
- 整数が書かれていない頂点を 1 個選び、 0 以上 N 以下の整数を書く。
操作終了後の各頂点 v に対して、 f(v) を「頂点 v の部分木に含まれるどの頂点(v 含む)にも書かれていないような最小の非負整数」と定めます。
f(v) = K を満たす頂点 v が存在する場合 Alice の勝利、そうでない場合 Bob の勝利となります。両者が最適な行動を行う場合、どちらが勝つか判定してください。
T 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- 1 \leq T \leq 10^3
- 2 \leq N \leq 10^3
- 0 \leq K \leq N
- 1 \leq P_i < i\ (2\leq i\leq N)
- -1 \leq A_i \leq N\ (1\leq i\leq N)
- 入力される数値は全て整数
- 1 つの入力に含まれるテストケースについて、N の総和は 2\times 10^3 以下
入力
入力は以下の形式で標準入力から与えられる。
T \mathrm{case}_1 \vdots \mathrm{case}_T
各ケースは以下の形式で与えられる。
N K P_2 P_3 \ldots P_N A_1 A_2 \ldots A_N
出力
T 行出力せよ。i\ (1\leq i \leq T) 行目には、 i 番目のテストケースについて、両者が最適な行動を行う場合 Alice が勝つならば Alice
を、Bob が勝つならば Bob
を出力せよ。
入力例 1
2 4 2 1 1 2 -1 -1 3 1 6 4 1 2 2 1 3 -1 -1 -1 -1 -1 -1
出力例 1
Alice Bob
1 番目のテストケースについては、Alice が頂点 2 に 0 を書き込むと、Bob の操作に依らず f(2) = 2 となります。そのため、Alice は勝つことができます。
2 番目のテストケースについては、Bob が上手く書き込む整数を選ぶことで、 f(v) = 4 なる頂点が存在しないようにできます。
Score : 500 points
Problem Statement
You are given a rooted tree with N vertices numbered 1 to N. Vertex 1 is the root, and the parent of vertex i\ (2\leq i \leq N) is P_i.
Some vertices of the rooted tree have non-negative integers from 0 to N written on them. This information is given by the sequence A=(A_1,A_2,\ldots,A_N). If A_i \neq -1, vertex i has the integer A_i written on it; if A_i=-1, vertex i does not have an integer written on it.
Alice and Bob play a game. Alice goes first, and they take turns performing the following operation until all vertices have an integer written on them.
- Choose one vertex without an integer written on it and write a non-negative integer between 0 and N on it.
After the operations, for each vertex v, let f(v) be the smallest non-negative integer not written on any vertex (including v) in the subtree rooted at vertex v.
If there is a vertex v such that f(v) = K, Alice wins. Otherwise, Bob wins. Determine the winner when both players play optimally.
There are T test cases. Answer each of them.
Constraints
- 1 \leq T \leq 10^3
- 2 \leq N \leq 10^3
- 0 \leq K \leq N
- 1 \leq P_i < i\ (2\leq i\leq N)
- -1 \leq A_i \leq N\ (1\leq i\leq N)
- All input values are integers.
- The sum of N over all test cases in a single input is at most 2\times 10^3.
Input
The input is given from Standard Input in the following format:
T \mathrm{case}_1 \vdots \mathrm{case}_T
Each case is given in the following format:
N K P_2 P_3 \ldots P_N A_1 A_2 \ldots A_N
Output
Print T lines. The i-th (1\leq i \leq T) line should contain Alice
if Alice wins, and Bob
if Bob wins when both players play optimally in the i-th test case.
Sample Input 1
2 4 2 1 1 2 -1 -1 3 1 6 4 1 2 2 1 3 -1 -1 -1 -1 -1 -1
Sample Output 1
Alice Bob
In the first test case, if Alice writes 0 on vertex 2, then f(2) = 2 regardless of Bob's operation. Therefore, Alice can win.
In the second test case, Bob can ensure that there will be no vertex with f(v) = 4 by choosing the right integer to write.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
この問題では、根付き有向木と言った際には全ての辺が根から葉の方向に向き付けられた根付き木を指すものとします。
総和が N-1 であるような非負整数列 d=(d_1,d_2,\ldots,d_N) が与えられます。
頂点に 1 から N の番号がついた、頂点 1 を根とする N 頂点の根付き有向木のうち、以下の条件を満たすものを良い木と呼びます。
- 頂点 i\ (1\leq i \leq N) の出次数は d_i
さらに、良い木の頂点 v に対して、 f(v) を「頂点 v の部分木に含まれる頂点(v 含む)の頂点番号の最小値」と定め、f(v)=v を満たす頂点を良い頂点と呼びます。
良い木全てに対する良い頂点の個数の総和を 998244353 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 500
- 0 \leq d_i \leq N-1
- d_1 \geq 1
- \sum_{i=1}^N d_i = N-1
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N d_1 d_2 \ldots d_N
出力
答えを出力せよ。
入力例 1
4 2 0 1 0
出力例 1
7
良い木は以下の 2 通りあります。青く塗られた頂点は良い頂点です。
それぞれについて良い頂点は 4 個、 3 個なので答えは 7 です。
入力例 2
10 3 1 0 0 2 0 1 2 0 0
出力例 2
37542
Score : 700 points
Problem Statement
In this problem, a rooted directed tree is a rooted tree where all edges are directed from the root to the leaves.
You are given a sequence of non-negative integers d=(d_1,d_2,\ldots,d_N) with a sum of N-1.
Among the N-vertex rooted directed trees with vertex numbered 1 to N and vertex 1 as the root, a good tree is one that satisfies the following condition:
- the out-degree of vertex i\ (1\leq i \leq N) is d_i.
Furthermore, for a vertex v of a good tree, let f(v) be the minimum vertex number of the vertices (including v) in the subtree rooted at vertex v, and v is called a good vertex if it satisfies f(v)=v.
Find the sum of the numbers of good vertices for all good trees, modulo 998244353.
Constraints
- 2 \leq N \leq 500
- 0 \leq d_i \leq N-1
- d_1 \geq 1
- \sum_{i=1}^N d_i = N-1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N d_1 d_2 \ldots d_N
Output
Print the answer.
Sample Input 1
4 2 0 1 0
Sample Output 1
7
There are two good trees, as shown below. The blue vertices are good vertices.
For these trees, there are 4 and 3 good vertices, respectively, so the answer is 7.
Sample Input 2
10 3 1 0 0 2 0 1 2 0 0
Sample Output 2
37542
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
1 以上 N 以下の整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
1 以上 N 以下の整数からなる長さ N の数列 B=(B_1,B_2,\ldots,B_N) のうち、全ての i=1,2,\ldots,N に対して以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。
- B の中に含まれる i の個数は A_i 個以下
- B の中に含まれる B_i の個数は A_i 個以下
制約
- 1 \leq N \leq 500
- 1 \leq A_i \leq N
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 1 2 3
出力例 1
10
条件を満たす数列は以下の 10 個です。
- (1,2,2)
- (1,2,3)
- (1,3,2)
- (1,3,3)
- (2,1,3)
- (2,3,1)
- (2,3,3)
- (3,1,2)
- (3,2,1)
- (3,2,2)
入力例 2
4 4 4 4 4
出力例 2
256
条件を満たす数列は、1 以上 4 以下の整数からなる長さ 4 の数列全てで、その個数は 4^4=256 個です。
入力例 3
5 1 1 1 1 1
出力例 3
120
条件を満たす数列は、(1,2,3,4,5) を並び替えて得られる数列全てで、その個数は 5!=120 個です。
入力例 4
14 6 5 14 3 6 7 3 11 11 2 3 7 8 10
出力例 4
628377683
個数を 998244353 で割ったあまりを出力してください。
Score : 700 points
Problem Statement
You are given a sequence of length N consisting of integers from 1 to N, A=(A_1,A_2,\ldots,A_N).
Find the number, modulo 998244353, of sequences of length N consisting of integers from 1 to N, B=(B_1,B_2,\ldots,B_N), that satisfy the following conditions for all i=1,2,\ldots,N.
- The number of occurrences of i in B is at most A_i.
- The number of occurrences of B_i in B is at most A_i.
Constraints
- 1 \leq N \leq 500
- 1 \leq A_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
3 1 2 3
Sample Output 1
10
The following 10 sequences satisfy the conditions:
- (1,2,2)
- (1,2,3)
- (1,3,2)
- (1,3,3)
- (2,1,3)
- (2,3,1)
- (2,3,3)
- (3,1,2)
- (3,2,1)
- (3,2,2)
Sample Input 2
4 4 4 4 4
Sample Output 2
256
All sequences of length 4 consisting of integers from 1 to 4 satisfy the conditions, and there are 4^4=256 such sequences.
Sample Input 3
5 1 1 1 1 1
Sample Output 3
120
All permutations of (1,2,3,4,5) satisfy the conditions, and there are 5!=120 such sequences.
Sample Input 4
14 6 5 14 3 6 7 3 11 11 2 3 7 8 10
Sample Output 4
628377683
Be sure to print the number modulo 998244353.
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
正整数 N, M が与えられます。各要素が 0 または 1 である N 行 M 列の行列 A は全部で 2^{NM} 個存在しますが、そのうち以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。
- 1 \leq a < c \leq N かつ 1 \leq b < d \leq M を満たす全ての整数の組 (a, b, c, d) について、A_{a, b} \times A_{c, d} \leq A_{a, d} \times A_{c, b} が成り立つ。
制約
- 1 \leq N, M \leq 400
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを 1 行に出力せよ。
入力例 1
2 2
出力例 1
13
条件は A_{1,1} \times A_{2,2} \leq A_{1,2} \times A_{2,1} です。\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} 以外の 13 個が条件を満たします。
入力例 2
1 30
出力例 2
75497471
2^{NM} 個すべての行列が条件を満たすので、2^{30} を 998244353 で割ったあまりである 75497471 を出力します。
入力例 3
400 400
出力例 3
412670892
Score : 900 points
Problem Statement
You are given positive integers N and M. Among the 2^{NM} matrices A with N rows and M columns where each element is 0 or 1, find the number, modulo 998244353, of ones that satisfy the following condition:
- A_{a, b} \times A_{c, d} \leq A_{a, d} \times A_{c, b} for every quadruple of integers (a, b, c, d) such that 1 \leq a < c \leq N and 1 \leq b < d \leq M.
Constraints
- 1 \leq N, M \leq 400
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer in a single line.
Sample Input 1
2 2
Sample Output 1
13
The condition is A_{1,1} \times A_{2,2} \leq A_{1,2} \times A_{2,1}. All 13 matrices other than \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} satisfy the condition.
Sample Input 2
1 30
Sample Output 2
75497471
All 2^{NM} matrices satisfy the condition, so print 2^{30} modulo 998244353, that is, 75497471.
Sample Input 3
400 400
Sample Output 3
412670892