AtCoder Daily Training MEDIUM 2024/1/4 18:30start

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

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 行 N 列のマス目が与えられます。上から i 行目、左から j 列目のマスには整数 A_{i,j} が書かれています。ここで、A_{i,j} は 0 か 1 であることが保証されます。

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目を出力してください。

ただし外側のマスとは、1 行目、N 行目、1 列目、N 列目のいずれか 1 つ以上に属するマスの集合のことを指します。

制約

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
入力は全て整数

入力

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

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

出力

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目において、上から i 行目、左から j 列目のマスに書かれている整数を B_{i,j} と置く。このとき、以下の形式で出力せよ。

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

入力例 1

出力例 1

上から i 行目、左から j 列目のマスを (i,j) と呼ぶこととします。

外側のマスは (1,1) から時計回りに列挙すると (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1),(2,1) の 12 個です。

これらのマスに書かれている整数を、時計回りに 1 個ずつ動かすと出力欄のようになります。

入力例 2

2
11
11

出力例 2

11
11

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
All input values are integers.

Input

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

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

Output

Let B_{i,j} be the integer written on the square at the i-th row from the top and j-th column from the left in the grid resulting from shifting the outer squares clockwise by one square each. Print them in the following format:

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Sample Input 1

Sample Output 1

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

Sample Output 3

E - RANDOM

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。

S の列を並べ替えて T と等しくできるか判定してください。

但し、図形 X の列を並べ替えるとは、以下の操作を言います。

(1,2,\dots,W) の順列 P=(P_1,P_2,\dots,P_W) をひとつ選択する。
その後、全ての 1 \le i \le H を満たす整数 i について、以下の操作を同時に行う。
- 1 \le j \le W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j 列にある要素に置き換える。

制約

H,W は整数
1 \le H,W
1 \le H \times W \le 4 \times 10^5
S_i,T_i は # と . からなる長さ W の文字列

入力

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

出力

S を T と等しくできるなら Yes 、そうでないなら No と出力せよ。

入力例 1

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

出力例 1

Yes

例えば S の 3,4,2,1 列目をこの順に左から並べ替えた場合、 S を T と等しくできます。

入力例 2

3 3
#.#
.#.
#.#
##.
##.
.#.

出力例 2

No

この入力では、 S を T と等しくすることができません。

入力例 3

2 1
#
.
#
.

出力例 3

Yes

S=T である場合もあります。

入力例 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

出力例 4

Yes

Score : 300 points

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
- For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

H and W are integers.
1 \le H,W
1 \le H \times W \le 4 \times 10^5
S_i and T_i are strings of length W consisting of # and ..

Input

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

Output

If S can be made equal to T, print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes

F - Graph Isomorphism

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君と青木君は、それぞれ N 個のボールに M 本のひもを取り付けたおもちゃを持っています。

高橋君のおもちゃにおいて、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール A_i とボール B_i を結んでいます。

青木君のおもちゃにおいても同様に、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール C_i とボール D_i を結んでいます。

それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2 つのボールを 2 本以上の異なるひもが結んでいることはありません。

すぬけ君は、2 人のおもちゃが同じ形であるかどうか気になっています。
ここで、2 人のおもちゃが同じ形であるとは、以下の条件を満たす数列 P が存在することをいいます。

P は (1, \dots, N) を並べ替えて得られる。
任意の 1 以上 N 以下の整数 i, j に対し、以下が成り立つ。
- 高橋君のおもちゃにおいてボール i, j がひもで繋がれていることと、青木君のおもちゃにおいてボール P_i, P_j がひもで繋がれていることは同値である。

2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力してください。

制約

1 \leq N \leq 8
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
(A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
(C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
入力は全て整数である。

入力

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

N M
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_M D_M

出力

2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力せよ。

入力例 1

出力例 1

Yes

高橋君のおもちゃは下図の左側のような形をしており、青木君のおもちゃは下図の右側のような形をしています。

yes1

次の図から、2 人のおもちゃが同じ形であることがわかります。例えば P = (3, 2, 1, 4) とすると問題文中の条件を満たします。

yes2

入力例 2

出力例 2

No

2 人のおもちゃは同じ形ではありません。

入力例 3

8 0

出力例 3

Yes

Score : 300 points

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

P is a permutation of (1, \dots, N).
For every pair of integers i, j between 1 and N (inclusive), the following holds.
- Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

1 \leq N \leq 8
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
(A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
(C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_M D_M

Output

If the two toys have the same shape, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

yes1

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

yes2

Sample Input 2

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

G - Online games

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

あるオンラインゲームがあり、 N 人のプレイヤーが登録しています。
サービス開始日から 10^{100} 日を迎えた今日、開発者である高橋君がログイン履歴を調べたところ、 i 番目のプレイヤーはサービス開始日を 1 日目として、 A_i 日目から B_i 日間連続でログインし、それ以外の日はログインしていなかったことが判明しました。すなわち、i 番目のプレイヤーはサービス開始日から、A_i , A_i+1 , \ldots , A_i+B_i-1 日目に、かつそれらの日にのみログインしていたことが分かりました。
1\leq k\leq N をみたす各整数 k について、サービス開始日から今日までの間で、ちょうど k 人がログインしていた日数を答えてください。

制約

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

入力

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

N
A_1 B_1
A_2 B_2
:
A_N B_N

出力

次のように空白区切りで N 個の整数を出力せよ。

D_1 D_2 \cdots D_N

ただし、 D_i はちょうど i 人がゲームにログインしていた日数を表す。

入力例 1

出力例 1

2 2 0

1 番目のプレイヤーは 1 日目と 2 日目に、 2 番目のプレイヤーは 2 日目と 3 日目と 4 日目に、 3 番目のプレイヤーは 3 日目だけにログインしています。よって、1, 4 日目には 1 人が、2, 3 日目には 2 人がログインしており、それ以外の日は誰もログインしていない事が分かります。答えはちょうど 1 人がログインした日数が 2 日、ちょうど 2 人がログインした日数が 2 日、ちょうど 3 人がログインした日数が 0 日となります。

入力例 2

2
1000000000 1000000000
1000000000 1000000000

出力例 2

0 1000000000

2 人以上のプレイヤーがちょうど同じ期間にログインしていることもあり得ます。

Score : 400 points

Problem Statement

There is an online game with N registered players.
Today, which is the 10^{100}-th day since its launch, the developer Takahashi examined the users' login history. It turned out that the i-th player logged in for B_i consecutive days from Day A_i, where Day 1 is the launch day, and did not log in for the other days. In other words, the i-th player logged in on Day A_i, A_i+1, \ldots, A_i+B_i-1, and only on those days.
For each integer k such that 1\leq k\leq N, find the number of days on which exactly k players logged in.

Constraints

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

Output

Print N integers with spaces in between, as follows:

D_1 D_2 \cdots D_N

Here, D_i denotes the number of days on which exactly k players logged in.

Sample Input 1

Sample Output 1

2 2 0

The first player logged in on Day 1, 2, the second player logged in on Day 2, 3, 4, and the third player logged in on Day 3 only.

Thus, we can see that Day 1, 4 had 1 player logged in, Day 2, 3 had 2 players logged in, and the other days had no players logged in.

The answer is: there were 2 days with exactly 1 player logged in, 2 days with exactly 2 players logged in, and 0 days with exactly 3 players logged in.

Sample Input 2

2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0 1000000000

There may be two or more players who logged in during the same period.