AtCoder Daily Training HARD 2025/11/05 18:00start

E - Make it Forest

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

配点 : 350 点

問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結ぶ辺です。
グラフを森にするためには辺を最低何本削除する必要がありますか？

森とは

単純無向グラフ F が森であるとは、F が閉路を含まないことを言います。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
1 \leq u_i \lt v_i \leq N
入力で与えられるグラフは単純
入力される値は全て整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

出力例 1

例えば 1 番目の辺を削除すると、グラフは森になります。

入力例 2

5 0

出力例 2

入力例 3

出力例 3

Score : 350 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The i-th edge connects vertices u_i and v_i.
What is the minimum number of edges that need to be deleted from this graph so that the graph becomes a forest?

What is a forest?

A simple undirected graph F is called a forest if and only if F does not contain any cycle.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
1 \leq u_i < v_i \leq N
The given graph is simple.
All input values are integers.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the answer.

Sample Input 1

Sample Output 1

For example, if you delete the first edge, the graph becomes a forest.

Sample Input 2

5 0

Sample Output 2

Sample Input 3

Sample Output 3

F - 11/22 Substring

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

配点 : 300 点

問題文

この問題における 11/22 文字列の定義は A 問題および 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 は / を 1 個以上含みます。
11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
S は 1, 2, / からなる長さ N の文字列
S は / を 1 個以上含む

入力

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

N
S

出力

11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を出力せよ。

入力例 1

8
211/2212

出力例 1

S の 2 文字目から 6 文字目からなる部分文字列は 11/22 で、これは 11/22 文字列です。S の部分文字列のうち 11/22 文字列であるものはこれが最長です。よって 5 が答えです。

入力例 2

5
22/11

出力例 2

入力例 3

22
/1211/2///2111/2222/11

出力例 3

Score : 300 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A 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.

You are given a string S of length N consisting of 1, 2, and /, where S contains at least one /.
Find the maximum length of a (contiguous) substring of S that is an 11/22 string.

Constraints

1 \leq N \leq 2 \times 10^5
S is a string of length N consisting of 1, 2, and /.
S contains at least one /.

Input

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

N
S

Output

Print the maximum length of a (contiguous) substring of S that is an 11/22 string.

Sample Input 1

8
211/2212

Sample Output 1

The substring from the 2-nd to 6-th character of S is 11/22, which is an 11/22 string. Among all substrings of S that are 11/22 strings, this is the longest. Therefore, the answer is 5.

Sample Input 2

5
22/11

Sample Output 2

Sample Input 3

22
/1211/2///2111/2222/11

Sample Output 3

G - Popcount and XOR

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

配点 : 400 点

問題文

非負整数 a,b,C が与えられます。次の 5 つの条件をすべて満たす非負整数の組 (X,Y) が存在するか判定し、存在するならひとつ出力してください。

0\leq X\lt2 ^ {60}
0\leq Y\lt2 ^ {60}
\operatorname{popcount}(X)=a
\operatorname{popcount}(Y)=b
X\oplus Y=C

ただし、\oplus はビットごとの排他的論理和を表します。

条件を満たす (X,Y) が複数存在する場合、どれを出力しても構いません。

popcount とは？

非負整数 x について x の popcount とは、x を 2 進法で表記したときの 1 の個数です。より厳密には、非負整数 x について \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) が成り立っているとき \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i です。

例えば、13 を 2 進法で表記すると 1101 なので、 \operatorname{popcount}(13)=3 となります。

ビットごとの排他的論理和とは？

非負整数 x,y について x,y のビットごとの排他的論理和 x\oplus y は以下のように定義されます。

x\oplus y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位は、x,y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位の数のうち一方のみが 1 であれば 1 、そうでなければ 0 となる。

例えば、9,3 を 2 進法で表記するとそれぞれ 1001, 0011 なので、9\oplus3=10 となります（10 を 2 進法で表記すると 1010 です）。

制約

0\leq a\leq60
0\leq b\leq60
0\leq C\lt2 ^ {60}
入力はすべて整数

入力

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

a b C

出力

条件を満たす非負整数の組が存在するならば、そのような (X,Y) をひとつ選び X,Y をこの順に空白を区切りとして出力せよ。存在しないならば、-1 を出力せよ。

入力例 1

3 4 7

出力例 1

28 27

(X,Y)=(28,27) は条件を満たします。 X,Y を 2 進法で表記するとそれぞれ 11100 と 11011 になります。

X を 2 進法で表記すると 11100 になるので、\operatorname{popcount}(X)=3 です。
Y を 2 進法で表記すると 11011 になるので、\operatorname{popcount}(Y)=4 です。
X\oplus Y を 2 進法で表記すると 00111 となり、X\oplus Y=7 です。

条件を満たす非負整数の組が複数存在する場合どれを出力しても構わないため、例えば 42 45 と出力しても正解になります。

入力例 2

34 56 998244353

出力例 2

-1

条件を満たす非負整数の組は存在しません。

入力例 3

39 47 530423800524412070

出力例 3

540431255696862041 10008854347644927

出力すべき値が 32\operatorname{bit} 整数に収まらない場合があります。

Score: 400 points

Problem Statement

You are given non-negative integers a, b, and C. Determine if there is a pair of non-negative integers (X, Y) that satisfies all of the following five conditions. If such a pair exists, print one.

0 \leq X < 2^{60}
0 \leq Y < 2^{60}
\operatorname{popcount}(X) = a
\operatorname{popcount}(Y) = b
X \oplus Y = C

Here, \oplus denotes the bitwise XOR.

If multiple pairs (X, Y) satisfy the conditions, you may print any of them.

What is popcount?

For a non-negative integer x, the popcount of x is the number of 1s in the binary representation of x. More precisely, for a non-negative integer x such that \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace), we have \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.

For example, 13 in binary is 1101, so \operatorname{popcount}(13)=3.

What is bitwise XOR?

For non-negative integers x, y, the bitwise exclusive OR x \oplus y is defined as follows.

The 2^k's place \ (k\geq0) in the binary representation of x \oplus y is 1 if exactly one of the 2^k's places \ (k\geq0) in the binary representations of x and y is 1, and 0 otherwise.

For example, 9 and 3 in binary are 1001 and 0011, respectively, so 9 \oplus 3 = 10 (in binary, 1010).

Constraints

0 \leq a \leq 60
0 \leq b \leq 60
0 \leq C < 2^{60}
All input values are integers.

Input

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

a b C

Output

If there is a pair of non-negative integers that satisfies the conditions, choose one such pair (X, Y) and print X and Y in this order, with a space in between. If no such pair exists, print -1.

Sample Input 1

3 4 7

Sample Output 1

28 27

The pair (X, Y) = (28, 27) satisfies the conditions. Here, X and Y in binary are 11100 and 11011, respectively.

X in binary is 11100, so \operatorname{popcount}(X) = 3.
Y in binary is 11011, so \operatorname{popcount}(Y) = 4.
X \oplus Y in binary is 00111, so X \oplus Y = 7.

If multiple pairs of non-negative integers satisfy the conditions, you may print any of them, so printing 42 45, for example, would also be accepted.

Sample Input 2

34 56 998244353

Sample Output 2

-1

No pair of non-negative integers satisfies the conditions.

Sample Input 3

39 47 530423800524412070

Sample Output 3

540431255696862041 10008854347644927

Note that the values to be printed may not fit in 32-bit integers.

H - Cables and Servers

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

配点 : 450 点

問題文

1 から N の番号がついた N 台のサーバーと 1 から M の番号がついた M 本のケーブルがあります。
ケーブル i はサーバー A_i とサーバー B_i を双方向に結んでいます。

以下の操作を何回か( 0 回でもよい)行うことで、全てのサーバー同士がケーブルを介して繋がっているようにしてください。

操作：ケーブルを 1 つ選び、その片方の端を別のサーバーに繋ぎ変える

操作の最小回数と、最小回数となる操作列を求めてください。

制約

2 \leq N \leq 2\times 10^5
N-1 \leq M \leq 2\times 10^5
1 \leq A_i,B_i \leq N
入力は全て整数である

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

操作回数の最小値を K とする。K+1 行出力せよ。
1 行目には K を出力せよ。
i+1 行目には i 回目の操作で選ぶケーブルの番号、繋ぎ変える前に繋がっていたサーバーの番号、繋ぎ変えたあと繋がっているサーバーの番号をこの順に空白区切りで出力せよ。

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

出力例 1

1
1 1 3

ケーブル 1 のサーバー 1 に繋がっている側の端をサーバー 3 に繋ぎ変えることで、サーバー同士がケーブルを介して繋がっている状態にすることができます。

このほか、「ケーブル 5 のサーバー 4 に繋がっている側の端をサーバー 1 に繋ぎ変える」という操作や、「ケーブル 2 のサーバー 2 に繋がっている側の端をサーバー 3 に繋ぎ変える」という操作でもサーバー同士がケーブルを介して繋がっている状態にすることができるため、正解とみなされます。

入力例 2

出力例 2

操作をする必要がないこともあります。

入力例 3

出力例 3

Score : 450 points

Problem Statement

There are N servers numbered from 1 to N and M cables numbered from 1 to M.
Cable i connects servers A_i and B_i bidirectionally.

By performing the following operation some number of times (possibly zero), make all servers connected via cables.

Operation: Choose one cable and reconnect one of its ends to a different server.

Find the minimum number of operations required and output an operation sequence achieving this minimum.

Constraints

2 \leq N \leq 2\times 10^5
N-1 \leq M \leq 2\times 10^5
1 \leq A_i, B_i \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
A_2 B_2
\vdots
A_M B_M

Output

Let the minimum number of operations be K. Print K+1 lines.

The first line should contain K.
The (i+1)-th line should contain three space-separated integers: the number of the cable chosen in the i-th operation, the server number that was originally connected at that end, and the server number to which it is connected after the operation, in this order.

If there are multiple valid solutions, any one of them will be accepted.

Sample Input 1

Sample Output 1

1
1 1 3

By reconnecting the end of cable 1 that is connected to server 1 to server 3, the servers can be connected via cables.

Operations such as reconnecting the end of cable 5 that is connected to server 4 to server 1, or reconnecting the end of cable 2 that is connected to server 2 to server 3, will also result in all servers being connected and are considered correct.

Sample Input 2

Sample Output 2

No operation may be necessary.

Sample Input 3

Sample Output 3

I - Breakdown

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

配点 : 475 点

問題文

N 個の頂点と M 本の辺からなる単純な無向グラフが与えられます。 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結ぶ辺です。また、i = 1, 2, \ldots, N について、頂点 i には正整数 W_i が割り当てられており、A_i 個のコマが置かれています。

グラフ上にコマが存在する限り、下記の操作を繰り返します。

まず、グラフ上のコマを 1 個選んで取り除き、そのコマが置かれていた頂点を x とおく。
x に隣接するいくつかの頂点からなる（空でも良い）集合 S であって、\sum_{y \in S} W_y \lt W_x であるものを選び、S に含まれる頂点それぞれに 1 個ずつコマを置く。

操作を行う回数としてあり得る最大値を出力してください。

なお、どのように操作を行っても、有限回の操作の後にはグラフ上にコマが存在しない状態に至ることが証明出来ます。

制約

入力される値はすべて整数
2 \leq N \leq 5000
1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
1 \leq u_i, v_i \leq N
u_i \neq v_i
i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
1 \leq W_i \leq 5000
0 \leq A_i \leq 10^9

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
W_1 W_2 \ldots W_N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

出力例 1

以下の説明では、各頂点にあるコマの個数を、数列 A = (A_1, A_2, \ldots, A_N) として表します。はじめ、A = (1, 0, 0, 0, 0, 1) です。

下記の手順で操作を行うことを考えます。

頂点 1 にあるコマを 1 個取り除き、頂点 2, 3 にコマを 1 個ずつ置く。その結果、A = (0, 1, 1, 0, 0, 1) となる。
頂点 2 にあるコマを 1 個取り除く。その結果、A = (0, 0, 1, 0, 0, 1) となる。
頂点 6 にあるコマを 1 個取り除く。その結果、A = (0, 0, 1, 0, 0, 0) となる。
頂点 3 にあるコマを 1 個取り除き、頂点 2 にコマを 1 個置く。その結果、A = (0, 1, 0, 0, 0, 0) となる。
頂点 2 にあるコマを 1 個取り除く。その結果、A = (0, 0, 0, 0, 0, 0) となる。

上記の手順で操作を行う回数は 5 回であり、これが操作を行う回数としてあり得る最大値です。

入力例 2

出力例 2

この入力例では、はじめからグラフ上にコマが存在しません。

入力例 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

出力例 3

Score: 475 points

Problem Statement

You are given a simple undirected graph consisting of N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge connects vertices u_i and v_i. Also, for i = 1, 2, \ldots, N, vertex i is assigned a positive integer W_i, and there are A_i pieces placed on it.

As long as there are pieces on the graph, repeat the following operation:

First, choose and remove one piece from the graph, and let x be the vertex on which the piece was placed.
Choose a (possibly empty) set S of vertices adjacent to x such that \sum_{y \in S} W_y \lt W_x, and place one piece on each vertex in S.

Print the maximum number of times the operation can be performed.

It can be proved that, regardless of how the operation is performed, there will be no pieces on the graph after a finite number of iterations.

Constraints

All input values are integers.
2 \leq N \leq 5000
1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
1 \leq u_i, v_i \leq N
u_i \neq v_i
i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
1 \leq W_i \leq 5000
0 \leq A_i \leq 10^9

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
W_1 W_2 \ldots W_N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

Sample Output 1

In the following explanation, let A = (A_1, A_2, \ldots, A_N) represent the numbers of pieces on the vertices. Initially, A = (1, 0, 0, 0, 0, 1).

Consider performing the operation as follows:

Remove one piece from vertex 1 and place one piece each on vertices 2 and 3. Now, A = (0, 1, 1, 0, 0, 1).
Remove one piece from vertex 2. Now, A = (0, 0, 1, 0, 0, 1).
Remove one piece from vertex 6. Now, A = (0, 0, 1, 0, 0, 0).
Remove one piece from vertex 3 and place one piece on vertex 2. Now, A = (0, 1, 0, 0, 0, 0).
Remove one piece from vertex 2. Now, A = (0, 0, 0, 0, 0, 0).

In this procedure, the operation is performed five times, which is the maximum possible number of times.

Sample Input 2

Sample Output 2

In this sample input, there are no pieces on the graph from the beginning.

Sample Input 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1