AtCoder Daily Training MEDIUM 2024/12/24 17:30start

Please sign in first.

C - Delimiter

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

N 個の整数 A_1,A_2,\dots,A_N が、 1 行に 1 つずつ、 N 行にわたって与えられます。但し、 N は入力では与えられません。
さらに、以下が保証されます。

A_i \neq 0 ( 1 \le i \le N-1 )
A_N = 0

A_N, A_{N-1},\dots,A_1 をこの順に出力してください。

制約

入力は全て整数
1 \le N \le 100
1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
A_N = 0

入力

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

A_1
A_2
\vdots
A_N

出力

A_N, A_{N-1},\dots,A_1 をこの順に、改行区切りで整数として出力せよ。

入力例 1

出力例 1

繰り返しになりますが、 N は入力では与えられないことに注意してください。
この入力においては N=4 で、 A=(3,2,1,0) です。

入力例 2

出力例 2

A=(0) です。

入力例 3

出力例 3

Score: 150 points

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

A_i \neq 0 ( 1 \le i \le N-1 )
A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

All input values are integers.
1 \le N \le 100
1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
A_N = 0

Input

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

A_1
A_2
\vdots
A_N

Output

Print A_N, A_{N-1}, \dots, A_1 in this order, as integers, separated by newlines.

Sample Input 1

Sample Output 1

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

Sample Output 2

A=(0).

Sample Input 3

Sample Output 3

D - Enlarged Checker Board

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

縦 A 行、横 B 列のマスからなるタイルを縦 N 行、横 N 列に並べてできた、縦 (A\times N) 行、横 (B\times N) 列のマス目 X があります。
1\leq i,j \leq N について、上から i 行目、左から j 列目のタイルをタイル (i,j) とします。

X の各マスは以下のように塗られています。

各タイルは白いタイルまたは黒いタイルである。
白いタイルのすべてのマスは白で塗られ、黒いタイルのすべてのマスは黒で塗られている。
タイル (1,1) は白いタイルである。
辺で隣接する 2 つのタイルは異なる色のタイルである。ただし、タイル (a,b) とタイル (c,d) が辺で隣接するとは、|a-c|+|b-d|=1 ( |x| を x の絶対値とする)であることを言う。

マス目 X を出力の形式に従って出力してください。

制約

1 \leq N,A,B \leq 10
入力は全て整数

入力

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

N A B

出力

次の条件をみたす (A\times N) 個の文字列 S_1,\ldots,S_{A\times N} を改行区切りで出力せよ。

S_1,\ldots,S_{A\times N} はそれぞれ長さ (B\times N) の . または # からなる文字列である。
各 i,j (1 \leq i \leq A\times N,1 \leq j \leq B\times N) に対し、マス目 X の上から i 行目かつ左から j 列目のマスが白で塗られているならば S_i の j 文字目は .であり、黒く塗られているならば # である。

入力例 1

4 3 2

出力例 1

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

入力例 2

5 1 5

出力例 2

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

入力例 3

4 4 1

出力例 3

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

入力例 4

1 4 4

出力例 4

....
....
....
....

Score : 200 points

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

Each tile is either a white tile or a black tile.
Every square in a white tile is painted white; every square in a black tile is painted black.
Tile (1,1) is a white tile.
Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

1 \leq N,A,B \leq 10
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

Print (A\times N) strings S_1,\ldots,S_{A\times N} that satisfy the following condition, with newlines in between.

Each of S_1,\ldots,S_{A\times N} is a string of length (B\times N) consisting of . and #.
For each i and j (1 \leq i \leq A\times N,1 \leq j \leq B\times N), the j-th character of S_i is . if the square at the i-th row from the top and j-th column from the left in grid X is painted white; the character is # if the square is painted black.

Sample Input 1

4 3 2

Sample Output 1

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

Sample Input 2

5 1 5

Sample Output 2

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

Sample Input 3

4 4 1

Sample Output 3

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

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

E - Count Arithmetic Subarrays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

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

1\leq l\leq r\leq N を満たす整数の組 (l,r) であって、数列 (A_l,A_{l+1},\dots,A_r) が等差数列であるようなものが何通りあるか求めてください。

なお、数列 (x_1,x_2,\dots,x_{|x|}) が等差数列であるとは、ある d が存在して x_{i+1}-x_i=d\ (1\leq i < |x|) であることをいいます。特に、長さ 1 の数列は常に等差数列です。

制約

1\leq N \leq 2\times 10^5
1\leq A_i \leq 10^9
入力は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4
3 6 9 3

出力例 1

条件を満たす整数の組 (l,r) は (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3) の 8 通りです。

実際、(l,r)=(1,3) のとき (A_l,\dots,A_r)=(3,6,9) は等差数列なので条件を満たしますが、 (l,r)=(2,4) のとき (A_l,\dots,A_r)=(6,9,3) は等差数列ではないので条件を満たしません。

入力例 2

5
1 1 1 1 1

出力例 2

すべての整数の組 (l,r)\ (1\leq l\leq r\leq 5) が条件を満たします。

入力例 3

8
87 42 64 86 72 58 44 30

出力例 3

Score : 300 points

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

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

Input

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

N
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4
3 6 9 3

Sample Output 1

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

F - Loong Tracking

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は座標平面上で龍を操作するゲームを作成しました。

龍は 1 から N までの番号がついた N 個のパーツからなり、パーツ 1 を頭と呼びます。

最初パーツ i は座標 (i,0) にあります。以下のクエリを Q 個処理してください。

1 C: 頭を方向 C に 1 移動させる。ここで、C は R, L, U, D のいずれかであり、それぞれ x 軸正方向、x 軸負方向、y 軸正方向、y 軸負方向を意味する。頭以外の全てのパーツは前のパーツに追従するように動く。すなわち、パーツ i\ \ (2\leq i \leq N) は移動前にパーツ i-1 があった座標に移動する。
2 p: パーツ p のある座標を求める。

制約

2 \leq N \leq 10^6
1 \leq Q \leq 2\times 10^5
1 種類目のクエリにおいて、C は R, L, U, D のいずれか
2 種類目のクエリにおいて、1\leq p \leq N
入力に含まれる数値は全て整数

入力

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

各クエリは以下の 2 種類のいずれかの形式である。

1 C

2 p

出力

2 種類目のクエリの回数を q として q 行出力せよ。
i 行目には、i 番目のそのようなクエリに対する答えの座標を (x,y) としたとき、x,y を空白区切りで出力せよ。

入力例 1

出力例 1

2 種類目のクエリを処理する各タイミングにおいて、パーツの位置は次のようになっています。

複数のパーツが同じ座標に存在しうることに注意してください。

Score : 300 points

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
2 p: Find the coordinates of part p.

Constraints

2 \leq N \leq 10^6
1 \leq Q \leq 2\times 10^5
For the first type of query, C is one of R, L, U, and D.
For the second type of query, 1\leq p \leq N.
All numerical input values are integers.

Input

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:

1 C

2 p

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain x and y separated by a space, where (x,y) are the answer to the i-th such query.

Sample Input 1

Sample Output 1

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

G - Synchronized Players

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 行 N 列のグリッドがあり、各マスは空きマスか障害物のあるマスのいずれかです。グリッドの上から i 行目、左から j 列目のマスを (i, j) と表記します。

また、2 人のプレイヤーがグリッド上の相異なる空きマス上におり、各マスの情報は N 個の長さ N の文字列 S_1, S_2, \ldots, S_N として以下の形式で与えられます。

S_i の j 文字目が P であるとき、(i, j) は空きマスであり、プレイヤーがいる
S_i の j 文字目が . であるとき、(i, j) は空きマスであり、プレイヤーがいない
S_i の j 文字目が # であるとき、(i, j) は障害物のあるマスである

以下の操作を繰り返し 2 人のプレイヤーを同じマスに集めるために必要な操作回数の最小値を求めてください。ただし、操作の繰り返しにより 2 人のプレイヤーを同じマスに集めることができない場合には -1 を出力してください。

上下左右のいずれかの方向を決める。そして各プレイヤーはともにその方向に隣接するマスへの移動を試みる。各プレイヤーは移動先のマスが存在し、かつ空きマスであるならば移動し、そうでないならば移動しない。

制約

N は 2 以上 60 以下の整数
S_i は長さ N の P, ., # からなる文字列
S_i の j 文字目が P であるような組 (i, j) の個数はちょうど 2 つ

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

5
....#
#..#.
.P...
..P..
....#

出力例 1

はじめに (3, 2) にいるプレイヤーをプレイヤー 1、(4, 3) にいるプレイヤーをプレイヤー 2 とします。

例えば以下のようにすることで、3 回の操作で 2 人のプレイヤーが同じマスに集まります。

左を選択する。プレイヤー 1 は (3, 1) に移動し、プレイヤー 2 は (4, 2) に移動する。
上を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 2) に移動する。
左を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 1) に移動する。

入力例 2

2
P#
#P

出力例 2

-1

入力例 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

出力例 3

Score: 400 points

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.
If the j-th character of S_i is ., then (i, j) is an empty cell without a player.
If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

N is an integer between 2 and 60, inclusive.
S_i is a string of length N consisting of P, ., and #.
There are exactly two pairs (i, j) where the j-th character of S_i is P.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).
Choose up. Player 1 does not move, and Player 2 moves to (3, 2).
Choose left. Player 1 does not move, and Player 2 moves to (3, 1).

Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........