AtCoder Daily Training MEDIUM 2025/01/14 17:30start

C - Adjacency Matrix

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

配点 : 150 点

問題文

N 頂点の単純無向グラフ G があり、グラフの頂点には 1,2,\ldots, N の番号が付けられています。

G の隣接行列 (A_{i,j}) が与えられます。すなわち、G は A_{i,j} = 1 であるとき、またそのときに限り頂点 i と頂点 j を結ぶ辺を持ちます。

i = 1, 2, \ldots, N について、頂点 i と直接結ばれている頂点の番号を昇順に出力してください。

ただし、頂点 i と頂点 j が直接結ばれているとは、頂点 i と頂点 j を結ぶ辺が存在することをいいます。

制約

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
入力される値はすべて整数

入力

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

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

出力

N 行出力せよ。 i 行目には頂点 i と直接結ばれている頂点の番号を昇順に空白区切りで出力せよ。

入力例 1

出力例 1

頂点 1 と直接結ばれている頂点は頂点 2, 3 です。したがって、1 行目には 2, 3 をこの順で出力します。

同様に、2 行目には 1, 4 をこの順に、3 行目には 1 を、4 行目には 2 を出力します。

入力例 2

2
0 0
0 0

出力例 2

G に辺が存在しないこともあります。

入力例 3

出力例 3

Score: 150 points

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
All input values are integers.

Input

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

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

Output

Print N lines. The i-th line should contain the numbers of the vertices directly connected to vertex i in ascending order, separated by a space.

Sample Input 1

Sample Output 1

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

Sample Output 3

D - Decode Time Signal

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

配点 : 200 点

問題文

AtCoder Land では時報がモールス信号で行なわれます。高橋君はこのモールス信号を解読したいです。

N 個の文字列 S_1, S_2, \ldots, S_N が与えられます。S_i (1 \leq i \leq N) は . と - からなる文字列で、0 以上 9 以下のある数字に対応するモールス符号です。N 個の文字列を復号し、順に連結して 1 つの文字列として出力してください。

数字とモールス符号の対応は以下の通りです。

0 -----
1 .----
2 ..---
3 ...--
4 ....-
5 .....
6 -....
7 --...
8 ---..
9 ----.

制約

1 \leq N \leq 100
N は整数
S_i (1 \leq i \leq N) は . と - からなる文字列
S_i (1 \leq i \leq N) は 0 以上 9 以下のある数字に対応するモールス符号

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 個の文字列を復号し、順に連結して 1 つの文字列として出力してください。

入力例 1

3
...--
.....
---..

出力例 1

...-- は 3 と、..... は 5 と、---.. は 8 と復号されます。よって、358 を出力します。

入力例 2

10
-----
.----
..---
...--
....-
.....
-....
--...
---..
----.

出力例 2

0123456789

E - Snuke the Cookie Picker

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

配点 : 300 点

問題文

縦 H マス, 横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と呼びます。
はじめ、グリッド上には、ある 縦横 2 マス以上 の部分長方形の内部にあるマスにクッキーが 1 枚ずつ置かれていて、それ以外のマスにはクッキーが置かれていません。
形式的に説明すると、以下の条件を全て満たす 4 つの整数の組 (a,b,c,d) がただ 1 つ存在します。

1 \leq a \lt b \leq H
1 \leq c \lt d \leq W
グリッド上のマスのうち、a \leq i \leq b, c \leq j \leq d を満たす全てのマス (i, j) にはクッキーが 1 枚ずつ置かれていて、それ以外のマスにはクッキーが置かれていない。

ところが、すぬけ君がグリッド上のクッキーのどれか 1 枚を取って食べてしまいました。
すぬけ君がクッキーを取ったマスは、クッキーが置かれていない状態に変わります。

すぬけ君がクッキーを食べた後のグリッドの状態が入力として与えられます。
マス (i, j) の状態は文字 S_{i,j} として与えられて、# はクッキーが置かれているマスを, . はクッキーが置かれていないマスを意味します。
すぬけ君が食べたクッキーが元々置かれていたマスを答えてください。(答えは一意に定まります。)

制約

2 \leq H, W \leq 500
S_{i,j} は # または .

入力

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

H W
S_{1,1}S_{1,2}\dotsS_{1,W}
S_{2,1}S_{2,2}\dotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\dotsS_{H,W}

出力

すぬけ君が食べたクッキーが元々置かれていたマスを (i, j) とする。i, j をこの順に空白区切りで出力せよ。

入力例 1

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

出力例 1

2 4

はじめ、クッキーは (2, 3) を左上、(4, 5) を右下とする部分長方形の内部にあるマスに置かれていて、すぬけ君は (2, 4) にあるクッキーを食べたことがわかります。よって (2, 4) を出力します。

入力例 2

3 2
#.
##
##

出力例 2

1 2

はじめ、クッキーは (1, 1) を左上、(3, 2) を右下とする部分長方形の内部にあるマスに置かれていて、すぬけ君は (1, 2) にあるクッキーを食べたことがわかります。

入力例 3

6 6
..####
..##.#
..####
..####
..####
......

出力例 3

2 5

Score : 300 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

1 \leq a \lt b \leq H
1 \leq c \lt d \leq W
There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

2 \leq H, W \leq 500
S_{i,j} is # or ..

Input

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

H W
S_{1,1}S_{1,2}\dotsS_{1,W}
S_{2,1}S_{2,2}\dotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\dotsS_{H,W}

Output

Let (i, j) the square contained the cookie eaten by Snuke. Print i and j in this order, separated by a space.

Sample Input 1

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

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

F - Sum of Numbers Greater Than Me

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

配点 : 300 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

i=1,\ldots,N のそれぞれについて次の問題を解いてください。

問題：A の要素のうち A_i より大きな要素全ての和を求めよ。

制約

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

入力

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

N
A_1 \ldots A_N

出力

各 1\leq k\leq N について、i=k に対する問題の答えを B_k とする。B_1,\ldots,B_N をこの順に空白区切りで出力せよ。

入力例 1

5
1 4 1 4 2

出力例 1

10 0 10 0 8

i=1 のとき A_1=1 より大きな要素の和は 4+4+2=10
i=2 のとき A_2=4 より大きな要素の和は 0
i=3 のとき A_3=1 より大きな要素の和は 4+4+2=10
i=4 のとき A_4=4 より大きな要素の和は 0
i=5 のとき A_5=2 より大きな要素の和は 4+4=8

入力例 2

10
31 42 59 26 53 58 97 93 23 54

出力例 2

456 414 190 487 361 249 0 97 513 307

入力例 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

For each i=1,\ldots,N, solve the following problem.

Problem: Find the sum of all elements in A that are greater than A_i.

Constraints

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

Input

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

N
A_1 \ldots A_N

Output

For each 1\leq k\leq N, let B_k be the answer to the problem when i=k. Print B_1,\ldots,B_N in this order, separated by spaces.

Sample Input 1

5
1 4 1 4 2

Sample Output 1

10 0 10 0 8

For i=1, the sum of elements greater than A_1=1 is 4+4+2=10.
For i=2, the sum of elements greater than A_2=4 is 0.
For i=3, the sum of elements greater than A_3=1 is 4+4+2=10.
For i=4, the sum of elements greater than A_4=4 is 0.
For i=5, the sum of elements greater than A_5=2 is 4+4=8.

Sample Input 2

10
31 42 59 26 53 58 97 93 23 54

Sample Output 2

456 414 190 487 361 249 0 97 513 307

Sample Input 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

G - ABA

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

配点 : 400 点

問題文

英大文字からなる文字列 S が与えられます。

整数の組 (i, j, k) であって、以下の条件をともに満たすものの個数を求めてください。

1 \leq i < j < k \leq |S|
S_i, S_j, S_k をこの順に結合して得られる長さ 3 の文字列が回文となる

ただし、|S| は文字列 S の長さ、S_x は S の x 番目の文字を指します。

制約

S は長さ 1 以上 2 \times 10^5 以下の英大文字からなる文字列

入力

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

出力

答えを出力せよ。

入力例 1

ABCACC

出力例 1

(i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6) が条件を満たします。

入力例 2

OOOOOOOO

出力例 2

入力例 3

XYYXYYXYXXX

出力例 3

Score : 400 points

Problem Statement

You are given a string S consisting of uppercase English letters.

Find the number of integer triples (i, j, k) satisfying both of the following conditions:

1 \leq i < j < k \leq |S|
The length-3 string formed by concatenating S_i, S_j, and S_k in this order is a palindrome.

Here, |S| denotes the length of S, and S_x denotes the x-th character of S.

Constraints

S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of uppercase English letters.

Input

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

Output

Print the answer.

Sample Input 1

ABCACC

Sample Output 1

The triples satisfying the conditions are (i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6).

Sample Input 2

OOOOOOOO

Sample Output 2

Sample Input 3

XYYXYYXYXXX