実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人がいます。N 人の人には人 1, 人 2,\dots, 人 N と番号がついています。
人 i(2 \le i \le N) の親は人 P_i です。ここで、P_i < i が保証されます。
人 1 が人 N の何代前か求めてください。
制約
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N P_2 P_3 \dots P_N
出力
答えを整数として出力せよ。
入力例 1
3 1 2
出力例 1
2
人 2 は人 3 の親であるため、人 3 の 1 代前です。
人 1 は人 2 の親であるため、人 3 の 2 代前です。
よって解は 2 です。
入力例 2
10 1 2 3 4 5 6 7 8 9
出力例 2
9
Score : 200 points
Problem Statement
There are N people, called Person 1, Person 2, \ldots, Person N.
The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.
How many generations away from Person N is Person 1?
Constraints
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_2 P_3 \dots P_N
Output
Print the answer as a positive integer.
Sample Input 1
3 1 2
Sample Output 1
2
Person 2 is a parent of Person 3, and thus is one generation away from Person 3.
Person 1 is a parent of Person 2, and thus is two generations away from Person 3.
Therefore, the answer is 2.
Sample Input 2
10 1 2 3 4 5 6 7 8 9
Sample Output 2
9
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
各要素が 0 あるいは 1 である N 行 N 列の行列 A, B が与えられます。
A の i 行目 j 列目の要素を A_{i,j}、B の i 行目 j 列目の要素を B_{i,j} で表します。
A を適切に回転することで、 A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできるか判定してください。
ただし、A を回転するとは、以下の操作を好きな回数（0 回でもよい）繰り返すことをいいます。
- 1 \leq i, j \leq N を満たすすべての整数の組 (i, j) について同時に A_{i,j} を A_{N + 1 - j,i} で置き換える
制約
- 1 \leq N \leq 100
- A, B の各要素は 0 か 1 のいずれか
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
出力
A を適切に回転することで、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできる場合 Yes を、そうでない場合 No を出力せよ。
入力例 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
出力例 1
Yes
はじめ、A は
0 1 1 1 0 0 0 1 0
です。
1 回操作を行うと、A は
0 1 0 1 0 1 0 0 1
となります。
もう 1 度操作を行うと、A は
0 1 0 0 0 1 1 1 0
となります。
このとき、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているので、Yes を出力します。
入力例 2
2 0 0 0 0 1 1 1 1
出力例 2
Yes
入力例 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
出力例 3
No
Score : 200 points
Problem Statement
You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:
- for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.
Constraints
- 1 \leq N \leq 100
- Each element of A and B is 0 or 1.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
Output
If it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, print Yes; otherwise, print No.
Sample Input 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
Sample Output 1
Yes
Initially, A is :
0 1 1 1 0 0 0 1 0
After performing the operation once, A is :
0 1 0 1 0 1 0 0 1
After performing the operation once again, A is :
0 1 0 0 0 1 1 1 0
Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.
Sample Input 2
2 0 0 0 0 1 1 1 1
Sample Output 2
Yes
Sample Input 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
Sample Output 3
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
長さ M の A の連続部分列 B=(B_1,B_2,\dots,B_M) に対する、\displaystyle \sum_{i=1}^{M} i \times B_i の最大値を求めてください。
注記
数列の連続部分列とは、数列の先頭から 0 個以上、末尾から 0 個以上の要素を削除して得られる列のことをいいます。
例えば (2, 3) や (1, 2, 3) は (1, 2, 3, 4) の連続部分列ですが、(1, 3) や (3,2,1) は (1, 2, 3, 4) の連続部分列ではありません。
制約
- 1 \le M \le N \le 2 \times 10^5
- - 2 \times 10^5 \le A_i \le 2 \times 10^5
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 2 5 4 -1 8
出力例 1
15
B=(A_3,A_4) とした場合、\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15 となります。16 以上の値を達成することはできないため、解は 15 です。
B=(A_1,A_4) などを選ぶことができないことに注意してください。
入力例 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
出力例 2
31
Score : 300 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.
Notes
A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.
For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).
Constraints
- 1 \le M \le N \le 2 \times 10^5
- - 2 \times 10^5 \le A_i \le 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 2 5 4 -1 8
Sample Output 1
15
When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.
Note that you are not allowed to choose, for instance, B=(A_1,A_4).
Sample Input 2
10 4 -3 1 -4 1 -5 9 -2 6 -5 3
Sample Output 2
31
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
列 S_n を次のように定義します。
- S_1 は 1 つの 1 からなる長さ 1 の列である。
- S_n (n は 2 以上の整数) は S_{n-1}, n, S_{n-1} をこの順につなげた列である。
たとえば S_2,S_3 は次のような列です。
- S_2 は S_1, 2, S_1 をこの順につなげた列なので 1,2,1 である。
- S_3 は S_2, 3, S_2 をこの順につなげた列なので 1,2,1,3,1,2,1 である。
N が与えられるので、列 S_N をすべて出力してください。
制約
- N は整数
- 1 \leq N \leq 16
入力
入力は以下の形式で標準入力から与えられる。
N
出力
S_N を空白区切りで出力せよ。
入力例 1
2
出力例 1
1 2 1
問題文の説明にある通り、S_2 は 1,2,1 となります。
入力例 2
1
出力例 2
1
入力例 3
4
出力例 3
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
S_4 は S_3,4,S_3 をこの順につなげた列です。
Score : 300 points
Problem Statement
We define sequences S_n as follows.
- S_1 is a sequence of length 1 containing a single 1.
- S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.
For example, S_2 and S_3 is defined as follows.
- S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
- S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.
Given N, print the entire sequence S_N.
Constraints
- N is an integer.
- 1 \leq N \leq 16
Input
Input is given from Standard Input in the following format:
N
Output
Print S_N, with spaces in between.
Sample Input 1
2
Sample Output 1
1 2 1
As described in the Problem Statement, S_2 is 1,2,1.
Sample Input 2
1
Sample Output 2
1
Sample Input 3
4
Sample Output 3
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
- S_4 is a concatenation of S_3, 4, and S_3, in this order.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
鳩 1, 鳩 2,\ldots, 鳩 N の N 羽の鳩と、巣 1, 巣 2,\ldots, 巣 N の N 個の巣があります。
はじめ、鳩 i (1\leq i\leq N) は巣 i にいます。
鳩たちに対して Q 回の操作を行います。
操作は次の 3 種類のうちのいずれかです。
- 種類 1 : 整数 a,b (1\leq a\leq N,1\leq b\leq N) が与えられる。鳩 a を今いる巣から取り出し、巣 b へ移動する。
- 種類 2 : 整数 a,b (1\leq a\lt b\leq N) が与えられる。巣 a にいる鳩をすべて巣 b へ移動し、巣 b にいる鳩をすべて巣 a へ移動する。これら 2 つの移動は一斉に行われる。
- 種類 3 : 整数 a (1\leq a\leq N) が与えられる。鳩 a が今いる巣の番号を報告する。
Q 回の操作を順に行ったときの、種類 3 の各操作における報告の結果を出力してください。
制約
- 1\leq N\leq10 ^ 6
- 1\leq Q\leq3\times10 ^ 5
- 入力される操作はすべて種類 1, 種類 2, 種類 3 のいずれかである。
- 入力される操作は問題文中の制約を満たす。
- 入力される操作のうちに種類 3 の操作が 1 つ以上含まれる。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q op _ 1 op _ 2 \vdots op _ Q
ただし、i+1 行目の入力 op _ i は i 番目の操作を表しており、op _ i は次のいずれかの形式である。
i 番目の操作が種類 1 の操作のとき、i+1 行目は次の形式で与えられる。
1 a b
これは、与えられる整数を a と b として種類 1 の操作を行うことを表している。
i 番目の操作が種類 2 の操作のとき、i+1 行目は次の形式で与えられる。
2 a b
これは、与えられる整数を a と b として種類 2 の操作を行うことを表している。
i 番目の操作が種類 3 の操作のとき、i+1 行目は次の形式で与えられる。
3 a
これは、与えられる整数を a として種類 3 の操作を行うことを表している。
出力
与えられる種類 3 の操作の個数を q 個として、q 行にわたって出力せよ。
i 行目 (1\leq i\leq q) には、種類 3 の操作のうち i 番目の操作で報告される巣の番号を出力せよ。
入力例 1
6 8 1 2 4 1 3 6 3 2 2 4 5 3 2 1 4 2 3 4 3 2
出力例 1
4 5 2 5
与えられる操作で、鳩は以下の図のように移動します。
種類 3 の操作でそれぞれ報告すべき巣の番号は 4,5,2,5 なので、4 5 2 5 を 4 行にわたって出力してください。
入力例 2
1 2 1 1 1 3 1
出力例 2
1
種類 1 の操作で、鳩を取り出した巣にそのまま戻す場合もあります。
入力例 3
30 15 3 3 2 8 30 2 12 15 2 2 17 1 19 1 2 7 30 3 12 3 8 2 25 26 1 13 10 1 16 10 2 16 29 2 1 21 2 6 11 1 21 8
出力例 3
3 15 7
Score : 350 points
Problem Statement
There are N pigeons labeled 1, 2, \ldots, N and N nests labeled 1, 2, \ldots, N.
Initially, pigeon i (1 \leq i \leq N) is in nest i.
You will perform Q operations on these pigeons.
There are three types of operations:
- Type 1: You are given integers a and b (1 \leq a \leq N, 1 \leq b \leq N). Take pigeon a out of its current nest and move it to nest b.
- Type 2: You are given integers a and b (1 \leq a < b \leq N). Move all pigeons in nest a to nest b, and move all pigeons in nest b to nest a. These two moves happen simultaneously.
- Type 3: You are given an integer a (1 \leq a \leq N). Pigeon a reports the label of the nest it is currently in.
Print the result of each Type 3 operation in the order the operations are given.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq Q \leq 3 \times 10^5
- Every operation is of Type 1, 2, or 3.
- All operations are valid according to the problem statement.
- There is at least one Type 3 operation.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q op _ 1 op _ 2 \vdots op _ Q
Here, op _ i on the line i+1 represents the i-th operation in one of the following formats.
If the i-th operation is of Type 1, op _ i is in the following format:
1 a b
This corresponds to a Type 1 operation with the given integers being a and b.
If the i-th operation is of Type 2, op _ i is in the following format:
2 a b
This corresponds to a Type 2 operation with the given integers being a and b.
If the i-th operation is of Type 3, op _ i is in the following format:
3 a
This corresponds to a Type 3 operation with the given integer being a.
Output
Let the number of Type 3 operations be q. Print q lines. The i-th line (1 \leq i \leq q) should contain the nest number reported in the i-th Type 3 operation.
Sample Input 1
6 8 1 2 4 1 3 6 3 2 2 4 5 3 2 1 4 2 3 4 3 2
Sample Output 1
4 5 2 5
In the operations given, the pigeons move as shown in the figure below:
The nest numbers to be reported for the Type 3 operations are 4,5,2,5. Print 4, 5, 2, 5 on separate lines.
Sample Input 2
1 2 1 1 1 3 1
Sample Output 2
1
The destination nest of a Type 1 operation may be the same as the nest the pigeon is currently in.
Sample Input 3
30 15 3 3 2 8 30 2 12 15 2 2 17 1 19 1 2 7 30 3 12 3 8 2 25 26 1 13 10 1 16 10 2 16 29 2 1 21 2 6 11 1 21 8
Sample Output 3
3 15 7