AtCoder Daily Training HARD 2025/11/26 16:00start

E - Centers

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

配点 : 250 点

問題文

1,2,\dots,N がちょうど 3 回ずつ現れる長さ 3N の数列 A=(A_1,A_2,\dots,A_{3N}) が与えられます。

i=1,2,\dots,N について、A の中にある i のうち真ん中にあるものの添字を f(i) と定めます。 1,2,\dots,N を f(i) の昇順に並べ替えてください。

f(i) の定義は厳密には以下の通りです。

A_j = i を満たす j が j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma) であるとする。このとき、f(i) = \beta である。

制約

1\leq N \leq 10^5
1 \leq A_j \leq N
i=1,2,\dots,N それぞれについて、A の中に i はちょうど 3 回現れる
入力は全て整数

入力

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

N
A_1 A_2 \dots A_{3N}

出力

1,2,\dots,N を f(i) の昇順に並べ替えてできる長さ N の数列を空白区切りで出力せよ。

入力例 1

3
1 1 3 2 3 2 2 3 1

出力例 1

1 3 2

A の中にある 1 は A_1,A_2,A_9 なので、f(1) = 2 です。
A の中にある 2 は A_4,A_6,A_7 なので、f(2) = 6 です。
A の中にある 3 は A_3,A_5,A_8 なので、f(3) = 5 です。

よって、f(1) < f(3) < f(2) であるため 1,3,2 の順に出力します。

入力例 2

1
1 1 1

出力例 2

入力例 3

4
2 3 4 3 4 1 3 1 1 4 2 2

出力例 3

3 4 1 2

Score : 250 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

1\leq N \leq 10^5
1 \leq A_j \leq N
i occurs in A exactly three times, for each i=1,2,\dots,N.
All input values are integers.

Input

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

N
A_1 A_2 \dots A_{3N}

Output

Print the sequence of length N obtained by sorting 1,2,\dots,N in ascending order of f(i), separated by spaces.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

Sample Input 3

4
2 3 4 3 4 1 3 1 1 4 2 2

Sample Output 3

3 4 1 2

F - Perfect Bus

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

配点 : 250 点

問題文

一台のバスが走っています。バスの乗客の数は常に非負整数です。

このバスにはある時点で 0 人以上の乗客が乗っており、その時点から現在までに N 回停車しました。このうち i 回目の停車では乗客が差し引き A_i 人増えました。A_i は負の値であることもあり、その場合は乗客が差し引き -A_i 人減ったことを意味しています。また、停車時以外には乗客の乗り降りはありませんでした。

与えられた情報に矛盾しない現在のバスの乗客の数として考えられる最小値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
-10^9 \leq A_i \leq 10^9
入力される数値はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

4
3 -5 7 -4

出力例 1

はじめに乗っている乗客の人数が 2 人であるとき、現在の乗客の人数は 2 + 3 + (-5) + 7 + (-4) = 3 人であり、さらにバスの乗客の人数は常に非負整数となります。

入力例 2

5
0 0 0 0 0

出力例 2

入力例 3

4
-1 1000000000 1000000000 1000000000

出力例 3

3000000000

Score: 250 points

Problem Statement

A bus is in operation. The number of passengers on the bus is always a non-negative integer.

At some point in time, the bus had zero or more passengers, and it has stopped N times since then. At the i-th stop, the number of passengers increased by A_i. Here, A_i can be negative, meaning the number of passengers decreased by -A_i. Also, no passengers got on or off the bus other than at the stops.

Find the minimum possible current number of passengers on the bus that is consistent with the given information.

Constraints

1 \leq N \leq 2 \times 10^5
-10^9 \leq A_i \leq 10^9
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

4
3 -5 7 -4

Sample Output 1

If the initial number of passengers was 2, the current number of passengers would be 2 + 3 + (-5) + 7 + (-4) = 3, and the number of passengers on the bus would have always been a non-negative integer.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

Sample Input 3

4
-1 1000000000 1000000000 1000000000

Sample Output 3

3000000000

G - Step Up Robot

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

配点 : 400 点

問題文

無限に続く階段があります。一番下は 0 段目で、1 段のぼるごとに 1 段目、2 段目と続きます。

0 段目に階段登りロボットがいます。階段登りロボットは、一回の動作で A _ 1,A _ 2,\ldots,A _ N 段ぶん階段をのぼることができます。つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は i+A _ 1 段目、i+A _ 2 段目、⋯、i+A _ N 段目のいずれかにいることができます。それ以外の段数を一回の動作でのぼることはできません。階段登りロボットは階段を下ることもできません。

階段の B _ 1,B _ 2,\ldots,B _ M 段目にはモチが設置されています。モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。

階段登りロボットは階段のちょうど X 段目にのぼりたいです。階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。

制約

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N
M
B _ 1 B _ 2 \ldots B _ M
X

出力

階段登りロボットが階段のちょうど X 段目にのぼることができるとき Yes を、そうでないとき No を 1 行に出力せよ。

入力例 1

出力例 1

Yes

例えば、次のようにして 15 段目に到達することができます。

階段を 3 段のぼる。ロボットは 3 段目に移動する。
階段を 4 段のぼる。ロボットは 7 段目に移動する。
階段を 5 段のぼる。ロボットは 12 段目に移動する。
階段を 3 段のぼる。ロボットは 15 段目に移動する。

入力例 2

出力例 2

No

どのように移動しても階段登りロボットが階段のちょうど 8 段目にいることはできません。

入力例 3

4
2 5 7 8
5
2 9 10 11 19
20

出力例 3

Yes

Score : 400 points

Problem Statement

There is a staircase with infinite steps. The foot of the stairs is the 0-th step, the next step is the 1-st step, the next is the 2-nd, and so on.

There is a stair-climbing robot on the 0-th step. The robot can climb up A _ 1,A _ 2,\ldots, or A _ N steps at a time. In other words, when the robot is on the i-th step, it can step onto one of the (i+A _ 1)-th step, (i+A _ 2)-th step, \ldots, and (i+A _ N)-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.

There are traps on the B _ 1-th, B _ 2-th, \ldots, and B _ M-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.

The robot wants to step onto the X-th step. Determine whether it is possible to do so.

Constraints

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
All values in the input are integers.

Input

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

N
A _ 1 A _ 2 \ldots A _ N
M
B _ 1 B _ 2 \ldots B _ M
X

Output

In a single line, print Yes if the robot can step onto the X-th step, and No otherwise.

Sample Input 1

Sample Output 1

Yes

For example, the robot can reach the 15-th step as follows.

Climb up 3 steps. The robot is now on the 3-rd step.
Climb up 4 steps. The robot is now on the 7-th step.
Climb up 5 steps. The robot is now on the 12-th step.
Climb up 3 steps. The robot is now on the 15-th step.

Sample Input 2

Sample Output 2

No

No matter how the robot moves, it cannot step onto the 8-th step.

Sample Input 3

4
2 5 7 8
5
2 9 10 11 19
20

Sample Output 3

Yes

H - Development

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

配点 : 450 点

問題文

AtCoder 国には 1 から N の番号がついた N 個の街と、M 本の道路、K 個の空港があります。

i 番目の道路は街 A_i と街 B_i を双方向に結び、移動に C_i 時間かかります。
空港は街 D_1,\ldots,D_K にあり、空港がある街同士は T 時間で移動できます。

Q 個のクエリが与えられるので順に処理してください。クエリは次の 3 種類のいずれかです。

1 x y t: 街 x と街 y を双方向に t 時間で結ぶ道路が作られる。
2 x: 街 x に空港が作られる。
3: f(x,y) を、街 x から街 y へ道路と空港を使って到達可能なときその最短時間、到達不可能なとき 0 とする。\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y) を求める。

制約

1 \leq N \leq 500
0 \leq M \leq 10^5
1 \leq A_i < B_i \leq N
1 \leq C_i \leq 10^9
0 \leq K \leq N
1 \leq T \leq 10^9
1 \leq D_1 < \dots < D_K \leq N
1 \leq Q \leq 1000
1 種類目のクエリにおいて、1\leq x < y \leq N, 1 \leq t \leq 10^9
2 種類目のクエリにおいて、1 \leq x \leq N
入力は全て整数

入力

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M
K T
D_1 \dots D_K
Q
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

\mathrm{Query}_i は i 番目のクエリを表し、その形式と意味は問題文中に与えられた通りである。

出力

3 種類目のクエリの解を順に改行区切りで出力せよ。

入力例 1

出力例 1

440
280
900

AtCoder 国には 4 つの街があり、最初、街 1 と街 2 の間を 10 時間で移動できる道路と、街 1 と街 3 の間を 100 時間で移動できる空港があります。

最初、f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=100,f(2,3)=f(3,2)=110 であり、その他は 0 なので、\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=440 です。
新たに街 2 と街 3 を 60 時間で結ぶ道路が作られました。
f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70,f(2,3)=f(3,2)=60 であり、その他は 0 なので、\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=280 です。
新たに街 4 に空港ができました。
f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70,f(1,4)=f(4,1)=100,f(2,3)=f(3,2)=60,f(2,4)=f(4,2)=110,f(3,4)=f(4,3)=100 であり、その他は 0 なので、\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=900 です。

2つの街の間に複数の道路が作られることや、1つの街に複数の空港が作られることもあります。

Score : 450 points

Problem Statement

AtCoder Country has N cities numbered from 1 to N, M roads, and K airports.

The i-th road connects cities A_i and B_i bidirectionally and takes C_i hours to travel. There are airports in cities D_1,\ldots,D_K, and you can travel between cities with airports in T hours.

Process Q queries in order. Each query is one of the following three types:

1 x y t: A road connecting cities x and y bidirectionally in t hours is built.
2 x: An airport is built in city x.
3: Let f(x,y) be the smallest number of hours needed to reach city y from city x using roads and airports if reachable, and 0 if unreachable. Find \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y).

Constraints

1 \leq N \leq 500
0 \leq M \leq 10^5
1 \leq A_i < B_i \leq N
1 \leq C_i \leq 10^9
0 \leq K \leq N
1 \leq T \leq 10^9
1 \leq D_1 < \dots < D_K \leq N
1 \leq Q \leq 1000
For type 1 queries: 1\leq x < y \leq N, 1 \leq t \leq 10^9.
For type 2 queries: 1 \leq x \leq N.
All input values are integers.

Input

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

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M
K T
D_1 \dots D_K
Q
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

\mathrm{Query}_i represents the i-th query, whose format and meaning are as given in the problem statement.

Output

Output the answers to type 3 queries in order, separated by newlines.

Sample Input 1

Sample Output 1

440
280
900

AtCoder Country has four cities. Initially, there is a road connecting cities 1 and 2 in 10 hours, and airports connecting cities 1 and 3 in 100 hours.

Initially, f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=100, f(2,3)=f(3,2)=110, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=440.
A new road connecting cities 2 and 3 in 60 hours is built.
f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70, f(2,3)=f(3,2)=60, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=280.
A new airport is built in city 4.
f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70, f(1,4)=f(4,1)=100, f(2,3)=f(3,2)=60, f(2,4)=f(4,2)=110, f(3,4)=f(4,3)=100, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=900.

Multiple roads may exist between some pair of cities. Also, a city may have multiple airports.

I - Black and White Rooks

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

配点 : 500 点

問題文

縦 N 行、横 M 列のマス目に、黒い飛車の駒 B 個と白い飛車の駒 W 個を設置することを考えましょう。

以下の条件をすべて満たす設置の仕方を いい配置 と呼びます。

B+W 個の駒すべてが設置されている。
1 つのマスに置かれている駒の数は高々 1 つである。
ある白い駒と黒い駒の組であって、互いが互いを攻撃しているようなものが存在しない。すなわち、ある白い駒と黒い駒の組であって、一方が 1 手の移動によってもう片方が置かれているマスに到達できるようなものが存在しない。

ここで、飛車の駒は、今いる位置から上、下、右、左のいずれかの方向に伸びる直線上にあり、かつ他の駒を飛び越えずに到達できるマスに 1 手で移動することができます。

いい配置としてあり得るものは何通りありますか？答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。

同じ色の駒同士は区別しないものとします。

制約

1 \leq N,M \leq 50
1 \leq B,W \leq 2500
B+W \leq N \times M
入力はすべて整数

入力

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

N M B W

出力

答えを 998244353 で割ったあまりを出力せよ。

入力例 1

2 2 1 1

出力例 1

いい配置としてあり得るものは以下の 4 通りです。

入力例 2

1 2 1 1

出力例 2

いい配置としてあり得るものが存在しない場合もあります。

入力例 3

40 40 30 30

出力例 3

467620384

998244353 で割ったあまりを出力することに注意してください。

Score : 500 points

Problem Statement

Consider placing B black rooks and W white rooks on a grid with N horizontal rows and M vertical columns.

A placement of the rooks satisfying all of the following conditions is called a good placement.

All B+W rooks are placed on the grid.
At most one rook is placed in the same square.
There is no pair of white rook and black rook attacking each other. That is, there is no pair of white rook and black rook such that one of them can reach the square in which the other is placed in one move.

Here, in one move, a rook can reach any square that is on a horizontal or vertical line from its current position and is reachable without jumping over another rook.

How many good placements are there? Since this count can be enormous, print it modulo 998244353.

Rooks in the same color are not distinguished.

Constraints

1 \leq N,M \leq 50
1 \leq B,W \leq 2500
B+W \leq N \times M
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M B W

Output

Print the count modulo 998244353.

Sample Input 1

2 2 1 1

Sample Output 1

There are four good placements as follows.

Sample Input 2

1 2 1 1

Sample Output 2

There may be no good placement.

Sample Input 3

40 40 30 30

Sample Output 3

467620384

Be sure to print the count modulo 998244353.