AtCoder Daily Training MEDIUM 2025/01/15 20:00start

C - 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

D - Postal Card

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

数字のみからなる長さ 6 の文字列が N 個与えられます。i \, (i = 1, 2, \dots, N) 番目のものを S_i と表します。

さらに、数字のみからなる長さ 3 の文字列が M 個与えられます。j \, (j = 1, 2, \dots, M) 番目のものを T_j と表します。

S_1, S_2, \dots, S_N のうち、末尾 3 文字が T_1, T_2, \dots, T_M のいずれかに一致するものの個数を求めてください。

制約

1 \leq N, M \leq 1000
N, M は整数
全ての i = 1, 2, \dots, N に対し、S_i は数字のみからなる長さ 6 の文字列
全ての j = 1, 2, \dots, M に対し、T_j は数字のみからなる長さ 3 の文字列

入力

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

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

出力

答えを出力せよ。

入力例 1

出力例 1

S_1 の末尾 3 文字は 857 であり、これは T_3 に一致します。
S_2 の末尾 3 文字は 159 であり、これは T_1 に一致します。
S_3 の末尾 3 文字は 028 であり、これは T_1, T_2, T_3 のいずれにも一致しません。

以上から、答えは 2 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

1 \leq N, M \leq 1000
N and M are integers.
S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Input

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

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

Output

Print the answer.

Sample Input 1

Sample Output 1

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

E - Doukasen

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが A_i cm で、 1 秒あたり B_i cm の一定の速さで燃えます。

この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。

制約

1 \leq N \leq 10^5
1 \leq A_i,B_i \leq 1000
入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か（単位を除いて）出力せよ。

想定解答との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。

入力例 1

出力例 1

3.000000000000000

着火前の導火線の左端から 3 cm の地点で 2 つの火がぶつかります。

入力例 2

出力例 2

3.833333333333333

入力例 3

出力例 3

8.916666666666668

Score : 300 points

Problem Statement

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

1 \leq N \leq 10^5
1 \leq A_i,B_i \leq 1000
All values in input are integers.

Input

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 distance between the position where the two flames will meet and the left end of the object, in centimeters (print just the number).

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-5}.

Sample Input 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

Sample Output 2

3.833333333333333

Sample Input 3

Sample Output 3

8.916666666666668

F - Belt Conveyor

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
(i,j) には文字 G_{i,j} が書きこまれています。ここで G_{i,j} は U, D, L, R のいずれかです。

あなたは (1,1) にいます。あなたは移動することができなくなるまで次の操作を繰り返します。

あなたは現在 (i,j) にいるとする。
G_{i,j} が U であり、かつ i \neq 1 ならば (i-1,j) へ移動する。
G_{i,j} が D であり、かつ i \neq H ならば (i+1,j) へ移動する。
G_{i,j} が L であり、かつ j \neq 1 ならば (i,j-1) へ移動する。
G_{i,j} が R であり、かつ j \neq W ならば (i,j+1) へ移動する。
それ以外の場合、あなたは移動することができない。

操作を終了した時点であなたがいるマスを出力してください。
ただし、あなたが操作を終了することなく無限に移動し続ける場合は -1 を出力してください。

制約

1 \leq H, W \leq 500
G_{i,j} は U, D, L, R のいずれかである。
H, W は整数である。

入力

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

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

出力

操作を終了した時点であなたが (i,j) にいる場合は次の形式で出力せよ。

i j

また、無限に動き続ける場合は -1 を出力せよ。

入力例 1

2 3
RDU
LRU

出力例 1

1 3

あなたは (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3) の順に動いたあとに操作を終了します。よって答えは (1, 3) です。

入力例 2

2 3
RRD
ULL

出力例 2

-1

あなたは (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots というように無限に動き続けます。この場合は -1 を出力します。

入力例 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

出力例 3

9 5

Score : 300 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
(i,j) has a character G_{i,j} written on it. G_{i,j} is U, D, L, or R.

You are initially at (1,1). You repeat the following operation until you cannot make a move.

Let (i,j) be the square you are currently at.
If G_{i,j} is U and i \neq 1, move to (i-1,j).
If G_{i,j} is D and i \neq H, move to (i+1,j).
If G_{i,j} is L and j \neq 1, move to (i,j-1).
If G_{i,j} is R and j \neq W, move to (i,j+1).
Otherwise, you cannot make a move.

Print the square you end up at when you cannot make a move.
If you indefinitely repeat moving, print -1 instead.

Constraints

1 \leq H, W \leq 500
G_{i,j} is U, D, L, or R.
H and W are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If you end up at (i, j), print it in the following format:

i j

If you indefinitely repeat moving, print -1.

Sample Input 1

2 3
RDU
LRU

Sample Output 1

1 3

You will move as (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3), ending up here, so the answer is (1, 3).

Sample Input 2

2 3
RRD
ULL

Sample Output 2

-1

You will indefinitely repeat moving as (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots, so -1 should be printed in this case.

Sample Input 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

Sample Output 3

9 5

G - Souvenirs

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

AtCoder Land のお土産屋に N 個の箱が売られています。

箱には 1, 2, \ldots, N の番号が付いており、箱 i の価格は A_i 円であり、A_i 個のお菓子が入っています。

高橋君は N 個の箱のうち M 個の箱を選んで買って帰り、1, 2, \ldots, M の名前が付いた M 人の人に 1 つずつ箱を渡そうとしています。

ただし、高橋君は以下の条件を満たすことができるように箱を買いたいです。

各 i = 1, 2, \ldots, M について、人 i には B_i 個以上のお菓子が入った箱を渡す

1 人に 2 個以上の箱を渡すことや同じ箱を複数人に渡すことはできないことに注意してください。

適切に箱を M 個買うことで条件を満たすことができるか判定し、条件を満たすことができる場合は高橋君が支払う金額の合計の最小値を求めてください。

制約

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

入力

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

出力

適切に箱を M 個買うことで条件を満たすことができる場合は高橋君が支払う金額の合計の最小値を出力せよ。そうでない場合は -1 を出力せよ。

入力例 1

4 2
3 4 5 4
1 4

出力例 1

高橋君は箱 1, 4 を買い、箱 1 を人 1、箱 4 を人 2 に渡すことで条件を満たすことができます。

このとき高橋君が支払う金額の合計は 7 円であり、支払う金額が 7 円未満のときは条件を満たすことはできないため、7 を出力します。

入力例 2

3 3
1 1 1
1000000000 1000000000 1000000000

出力例 2

-1

入力例 3

7 3
2 6 8 9 5 1 11
3 5 7

出力例 3

Score : 350 points

Problem Statement

A souvenir shop at AtCoder Land sells N boxes.

The boxes are numbered 1 to N, and box i has a price of A_i yen and contains A_i pieces of candy.

Takahashi wants to buy M out of the N boxes and give one box each to M people named 1, 2, \ldots, M.

Here, he wants to buy boxes that can satisfy the following condition:

For each i = 1, 2, \ldots, M, person i is given a box containing at least B_i pieces of candy.

Note that it is not allowed to give more than one box to a single person or to give the same box to multiple people.

Determine whether it is possible to buy M boxes that can satisfy the condition, and if it is possible, find the minimum total amount of money Takahashi needs to pay.

Constraints

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

Input

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

Output

If it is possible to buy M boxes that can satisfy the condition, print the minimum total amount of money Takahashi needs to pay. Otherwise, print -1.

Sample Input 1

4 2
3 4 5 4
1 4

Sample Output 1

Takahashi can buy boxes 1 and 4, and give box 1 to person 1 and box 4 to person 2 to satisfy the condition.

In this case, he needs to pay 7 yen in total, and it is impossible to satisfy the condition by paying less than 7 yen, so print 7.

Sample Input 2

3 3
1 1 1
1000000000 1000000000 1000000000

Sample Output 2

-1

Sample Input 3

7 3
2 6 8 9 5 1 11
3 5 7