AtCoder Daily Training ALL 2024/12/24 19:30start

A - 11/22 String

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 150 点

問題文

この問題における 11/22 文字列の定義は C 問題および E 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

|T| は奇数である。ここで、|T| は T の長さを表す。
1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
\frac{|T|+1}{2} 文字目が / である。
\frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられます。S が 11/22 文字列であるか判定してください。

制約

1 \leq N \leq 100
S は 1, 2, / からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

S が 11/22 文字列であれば Yes を、そうでなければ No を出力せよ。

入力例 1

5
11/22

出力例 1

Yes

11/22 は問題文の 11/22 文字列の条件を満たします。

入力例 2

1
/

出力例 2

Yes

/ は問題文の 11/22 文字列の条件を満たします。

入力例 3

4
1/22

出力例 3

No

1/22 は問題文の 11/22 文字列の条件を満たしません。

入力例 4

5
22/11

出力例 4

No

Score : 150 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems C and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

|T| is odd. Here, |T| denotes the length of T.
The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
The (\frac{|T|+1}{2})-th character is /.
The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string S of length N consisting of 1, 2, and /, determine whether S is an 11/22 string.

Constraints

1 \leq N \leq 100
S is a string of length N consisting of 1, 2, and /.

Input

The input is given from Standard Input in the following format:

N
S

Output

If S is an 11/22 string, print Yes; otherwise, print No.

Sample Input 1

5
11/22

Sample Output 1

Yes

11/22 satisfies the conditions for an 11/22 string in the problem statement.

Sample Input 2

1
/

Sample Output 2

Yes

/ satisfies the conditions for an 11/22 string.

Sample Input 3

4
1/22

Sample Output 3

No

1/22 does not satisfy the conditions for an 11/22 string.

Sample Input 4

5
22/11

Sample Output 4

No

B - Count Down

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

N 以下の非負整数を大きい方から順にすべて出力してください。

制約

1 \leq N \leq 100
N は整数

入力

入力は以下の形式で標準入力から与えられる。

出力

N 以下の非負整数が X 個存在するとき、X 行出力せよ。
i=1,2,\ldots,X に対し、i 行目には N 以下の非負整数のうち大きい方から i 番目のものを出力せよ。

入力例 1

出力例 1

3 以下の非負整数は 0,1,2,3 の 4 個です。
1 行目に 3 を、2 行目に 2 を、3 行目に 1 を、4 行目に 0 を出力することでこれらを大きい方から順に出力したことになります。

入力例 2

出力例 2

Score : 100 points

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

1 \leq N \leq 100
N is an integer.

Input

The input is given from Standard Input in the following format:

Output

Print X lines, where X is the number of non-negative integers less than or equal to N.
For each i=1, 2, \ldots, X, the i-th line should contain the i-th greatest non-negative integer less than or equal to N.

Sample Input 1

Sample Output 1

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

Sample Output 2

C - Better Students Are Needed!

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

入学試験の受験者が N 人います。
試験の結果、 i 番の受験生は数学で A_i 点、英語で B_i 点を取りました。

試験の合格者は次のように決められます。

数学の点が高い方から X 人を合格とする。
次に、この時点でまだ合格となっていない受験者のうち、英語の点が高い方から Y 人を合格とする。
次に、この時点でまだ合格となっていない受験者のうち、数学と英語の合計点が高い方から Z 人を合格とする。
ここまでで合格となっていない受験者は、不合格とする。

ただし、 1. から 3. までのどの段階についても、同点であった場合は受験生の番号の小さい方を優先します。入出力例も参照してください。

以上の手順で合格者を決める時、合格となった受験生の番号を小さい方から順に改行区切りで出力してください。

制約

入力は全て整数
1 \le N \le 1000
0 \le X,Y,Z \le N
1 \le X+Y+Z \le N
0 \le A_i,B_i \le 100

入力

入力は以下の形式で標準入力から与えられる。

N X Y Z
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

合格となった受験生の番号を小さい方から順に改行区切りで出力せよ。

入力例 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

出力例 1

1
4
5

まず、数学の点が高い方から 1 人が合格となります。
- 数学の最高点は 80 点で 1 番の受験生と 3 番の受験生が並んでいますが、受験生の番号が小さい方が優先され 1 番の受験生が合格となります。
次に、まだ合格となっていない受験者のうち、英語の点が高い方から 0 人が合格となります。
- 明らかに、ここで合格者が増えることはありません。
次に、まだ合格となっていない受験者のうち、数学と英語の合計点が高い方から 2 人が合格となります。
- まず、まだ合格となっていない受験者の中で、合計点が 160 点と最も高い 5 番の受験生が合格となります。
- 次に、まだ合格となっていない受験者の中で、合計点が 150 点の 4 番の受験生と 6 番の受験生が並んでいます。受験生の番号の小さい方が優先され、 4 番の受験生が合格となります。

以上より、合格となる受験生の番号は 1,4,5 なので、小さい方から出力してください。

入力例 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

出力例 2

全員が合格となることもあります。

入力例 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

出力例 3

Score : 200 points

Problem Statement

N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.

The admissions are determined as follows.

X examinees with the highest math scores are admitted.
Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
Those examinees who are not admitted yet are rejected.

Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.

Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.

Constraints

All values in input are integers.
1 \le N \le 1000
0 \le X,Y,Z \le N
1 \le X+Y+Z \le N
0 \le A_i,B_i \le 100

Input

Input is given from Standard Input in the following format:

N X Y Z
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the examinees' number of the admitted examinees in ascending order, separated by newlines.

Sample Input 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

Sample Output 1

1
4
5

First, 1 examinee with the highest math score is admitted.
- Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
- Obviously, it does not affect the admissions.
Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
- First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
- Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.

Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.

Sample Input 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

Sample Output 2

All examinees may be admitted.

Sample Input 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

Sample Output 3

D - Same Map in the RPG World

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。

縦 H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。
A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。

次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。

j=1, 2, \dots, W について次の操作を同時に行う。
- A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} を A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j} に同時に置き換える。
i = 1, 2, \dots, H について次の操作を同時に行う。
- A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} を A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1} に同時に置き換える。

次の条件を満たす非負整数の組 (s, t) は存在しますか？存在する場合は Yes を、存在しない場合は No を出力してください。

縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の A が B と一致する。

ここで、A と B が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して A_{i, j} = B_{i, j} が成り立つことを言います。

制約

2 \leq H, W \leq 30
A_{i,j},B_{i,j} は # または .
H, W は整数

入力

入力は以下の形式で標準入力から与えられる。

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

出力

条件を満たす整数の組 (s, t) が存在する場合は Yes を、存在しない場合は No を出力せよ。

入力例 1

4 3
..#
...
.#.
...
#..
...
.#.
...

出力例 1

Yes

(s, t) = (2, 1) とすると A と B を一致させることができます。
(s, t) = (2, 1) の時の操作の手順を説明します。はじめ、A は次の通りです。

..#
...
.#.
...

まず、縦方向のシフトを行います。A は次のようになります。

...
.#.
...
..#

次に、再び縦方向のシフトを行います。A は次のようになります。

.#.
...
..#
...

最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。

#..
...
.#.
...

入力例 2

3 2
##
##
#.
..
#.
#.

出力例 2

No

どのように (s, t) を選んでも A と B を一致させることはできません。

入力例 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

出力例 3

Yes

入力例 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

出力例 4

Yes

Score : 200 points

Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

For each j=1, 2, \dots, W, simultaneously do the following:
- simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
For each i = 1, 2, \dots, H, simultaneously do the following:
- simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

2 \leq H, W \leq 30
A_{i,j} is # or ., and so is B_{i,j}.
H and W are integers.

Input

The input is given from Standard Input in the following format:

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

Output

Print Yes if there is a conforming integer pair (s, t); print No otherwise.

Sample Input 1

4 3
..#
...
.#.
...
#..
...
.#.
...

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

..#
...
.#.
...

We first apply a vertical shift to make A as follows.

...
.#.
...
..#

Then we apply another vertical shift to make A as follows.

.#.
...
..#
...

Finally, we apply a horizontal shift to make A as follows, which equals B.

#..
...
.#.
...

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.

Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes

E - XX to XXX

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

英小文字からなる 2 つの文字列 S, T が与えられます。次の操作を好きな回数（ 0 回でも良い）行うことで、S を T と一致させることができるかを判定してください。

S において同じ文字が 2 文字連続しているところの間に、その文字と同じ文字を 1 つ挿入する。すなわち、下記の 3 つの手順からなる操作を行う。

現在の S の長さを N とし、S = S_1S_2\ldots S_N とする。

1 以上 N-1 以下の整数 i であって、S_i = S_{i+1} を満たすものを 1 つ選択する。（ただし、そのような i が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。）

S の i 文字目と i+1 文字目の間に文字 S_i(= S_{i+1}) を 1 つ挿入する。その結果、S は長さ N+1 の文字列 S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N となる。

制約

S と T はそれぞれ英小文字からなる長さ 2 以上 2 \times 10^5 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

S を T と一致させることができる場合は Yes を、そうでない場合は No を出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

abbaac
abbbbaaac

出力例 1

Yes

下記の 3 回の操作によって、S = abbaac を T = abbbbaaac に一致させることができます。

まず、S の 2 文字目と 3 文字目の間に b を挿入する。その結果、S = abbbaac となる。
次に、再び S の 2 文字目と 3 文字目の間に b を挿入する。その結果、S = abbbbaac となる。
最後に、S の 6 文字目と 7 文字目の間に a を挿入する。その結果、S = abbbbaaac となる。

よって、Yes を出力します。

入力例 2

xyzz
xyyzz

出力例 2

No

どのように操作を行っても、 S = xyzz を T = xyyzz に一致させることはできません。よって、No を出力します。

Score : 300 points

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

Let N be the current length of S, and S = S_1S_2\ldots S_N.

Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)

Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S equal T, print Yes; otherwise, print No. Note that the judge is case-sensitive.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

F - Robot Takahashi

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

子供と大人があわせて N 人います。i 番目の人の体重は W_i です。
それぞれの人が子供か大人かは、0 と 1 からなる長さ N の文字列 S によって表され、
S の i 文字目が 0 であるとき i 番目の人が子供であることを、1 であるとき i 番目の人が大人であることをさします。

ロボットである高橋君に対して実数 X を設定すると、高橋君はそれぞれの人に対して、体重が X 未満なら子供、X 以上なら大人と判定します。
実数 X に対してf(X) を、高橋君に X を設定したときに N 人のうち子供か大人かを正しく判定できる人数で定めます。

X が実数全体を動くとき、f(X) の最大値を求めてください。

制約

1\leq N\leq 2\times 10^5
S は 0 と 1 からなる長さ N の文字列
1\leq W_i\leq 10^9
N,W_i は整数

入力

入力は以下の形式で標準入力から与えられる。

N
S
W_1 W_2 \ldots W_N

出力

f(X) の最大値を整数で一行に出力せよ。

入力例 1

5
10101
60 45 30 40 80

出力例 1

X=50 と設定すると、高橋君は 2,3,4 番目の人を子供、 1,5 番目の人を大人と判定します。
実際には 2,4 番目の人が子供、 1,3,5 番目の人が大人であるので、このとき、1,2,4,5 番目の合計 4 人に対して正しく判定できています。よって、f(50)=4 です。

5 人全員に対して正しく判定できるような X は存在しないのでこのときが最大です。よって、4 を出力します。

入力例 2

3
000
1 2 3

出力例 2

例えば、X=10 とすると最大値 f(10)=3 を達成します。
全員が大人、または全員が子供である可能性もあることに注意してください。

入力例 3

5
10101
60 50 50 50 60

出力例 3

例えば、X=55 とすると最大値 f(55)=4 を達成します。
同じ体重の人が複数人存在する可能性もあることに注意してください。

Score : 300 points

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

1\leq N\leq 2\times 10^5
S is a string of length N consisting of 0 and 1.
1\leq W_i\leq 10^9
N and W_i are integers.

Input

Input is given from Standard Input in the following format:

N
S
W_1 W_2 \ldots W_N

Output

Print the maximum value of f(X) as an integer in a single line.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

G - Erase Leaves

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

頂点 1, 頂点 2,\ldots, 頂点 N の N 個の頂点からなる木が与えられます。 i 番目 (1\leq i\lt N) の辺は頂点 u _ i と v _ i を結んでいます。

次の操作を好きな回数繰り返すことを考えます。

葉である頂点 v を 1 つ選び、頂点 v およびそれに接続する辺をすべて削除する。

頂点 1 を削除するまでに最小で操作を何回行う必要があるか求めてください。

木とは？

木とは、無向グラフのうち連結であって閉路がないものです。詳しくはこちらをご覧ください: Wikipedia「木 (数学)」

葉とは？

木の葉とは、木の頂点のうち次数がたかだか 1 であるものです。

制約

2\leq N\leq3\times10^5
1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
与えられるグラフは木
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ {N-1} v _ {N-1}

出力

答えを 1 行で出力せよ。

入力例 1

出力例 1

与えられるグラフは次のようになります。

たとえば、頂点 9,8,7,6,1 の順に選んで操作を行うことで、5 回の操作で頂点 1 を削除することができます。

4 回以下の操作では頂点 1 を削除することはできないため、5 を出力してください。

入力例 2

出力例 2

与えられたグラフにおいて、頂点 1 は葉です。よって、1 回目の操作で頂点 1 を選んで削除することができます。

入力例 3

出力例 3

Score : 400 points

Problem Statement

You are given a tree with N vertices: vertex 1, vertex 2, \ldots, vertex N. The i-th edge (1\leq i\lt N) connects vertex u _ i and vertex v _ i.

Consider repeating the following operation some number of times:

Choose one leaf vertex v and delete it along with all incident edges.

Find the minimum number of operations required to delete vertex 1.

What is a tree?

A tree is an undirected graph that is connected and has no cycles. For more details, see: Wikipedia "Tree (graph theory)".

What is a leaf?

A leaf in a tree is a vertex with a degree of at most 1.

Constraints

2\leq N\leq3\times10^5
1\leq u _ i\lt v _ i\leq N\ (1\leq i\lt N)
The given graph is a tree.
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ {N-1} v _ {N-1}

Output

Print the answer in a single line.

Sample Input 1

Sample Output 1

The given graph looks like this:

For example, you can choose vertices 9,8,7,6,1 in this order to delete vertex 1 in five operations.

Vertex 1 cannot be deleted in four or fewer operations, so print 5.

Sample Input 2

Sample Output 2

In the given graph, vertex 1 is a leaf. Hence, you can choose and delete vertex 1 in the first operation.

Sample Input 3

Sample Output 3

H - Sinking Land

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

H \times W の大きさの島があり、島は周りを海で囲まれています。
島は縦 H 個 \times 横 W 個の 1\times 1 の区画に分けられており、上から i 番目かつ左から j 番目の区画の（現在の海面を基準にした）標高は A_{i,j} です。

現在から 1 年ごとに海面の高さが 1 ずつ上昇します。
このとき、海または海に沈んだ区画に上下左右に隣接する区画であって、標高が海面の高さ以下の区画は海に沈みます。
ここで、ある区画が新しく海に沈んだときそれと上下左右に隣接する区画であって海面の高さ以下のものも同時に海に沈み、これによって新しく沈んだ区画についてもこれは繰り返されます。

i=1,2,\ldots, Y それぞれについて、現在から i 年後に、島のうち海に沈まず残っている部分の面積を求めてください。

制約

1\leq H,W\leq 1000
1\leq Y\leq 10^5
1\leq A_{i,j}\leq 10^5
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

H W Y
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}

出力

Y 行出力せよ。 i 行目 (1\leq i\leq Y) には現在から i 年後に海に沈まず残っている島の面積を出力せよ。

入力例 1

出力例 1

島の上から i 番目かつ左から j 番目の区画を (i,j) で表します。このとき、次のようになります。

1 年後、海面は現在より 1 上昇しますが、海に面している標高 1 の区画は存在しないため、どの区画も沈みません。よって、1 行目には 9 を出力します。
2 年後、海面は現在より 2 上昇し、(1,2) が海に沈みます。これによって、(2,2) は海に沈んだ区画に隣接する区画となりますが、その標高は 2 以下であるため、これも海に沈みます。これら以外にこの時点で他に沈む区画はありません。よって、2 つの区画が沈むため、2 行目には 9-2=7 を出力します。
3 年後、海面は現在より 3 上昇し、(2,1) が新しく海に沈みます。他に沈む区画はありません。よって、3 行目には 6 を出力します。
4 年後、海面は現在より 4 上昇し、(2,3) が新しく海に沈みます。他に沈む区画はありません。よって、4 行目には 5 を出力します。
5 年後、海面は現在より 5 上昇し、(3,2) が新しく海に沈みます。他に沈む区画はありません。よって、5 行目には 4 を出力します。

よって、9,7,6,5,4 をこの順に各行に出力します。

入力例 2

出力例 2

15
7
0

Score : 450 points

Problem Statement

There is an island of size H \times W, surrounded by the sea.
The island is divided into H rows and W columns of 1 \times 1 sections, and the elevation of the section at the i-th row from the top and the j-th column from the left (relative to the current sea level) is A_{i,j}.

Starting from now, the sea level rises by 1 each year.
Here, a section that is vertically or horizontally adjacent to the sea or a section sunk into the sea and has an elevation not greater than the sea level will sink into the sea.
Here, when a section newly sinks into the sea, any vertically or horizontally adjacent section with an elevation not greater than the sea level will also sink into the sea simultaneously, and this process repeats for the newly sunk sections.

For each i=1,2,\ldots, Y, find the area of the island that remains above sea level i years from now.

Constraints

1 \leq H, W \leq 1000
1 \leq Y \leq 10^5
1 \leq A_{i,j} \leq 10^5
All input values are integers.

Input

The input is given from Standard Input in the following format:

H W Y
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}

Output

Print Y lines. The i-th line (1 \leq i \leq Y) should contain the area of the island that remains above sea level i years from now.

Sample Input 1

Sample Output 1

Let (i,j) denote the section at the i-th row from the top and the j-th column from the left. Then, the following happens:

After 1 year, the sea level is higher than now by 1, but there are no sections with an elevation of 1 that are adjacent to the sea, so no sections sink. Thus, the first line should contain 9.
After 2 years, the sea level is higher than now by 2, and (1,2) sinks into the sea. This makes (2,2) adjacent to a sunken section, and its elevation is not greater than 2, so it also sinks. No other sections sink at this point. Thus, two sections sink, and the second line should contain 9-2=7.
After 3 years, the sea level is higher than now by 3, and (2,1) sinks into the sea. No other sections sink. Thus, the third line should contain 6.
After 4 years, the sea level is higher than now by 4, and (2,3) sinks into the sea. No other sections sink. Thus, the fourth line should contain 5.
After 5 years, the sea level is higher than now by 5, and (3,2) sinks into the sea. No other sections sink. Thus, the fifth line should contain 4.

Therefore, print 9, 7, 6, 5, 4 in this order, each on a new line.

Sample Input 2

Sample Output 2

15
7
0

I - Minimum Bounding Box 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

縦 H 行、横 W 列のグリッドがあります。

このグリッドから一様ランダムに K 個のマスを選びます。選んだマスを全て含むような（グリッドの軸に辺が平行な）最小の長方形に含まれるマスの個数がスコアとなります。

得られるスコアの期待値を \text{mod }998244353 で求めてください。

有理数 \text{mod }998244353 とは

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

1\leq H,W \leq 1000
1\leq K \leq HW
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

H W K

出力

答えを出力せよ。

入力例 1

2 2 2

出力例 1

665496238

マス (1,1) とマス (2,2) が選ばれた場合、またはマス (1,2) とマス (2,1) が選ばれた場合の 2 通りではスコアは 4 となります。また、それ以外の 4 通りではスコアは 2 となります。

よって得られるスコアの期待値は \frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3} であり、665496238 \times 3 \equiv 8\pmod{998244353} なので 665496238 が答えとなります。

入力例 2

10 10 1

出力例 2

入力例 3

314 159 2653

出力例 3

639716353

Score : 500 points

Problem Statement

We have a grid with H rows and W columns.

We choose K cells in this grid uniformly at random. The score is the number of cells in the minimum rectangle (whose edges are parallel to the axes of the grid) that contains all of the chosen cells.

Find the expected score modulo 998244353.

What is rational number modulo 998244353?

We can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find such R.

Constraints

1\leq H,W \leq 1000
1\leq K \leq HW
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

H W K

Output

Print the answer.

Sample Input 1

2 2 2

Sample Output 1

665496238

The score equals 4 in the following two cases: if cells (1,1) and (2,2) are chosen, or cells (1,2) and (2,1) are chosen. The other four cases yield a score of 2.

Thus, the expected score equals \frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3}. Since 665496238 \times 3 \equiv 8\pmod{998244353}, you should print 665496238.

Sample Input 2

10 10 1

Sample Output 2

Sample Input 3

314 159 2653

Sample Output 3

639716353