A - 2nd Greatest Distance

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

2 次元平面上に 1 から N の番号がついた N 軒の家があります。 家 i(x_i,y_i) にあります。

### 制約

• 与えられる入力は全て整数
• 3 \leq N \leq 2 \times 10^{5}
• -10^{9} \leq x_i, y_i \leq 10^{9}

### 入力

N
x_{1} y_{1}
\vdots
x_{N} y_{N}


### 入力例 1

3
0 0
1 2
4 0


### 出力例 1

3

• 1,2 間の距離は 2 です。
• 1,3 間の距離は 4 です。
• 2,3 間の距離は 3 です。
• これらを降順に並べて作られる数列は (4,3,2) です。先頭から 2 番目に現れる数は 3 です。

### 入力例 2

4
0 0
0 0
1 0
0 1


### 出力例 2

1

• 家は同じ座標に存在することもあります。

### 入力例 3

20
407 361
167 433
756 388
-551 -47
306 -471
36 928
338 -355
911 852
288 70
-961 -769
-668 -386
-690 -378
182 -609
-677 401
-458 -112
184 -131
-243 888
-163 471
-11 997
119 544


### 出力例 3

1766


Score : 400 points

### Problem Statement

There are N houses numbered 1 through N on a two-dimensional plane. House i is at (x_i, y_i).

We use Chebyshev distance to calculate the distance between two houses. That is, the distance between Houses i and j is \max(|x_i - x_j|, |y_i-y_j|).

There are \frac{N(N-1)}{2} pairs formed by two different houses. For each of these pairs, we will calculate the distance between the houses, and then we will sort these distances in descending order to get a sequence of length \frac{N(N-1)}{2}. Find the second value from the beginning of this sequence.

### Constraints

• All values in input are integers.
• 3 \leq N \leq 2 \times 10^{5}
• -10^{9} \leq x_i, y_i \leq 10^{9}

### Input

Input is given from Standard Input in the following format:

N
x_{1} y_{1}
\vdots
x_{N} y_{N}


### Output

Print the second value from the beginning of the sequence of distances of different houses sorted in descending order.

### Sample Input 1

3
0 0
1 2
4 0


### Sample Output 1

3

• The distance between Houses 1 and 2 is 2;
• The distance between Houses 1 and 3 is 4;
• The distance between Houses 2 and 3 is 3.
• By sorting these in descending order, we get (4,3,2), where the second value from the beginning is 3.

### Sample Input 2

4
0 0
0 0
1 0
0 1


### Sample Output 2

1

• There may be multiple houses at the same coordinates.

### Sample Input 3

20
407 361
167 433
756 388
-551 -47
306 -471
36 928
338 -355
911 852
288 70
-961 -769
-668 -386
-690 -378
182 -609
-677 401
-458 -112
184 -131
-243 888
-163 471
-11 997
119 544


### Sample Output 3

1766

B - RGB Matching

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけ君は 1 から 2N の番号がついた 2N 匹の犬を飼っています。

i のかわいさは a_i です。 それぞれの犬の体色は赤、緑、青のいずれかで、犬 i の体色は c_i です。 c_iR, G, B のいずれかであり、R ならばその犬の体色が赤であることを、G ならば緑であることを、B ならば青であることを表します。

すぬけ君は N 棟の犬小屋を持っており、それぞれの犬小屋に 2 匹の犬を住まわせようとしています。 どの犬もちょうど一つの犬小屋に住んでいるように住まわせる必要があることに注意してください。

2 匹の犬を同じ犬小屋に住まわせるとその小屋には 不満 が生じます。 不満の度合いは整数で表され、犬 i,j が同じ小屋にいるとき生じる不満は c_i = c_j ならば 0、そうでなければ |a_i - a_j| です。

N 棟の犬小屋に犬を 2 匹ずつ住まわせた結果生じる不満の総和としてありうる値の最小値を求めてください。

### 制約

• 1 \leq N \leq 10^{5}
• 1 \leq a_i \leq 10^{15}
• a_i は整数
• c_iR, G, B のいずれか

### 入力

N
a_{1} c_{1}
\vdots
a_{2N} c_{2N}


### 出力

N 棟の犬小屋に犬を 2 匹ずつ住まわせた結果生じる不満の総和としてありうる値の最小値を出力せよ。

### 入力例 1

1
1 R
2 G


### 出力例 1

1

• 1 のかわいさは 1、犬 2 のかわいさは 2 です。
• c_1 \neq c_2 より、不満は 1 となります。

### 入力例 2

1
1 B
2 B


### 出力例 2

0

• 1 のかわいさは 1、犬 2 のかわいさは 2 です。
• c_1 = c_2 より、不満は 0 となります。

### 入力例 3

10
585 B
293 B
788 B
222 B
772 G
841 B
115 R
603 G
450 B
325 R
851 B
205 G
134 G
651 R
565 R
548 B
391 G
19 G
808 B
475 B


### 出力例 3

0


Score : 500 points

### Problem Statement

Snuke has 2N dogs, numbered 1 through 2N.

The cuteness of Dog i is a_i. The color of Dog i is c_i, which is R, G, or B; R stands for red, G stands for green, and B stands for blue.

Snuke has N kennels, and wants to put two dogs in each kennel. Note that this means each dog will be in exactly one kennel.

When he puts two dogs in the same kennel, it will cause some dissatisfaction in that kennel. The level of dissatisfaction is represented as an integer. When Dogs i and j are in the same kennel, the dissatisfaction will be 0 if c_i = c_j and |a_i - a_j| otherwise.

Find the minimum possible total dissatisfaction when putting two dogs in each of the N kennels.

### Constraints

• 1 \leq N \leq 10^{5}
• 1 \leq a_i \leq 10^{15}
• a_i is an integer.
• c_i is R, G, or B.

### Input

Input is given from Standard Input in the following format:

N
a_{1} c_{1}
\vdots
a_{2N} c_{2N}


### Output

Print the minimum possible total dissatisfaction when putting two dogs in each of the N kennels.

### Sample Input 1

1
1 R
2 G


### Sample Output 1

1

• Dog 1 has the cuteness of 1, and Dog 2 has the cuteness of 2.
• Since c_1 \neq c_2, the dissatisfaction will be 1.

### Sample Input 2

1
1 B
2 B


### Sample Output 2

0

• Dog 1 has the cuteness of 1, and Dog 2 has the cuteness of 2.
• Since c_1 = c_2, the dissatisfaction will be 0.

### Sample Input 3

10
585 B
293 B
788 B
222 B
772 G
841 B
115 R
603 G
450 B
325 R
851 B
205 G
134 G
651 R
565 R
548 B
391 G
19 G
808 B
475 B


### Sample Output 3

0

C - Odd Even Sort

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

(1,2, \ldots, N) を並び替えた数列 p が与えられます。 はじめ、p の第 n 項は p_{n} です。

あなたの目的は N^2 回以下 操作 を行い p を昇順に並び替えることです。 あなたは操作により以下のように p を変更することができます。

• 奇数 回目の操作では 1 以上 N-1 以下の 奇数 n を選んで p_np_{n+1} を入れ替えます。
• 偶数 回目の操作では 2 以上 N-1 以下の 偶数 n を選んで p_np_{n+1} を入れ替えます。

この問題の制約下で必ず目的を達成できることが証明できます。 そのような操作列を 1 つ求めてください。

T 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

### 制約

• 与えられる入力は全て整数
• 1 \leq T \leq 250
• 2 \leq N \leq 500
• 1 \leq p_i \leq N
• p(1,2,\ldots,N) を並び替えて得られる。
• 1 つの入力ファイルにおいて N の総和は 500 を超えない。

### 入力

T
\mathrm{case}_{1}
\vdots
\mathrm{case}_{T}


N
p_1 \cdots p_N


### 出力

T 個のテストケースについて与えられた順番に以下の形式で答えを出力せよ。

M
a_1 \cdots a_M


M は操作列の長さを表し、a_ii 回目の操作で選んだ整数を表す。

### 入力例 1

2
5
2 1 3 5 4
2
1 2


### 出力例 1

2
1 4
0


• 1 つ目のテストケースについて説明します。
• 1 回目の操作で 1 を選ぶと p(1,2,3,5,4) となります。
• 2 回目の操作で 4 を選ぶと p(1,2,3,4,5) となります。
• (1,4) は操作列として正しいですが、(4,1) は操作列として正しくないことに注意してください。
• 操作を 1 度も行わなくともよいこと、操作回数を最小にする必要はないことに注意してください。

Score : 500 points

### Problem Statement

Given is a sequence p which is a permutation of (1,2, \ldots, N). Initially, the n-th term of p is p_{n}.

Your objective is to sort p in ascending order in at most N^2 operations. In one operation, you make the following change on p:

• In the 1-st, 3-rd, and subsequent odd-numbered operations, you choose an odd number n between 1 and N-1 (inclusive) to swap p_n and p_{n+1}.
• In the 2-nd, 4-th, and subsequent even-numbered operations, you choose an even number n between 2 and N-1 (inclusive) to swap p_n and p_{n+1}.

We can prove that the objective is always achievable under the Constraints of this problem. Find one sequence of operations that achieves the objective.

You will be given T test cases and asked to solve each of them.

### Constraints

• All values in input are integers.
• 1 \leq T \leq 250
• 2 \leq N \leq 500
• 1 \leq p_i \leq N
• p is a permutation of (1,2,\ldots,N).
• In one input file, the sum of N does not exceed 500.

### Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_{1}
\vdots
\mathrm{case}_{T}


Each case is in the following format:

N
p_1 \cdots p_N


### Output

For each of the T test cases, in the order they are given, print your answer in the following format:

M
a_1 \cdots a_M


Here, M represents the length of your sequence of operations, and a_i represents the integer you choose in the i-th operation.

Your output will be considered correct if, for every test case, your sequence of operations achieves the objective.

### Sample Input 1

2
5
2 1 3 5 4
2
1 2


### Sample Output 1

2
1 4
0


• Here is the description for the 1-st test case.
• Choosing 1 in the 1-st operation makes p = (1,2,3,5,4).
• Choosing 4 in the 2-nd operation makes p = (1,2,3,4,5).
• Note that although (1,4) is a valid sequence of operations, (4, 1) is not.
• Also note that it is allowed to perform no operation, and it is not required to minimize the number of operations.
D - 1 or 2

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけ君は黒板と N 個の飴を持っています。 i 番目の飴の おいしさa_i です。

すぬけ君は手持ちの飴がなくなるまで、以下の操作を繰り返します。

• 手持ちの飴から 1 つ、あるいは 2 つ選んで食べ、その後選んだ飴のおいしさの総和を黒板に書き込む(食べた飴はなくなります)。

すぬけ君は黒板に書かれた値の最大値を X、最小値を Y として X-Y が最小になるようにしたいです。 X-Y としてありうる値の最小値を求めてください。

### 制約

• 与えられる入力は全て整数
• 1 \leq N \leq 5000
• -10^{9} \leq a_i \leq 10^9

### 入力

N
a_{1} a_{2} \cdots a_N


### 入力例 1

3
1 2 4


### 出力例 1

1

• 1 回目の操作で美味しさ 1,2 の飴を食べ、2 回目の操作で美味しさ 4 の飴を食べるのが最適な操作手順の 1 つです。

### 入力例 2

2
-100 -50


### 出力例 2

0

• 1 回目の操作で美味しさ -100,-50 の飴を食べるのが最適です。

### 入力例 3

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38


### 出力例 3

13


Score : 700 points

### Problem Statement

Snuke has a blackboard and N candies. The tastiness of the i-th candy is a_i.

He will repeat the operation below until he has no more candy.

• Choose one or two of his candies and eat them (of course, they disappear). Then, write on the blackboard the total tastiness of the candies he has just chosen.

Snuke wants to minimize X-Y, where X and Y are the largest and smallest values written on the blackboard, respectively. Find the minimum possible value of X-Y.

### Constraints

• All values in input are integers.
• 1 \leq N \leq 5000
• -10^{9} \leq a_i \leq 10^9

### Input

Input is given from Standard Input in the following format:

N
a_{1} a_{2} \cdots a_N


### Output

Print the minimum possible value of X-Y, where X and Y are the largest and smallest values written on the blackboard, respectively.

### Sample Input 1

3
1 2 4


### Sample Output 1

1

• One optimal sequence of operations is to eat the candies with the tastinesses of 1 and 2 in the first operation, and then eat the candies with the tastiness of 4 in the second operation.

### Sample Input 2

2
-100 -50


### Sample Output 2

0

• It is optimal to eat both candies with the tastiness of -100 and -50 in the first operation.

### Sample Input 3

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38


### Sample Output 3

13

E - Directed Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 から N の番号がついた N 頂点の有向木が与えられます。

a(1,\ldots,N) を並び替えて得られる数列とします。また、ai 番目の項を a_i とします。

a としてありうる数列は N! 通りあります。それらのうち、下記の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

• 条件：1 \leq i \leq N を満たす任意の整数 i について、頂点 a_i から 1 度以上辺を辿って頂点 i へ到達することはできない。

### 制約

• 与えられる入力は全て整数
• 1 \leq N \leq 2000
• 1 \leq p_i < i

### 入力

N
p_{2} \cdots p_N


### 出力

(1,\ldots,N) の並び替え a のうち、問題文中の条件を満たすものの個数を 998244353 で割ったあまりを出力せよ。

### 入力例 1

4
1 1 3


### 出力例 1

4


### 入力例 2

30
1 1 3 1 5 1 1 1 8 9 7 3 11 11 15 14 4 10 11 12 1 10 13 11 7 23 8 12 18


### 出力例 2

746746186

• 998244353 で割ったあまりを出力するのを忘れずに。

Score : 700 points

### Problem Statement

Given is a directed tree with N vertices numbered 1 through N.

Vertex 1 is the root of the tree. For each integer i such that 2 \leq i \leq N, there is a directed edge from Vertex p_i to i.

Let a be the permutation of (1, \ldots, N), and a_i be the i-th element of a.

Among the N! sequences that can be a, find the number of sequences that satisfy the following condition, modulo 998244353.

• Condition: For every integer i such that 1 \leq i \leq N, Vertex i is unreachable from Vertex a_i by traversing one or more edges.

### Constraints

• All values in input are integers.
• 1 \leq N \leq 2000
• 1 \leq p_i < i

### Input

Input is given from Standard Input in the following format:

N
p_{2} \cdots p_N


### Output

Print the number of sequences a among the permutations of (1, \ldots, N) that satisfy the condition in Problem Statement, modulo 998244353.

### Sample Input 1

4
1 1 3


### Sample Output 1

4


### Sample Input 2

30
1 1 3 1 5 1 1 1 8 9 7 3 11 11 15 14 4 10 11 12 1 10 13 11 7 23 8 12 18


### Sample Output 2

746746186

• Remember to print the count modulo 998244353.
F - Logical Operations on Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 から N の番号がついた N 頂点の木が与えられます。

i 番目の辺は頂点 a_ib_i をつないでいます。

すぬけ君は頂点には 01 のラベルを、辺には ANDOR のラベルをつけることにしました。 頂点と辺へのラベルのつけ方は 2^{2N-1} 通りあります。それらのうち下記の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

• 辺を 1 本選んで縮約する(消された 2 個の頂点に書かれていたラベルを x,y、消された辺に書かれていたラベルを \mathrm{op} とする)。
• \mathrm{op}AND ならば \mathrm{AND}(x,y) を、OR ならば \mathrm{OR}(x,y) を新たな頂点にラベルとしてつける。

### 注記

• 演算 \mathrm{AND} の定義は次の通りです：\mathrm{AND}(0,0)=(0,1)=(1,0)=0,\mathrm{AND}(1,1)=1
• 演算 \mathrm{OR} の定義は次の通りです：\mathrm{OR}(1,1)=(0,1)=(1,0)=1,\mathrm{OR}(0,0)=0
• 頂点 s と頂点 t を結ぶ辺を縮約する際は、その辺を取り除くと同時に 2 頂点を併合します。縮約後の木において、併合により生まれた頂点と頂点 u を結ぶ辺が存在するのは、縮約前の木において su を結ぶ辺または tu を結ぶ辺が存在するときであり、またそのときに限られます。

### 制約

• 与えられる入力は全て整数
• 2 \leq N \leq 10^{5}
• 1 \leq a_i, b_i \leq N
• 与えられるグラフは木

### 入力

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}


### 入力例 1

2
1 2


### 出力例 1

4


### 入力例 2

20
7 3
20 18
16 12
7 2
10 5
18 16
16 3
4 11
7 15
8 1
6 1
12 13
15 5
19 17
7 1
9 8
7 17
16 14
11 7


### 出力例 2

283374562

• 998244353 で割ったあまりを出力するのを忘れずに。

Score : 800 points

### Problem Statement

Given is a tree with N vertices numbered 1 through N.

The i-th edge connects Vertices a_i and b_i.

Snuke will label each vertex with 0 or 1 and each edge with AND or OR. Among the 2^{2N-1} ways to label the vertices and edges, find the number of ways that satisfy the following condition, modulo 998244353.

Condition: There exists a sequence of N-1 operations ending up with one vertex labeled 1, where each operation consists of the steps below.

• Choose one edge and contract it. Here, let x and y be the labels of the erased vertices and \mathrm{op} be the label of the erased edge.
• If \mathrm{op} is AND, label the new vertex with \mathrm{AND}(x,y); if \mathrm{op} is OR, label the new vertex with \mathrm{OR}(x,y).

### Notes

• The operation \mathrm{AND} is defined as follows: \mathrm{AND}(0,0)=(0,1)=(1,0)=0,\mathrm{AND}(1,1)=1.
• The operation \mathrm{OR} is defined as follows: \mathrm{OR}(1,1)=(0,1)=(1,0)=1,\mathrm{OR}(0,0)=0.
• When contracting the edge connecting Vertex s and Vertex t, we merge the two vertices while removing that edge. After the contraction, there is an edge connecting the new vertex and vertex u if and only if there was an edge connecting s and u or connecting t and u before the contraction.

### Constraints

• All values in input are integers.
• 2 \leq N \leq 10^{5}
• 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
\vdots
a_{N-1} b_{N-1}


### Output

Print the number of ways to label the tree that satisfy the condition in Problem Statement, modulo 998244353.

### Sample Input 1

2
1 2


### Sample Output 1

4


### Sample Input 2

20
7 3
20 18
16 12
7 2
10 5
18 16
16 3
4 11
7 15
8 1
6 1
12 13
15 5
19 17
7 1
9 8
7 17
16 14
11 7


### Sample Output 2

283374562

• Remember to print the count modulo 998244353.