AtCoder Daily Training EASY 2026/08/27 16:00start

A - Range Swap

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

配点 : 100 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) および正整数 P,Q,R,S が与えられます。
ここで、P,Q,R,S は、1\leq P\leq Q<R\leq S \leq N および Q-P=S-R をみたしています。

数列 A の P 番目から Q 番目の項までと R 番目から S 番目の項までを入れ替えた数列を B=(B_1, B_2,\ldots, B_N) とします。
数列 B を出力してください。

制約

1\leq N \leq 100
1\leq A_i\leq 100
1\leq P\leq Q<R\leq S \leq N
Q-P=S-R
入力はすべて整数

入力

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

N P Q R S
A_1 A_2 \ldots A_N

出力

B_1, B_2,\ldots, B_N を空白区切りで出力せよ。

入力例 1

8 1 3 5 7
1 2 3 4 5 6 7 8

出力例 1

5 6 7 4 1 2 3 8

数列 A=(1,2,3,4,5,6,7,8) の 1 番目から 3 番目の項 (1,2,3) と 5 番目から 7 番目までの項 (5,6,7) を入れ替えると, B=(5,6,7,4,1,2,3,8) となります。よってこれを空白区切りで出力します。

入力例 2

5 2 3 4 5
2 2 1 1 1

出力例 2

2 1 1 2 1

数列には同じ整数が複数回現れる事もあります。

入力例 3

2 1 1 2 2
50 100

出力例 3

100 50

入力例 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

出力例 4

22 47 29 97 72 81 75 26 45 2

Score : 100 points

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.

Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.

Constraints

1\leq N \leq 100
1\leq A_i\leq 100
1\leq P\leq Q<R\leq S \leq N
Q-P=S-R
All values in the input are integers.

Input

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

N P Q R S
A_1 A_2 \ldots A_N

Output

Print B_1, B_2,\ldots, B_N, with spaces in between.

Sample Input 1

8 1 3 5 7
1 2 3 4 5 6 7 8

Sample Output 1

5 6 7 4 1 2 3 8

Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.

Sample Input 2

5 2 3 4 5
2 2 1 1 1

Sample Output 2

2 1 1 2 1

The same integer may occur multiple times in the sequence.

Sample Input 3

2 1 1 2 2
50 100

Sample Output 3

100 50

Sample Input 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

Sample Output 4

22 47 29 97 72 81 75 26 45 2

B - 12435

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

配点 : 150 点

問題文

(1,2,3,4,5) を並び替えた整数列 A=(A_1,A_2,A_3,A_4,A_5) が与えられます。

A の隣り合う 2 つの項を入れ替える操作を ちょうど 1 回 行うことで A を昇順にすることができるか判定してください。

制約

A は (1,2,3,4,5) を並び替えてできる長さ 5 の整数列

入力

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

A_1 A_2 A_3 A_4 A_5

出力

ちょうど 1 回の操作で A を昇順にすることができるならば Yes を、できないならば No を出力せよ。

入力例 1

1 2 4 3 5

出力例 1

Yes

A_3 と A_4 を入れ替えることで A=(1,2,3,4,5) となり、 A を昇順に並び替えることができます。したがって、 Yes を出力してください。

入力例 2

5 3 2 4 1

出力例 2

No

どのような操作をしても A を昇順に並び替えることはできません。

入力例 3

1 2 3 4 5

出力例 3

No

ちょうど 1 回操作をする必要があります。

入力例 4

2 1 3 4 5

出力例 4

Yes

Score : 150 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,A_3,A_4,A_5) obtained by permuting (1,2,3,4,5).

Determine whether A can be sorted in ascending order by performing exactly one operation of swapping two adjacent elements in A.

Constraints

A is an integer sequence of length 5 obtained by permuting (1,2,3,4,5).

Input

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

A_1 A_2 A_3 A_4 A_5

Output

If A can be sorted in ascending order by exactly one operation, print Yes; otherwise, print No.

Sample Input 1

1 2 4 3 5

Sample Output 1

Yes

By swapping A_3 and A_4, A becomes (1,2,3,4,5), so it can be sorted in ascending order. Therefore, print Yes.

Sample Input 2

5 3 2 4 1

Sample Output 2

No

No matter what operation is performed, it is impossible to sort A in ascending order.

Sample Input 3

1 2 3 4 5

Sample Output 3

No

You must perform exactly one operation.

Sample Input 4

2 1 3 4 5

Sample Output 4

Yes

C - Crop

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

配点 : 200 点

問題文

高さ H ピクセル、幅 W ピクセルの白黒画像があります。上から i 行目、左から j 列目のピクセルの色は文字 C_{i,j} として与えられ、. は白、# は黒を表します。

この画像の上下左右の端から、すべてのピクセルが白であるような行や列を削除します。具体的には、次の処理を順に行います。

画像の最上行がすべて白である限り、最上行を削除することを繰り返す。
画像の最下行がすべて白である限り、最下行を削除することを繰り返す。
画像の最左列がすべて白である限り、最左列を削除することを繰り返す。
画像の最右列がすべて白である限り、最右列を削除することを繰り返す。

処理後の画像を出力してください。

なお、与えられる画像には黒いピクセルが少なくとも 1 つ存在します。

制約

1 \le H, W \le 50
C_{i,j} は . または # である
黒いピクセルが少なくとも 1 つ存在する

入力

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

H W
C_{1,1}C_{1,2}\ldots C_{1,W}
C_{2,1}C_{2,2}\ldots C_{2,W}
\vdots
C_{H,1}C_{H,2}\ldots C_{H,W}

出力

処理後の画像を、以下の形式で出力せよ。
ここで、h,w は処理後の画像の高さと幅（ピクセル単位）である。
また、c_{i,j} は処理後の画像の上から i 行目、左から j 列目のピクセルの色を表す文字であり、白のときは . 、黒のときは # とする。

c_{1,1}c_{1,2}\ldots c_{1,w}
c_{2,1}c_{2,2}\ldots c_{2,w}
\vdots
c_{h,1}c_{h,2}\ldots c_{h,w}

入力例 1

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

出力例 1

.#.
###

上端の 1 行、下端の 1 行、左端の 1 列、右端の 1 列を削除すればよいです。

入力例 2

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

出力例 2

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

この画像では、最上行、最下行、最左列、最右列のいずれにも黒いピクセルが含まれています。
したがってどの行や列も削除されず、元の画像をそのまま出力すればよいです。

入力例 3

5 6
......
......
...#..
......
......

出力例 3

Score : 200 points

Problem Statement

There is a black-and-white image of height H pixels and width W pixels. The color of the pixel at the i-th row from the top and j-th column from the left is given as a character C_{i,j}, where . represents white and # represents black.

From the top, bottom, left, and right edges of this image, remove rows and columns where all pixels are white. Specifically, perform the following operations in order:

While the topmost row of the image is entirely white, repeat removing the topmost row.
While the bottommost row of the image is entirely white, repeat removing the bottommost row.
While the leftmost column of the image is entirely white, repeat removing the leftmost column.
While the rightmost column of the image is entirely white, repeat removing the rightmost column.

Output the image after processing.

The given image contains at least one black pixel.

Constraints

1 \le H, W \le 50
C_{i,j} is . or #.
At least one black pixel exists.

Input

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

H W
C_{1,1}C_{1,2}\ldots C_{1,W}
C_{2,1}C_{2,2}\ldots C_{2,W}
\vdots
C_{H,1}C_{H,2}\ldots C_{H,W}

Output

Output the image after processing in the following format.
Here, h and w are the height and width of the image after processing, in pixels, respectively.
c_{i,j} is the character representing the color of the pixel at the i-th row from the top and j-th column from the left; c_{i,j} must be . if the pixel is white and # if it is black.

c_{1,1}c_{1,2}\ldots c_{1,w}
c_{2,1}c_{2,2}\ldots c_{2,w}
\vdots
c_{h,1}c_{h,2}\ldots c_{h,w}

Sample Input 1

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

Sample Output 1

.#.
###

You should remove one row from the top edge, one row from the bottom edge, one column from the left edge, and one column from the right edge.

Sample Input 2

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

Sample Output 2

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

In this image, all of the topmost row, bottommost row, leftmost column, and rightmost column contain black pixels.
Therefore, without removing any rows or columns, you should output the original image as is.

Sample Input 3

5 6
......
......
...#..
......
......

Sample Output 3

D - Binary Alchemy

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

配点 : 200 点

問題文

N 種類の元素があり、元素には 1, 2, \ldots, N の番号が付けられています。

元素どうしは合成させることができ、元素 i と元素 j を合成すると i \geq j のとき元素 A_{i, j} に、i < j のとき元素 A_{j, i} に変化します。

元素 1 に対して元素 1, 2, \ldots, N をこの順に合成したとき、最終的に得られる元素を求めてください。

制約

1 \leq N \leq 100
1 \leq A_{i, j} \leq N
入力される値はすべて整数

入力

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

N
A_{1, 1}
A_{2, 1} A_{2, 2}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}

出力

最終的に得られる元素の番号を出力せよ。

入力例 1

出力例 1

元素 1 と元素 1 を合成すると、元素 3 が得られます。
元素 3 と元素 2 を合成すると、元素 1 が得られます。
元素 1 と元素 3 を合成すると、元素 3 が得られます。
元素 3 と元素 4 を合成すると、元素 2 が得られます。

したがって、出力するべき値は 2 です。

入力例 2

出力例 2

入力例 3

6
2
1 5
1 6 3
2 6 1 4
2 1 1 1 6
5 6 1 2 2 5

出力例 3

Score : 200 points

Problem Statement

There are N types of elements numbered 1, 2, \ldots, N.

Elements can be combined with each other. When elements i and j are combined, they transform into element A_{i, j} if i \geq j, and into element A_{j, i} if i < j.

Starting with element 1, combine it with elements 1, 2, \ldots, N in this order. Find the final element obtained.

Constraints

1 \leq N \leq 100
1 \leq A_{i, j} \leq N
All input values are integers.

Input

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

N
A_{1, 1}
A_{2, 1} A_{2, 2}
\vdots
A_{N, 1} A_{N, 2} \ldots A_{N, N}

Output

Print the number representing the final element obtained.

Sample Input 1

Sample Output 1

Combining element 1 with element 1 results in element 3.
Combining element 3 with element 2 results in element 1.
Combining element 1 with element 3 results in element 3.
Combining element 3 with element 4 results in element 2.

Therefore, the value to be printed is 2.

Sample Input 2

Sample Output 2

Sample Input 3

6
2
1 5
1 6 3
2 6 1 4
2 1 1 1 6
5 6 1 2 2 5

Sample Output 3

E - Don’t be cycle

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

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1 から N の番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めてください。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

閉路とは

単純無向グラフが閉路を持つとは、i \neq j ならば v_i \neq v_j を満たす長さ 3 以上の頂点列 (v_0, v_1, \ldots, v_{n-1}) であって、各 0 \leq i < n に対し v_i と v_{i+1 \bmod n} の間に辺が存在するものがあることをいいます。

制約

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

出力

答えを出力せよ。

入力例 1

出力例 1

頂点 1 と頂点 2 を結ぶ辺・頂点 4 と頂点 5 を結ぶ辺の 2 本を削除するなどの方法でグラフが閉路を持たないようにすることができます。
1 本以下の辺の削除でグラフが閉路を持たないようにすることはできないので、2 を出力します。

入力例 2

4 2
1 2
3 4

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multi-edges whose edges have no direction.

What is a cycle?

A cycle in a simple undirected graph is a sequence of vertices (v_0, v_1, \ldots, v_{n-1}) of length at least 3 satisfying v_i \neq v_j if i \neq j such that for each 0 \leq i < n, there is an edge between v_i and v_{i+1 \bmod n}.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq A_i, B_i \leq N
The given graph is simple.
All values in the input 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

Print the answer.

Sample Input 1

Sample Output 1

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

Sample Input 3