AtCoder Daily Training EASY 2025/02/26 18:00start

A - Range Swap

Time Limit: 2 sec / Memory Limit: 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 - Tires

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

末尾が er または ist であるような文字列 S が与えられます。
S の末尾が er である場合は er を、 ist である場合は ist を出力してください。

制約

2 \le |S| \le 20
S は英小文字のみからなる。
S の末尾は er または ist である。

入力

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

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

er

S="atcoder" の末尾は er です。

入力例 2

tourist

出力例 2

ist

入力例 3

er

出力例 3

er

Score : 100 points

Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

2 \le |S| \le 20
S consists of lowercase English letters.
S ends with er or ist.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er

C - Line Sensor

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。

1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。

j 列目に置かれている箱の個数。言い換えると、C_{i,j} が # であるような整数 i の個数。

X_1, X_2, \dots, X_W をすべて求めてください。

制約

1 \leq H \leq 1000
1 \leq W \leq 1000
H, W は整数
C_{i, j} は . または #

入力

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

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

出力

X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。

X_1 X_2 \dots X_W

入力例 1

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

出力例 1

1 2 0 3

1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。

入力例 2

3 7
.......
.......
.......

出力例 2

0 0 0 0 0 0 0

箱が置かれているマスが存在しない場合もあります。

入力例 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

出力例 3

2 7 4

入力例 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

出力例 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

Score : 200 points

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

1 \leq H \leq 1000
1 \leq W \leq 1000
H and W are integers.
C_{i, j} is . or #.

Input

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

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

Output

Print X_1, X_2, \dots, X_W in the following format:

X_1 X_2 \dots X_W

Sample Input 1

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

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

D - Matrix Transposition

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

H 行 W 列の行列 A が与えられます。
A の上から i 行目、左から j 列目の要素は A_{i,j} です。

ここで、W 行 H 列の行列 B を、上から i 行目、左から j 列目の要素が A_{j,i} と一致するような行列として定めます。
すなわち、B は A の転置行列です。

B を出力してください。

制約

1\leq H,W \leq 10^5
H \times W \leq 10^5
1 \leq A_{i,j} \leq 10^9
入力は全て整数である

入力

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

H W
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}

出力

B を以下の形式で出力せよ。

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

入力例 1

出力例 1

1 4 7 10
2 5 8 11
3 6 9 12

たとえば A_{2,1}=4 なので、転置行列 B の上から 1 行目、左から 2 列目の要素は 4 になります。

入力例 2

2 2
1000000000 1000000000
1000000000 1000000000

出力例 2

1000000000 1000000000
1000000000 1000000000

Score : 200 points

Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

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

Input

Input is given from Standard Input in the following format:

H W
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 B in the following format:

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

Sample Input 1

Sample Output 1

1 4 7 10
2 5 8 11
3 6 9 12

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000

E - Standing On The Shoulders

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人の巨人がいます。巨人にはそれぞれ 1, 2, \ldots, N の名前がついており、巨人 i が地面に立ったとき、肩の高さは A_i、頭の高さは B_i となります。

あなたは (1, 2, \ldots, N) を並べ替えて得られる数列 (P_1, P_2, \ldots, P_N) を選び、以下の規則に従って N 人の巨人を積み上げることができます。

まず地面に巨人 P_1 を立たせる。巨人 P_1 の肩は地面を基準として A_{P_1}、頭は地面を基準として B_{P_1} の高さとなる。
i = 1, 2, \ldots, N - 1 の順に巨人 P_i の肩の上に巨人 P_{i + 1} を立たせる。巨人 P_i の肩が地面を基準として高さ t のとき、巨人 P_{i + 1} の肩は地面を基準として t + A_{P_{i + 1}}、頭は地面を基準として t + B_{P_{i + 1}} の高さとなる。

一番上に立っている巨人、すなわち巨人 P_N の地面を基準とした頭の高さとして実現できる最大値を求めてください。

制約

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

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ。

入力例 1

出力例 1

(P_1, P_2, P_3) = (2, 1, 3) とすると、地面を基準として巨人 2 は肩の高さが 5、頭の高さが 8、巨人 1 は肩の高さが 9、頭の高さが 15、巨人 3 は肩の高さが 11、頭の高さが 18 となります。

一番上に立っている巨人の頭の高さが地面を基準として 18 より大きくなることはないため 18 を出力します。

入力例 2

出力例 2

入力例 3

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

出力例 3

7362669937

Score: 300 points

Problem Statement

There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.

You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:

First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.
For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.

Find the maximum possible height of the head of the topmost giant P_N from the ground.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq B_i \leq 10^9
All input values are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer.

Sample Input 1

Sample Output 1

If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.

The head height of the topmost giant from the ground cannot be greater than 18, so print 18.

Sample Input 2

Sample Output 2

Sample Input 3

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

Sample Output 3

7362669937