AtCoder Daily Training MEDIUM 2023/11/21 15:30start

C - qwerty

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 以上 26 以下の整数からなる長さ 26 の数列 P=(P_1,P_2, \ldots ,P_{26}) が与えられます。ここで、P の要素は相異なることが保証されます。

以下の条件を満たす長さ 26 の文字列 S を出力してください。

任意の i\, (1 \leq i \leq 26) について、S の i 文字目は辞書順で小さい方から P_i 番目の英小文字である。

制約

1 \leq P_i \leq 26
P_i \neq P_j (i \neq j)
入力は全て整数である。

入力

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

P_1 P_2 \ldots P_{26}

出力

文字列 S を出力せよ。

入力例 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

出力例 1

abcdefghijklmnopqrstuvwxyz

入力例 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

出力例 2

bacdefghijklmnopqrstuvwxyz

入力例 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

出力例 3

eklpyqragjdwtcbxzsnifvhmou

Score : 200 points

Problem Statement

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

1 \leq P_i \leq 26
P_i \neq P_j (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

P_1 P_2 \ldots P_{26}

Output

Print the string S.

Sample Input 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou

D - Same Map in the RPG World

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。

縦 H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。
A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。

次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。

j=1, 2, \dots, W について次の操作を同時に行う。
- A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} を A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j} に同時に置き換える。
i = 1, 2, \dots, H について次の操作を同時に行う。
- A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} を A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1} に同時に置き換える。

次の条件を満たす非負整数の組 (s, t) は存在しますか？存在する場合は Yes を、存在しない場合は No を出力してください。

縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の A が B と一致する。

ここで、A と B が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して A_{i, j} = B_{i, j} が成り立つことを言います。

制約

2 \leq H, W \leq 30
A_{i,j},B_{i,j} は # または .
H, W は整数

入力

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

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

出力

条件を満たす整数の組 (s, t) が存在する場合は Yes を、存在しない場合は No を出力せよ。

入力例 1

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

出力例 1

Yes

(s, t) = (2, 1) とすると A と B を一致させることができます。
(s, t) = (2, 1) の時の操作の手順を説明します。はじめ、A は次の通りです。

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

まず、縦方向のシフトを行います。A は次のようになります。

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

次に、再び縦方向のシフトを行います。A は次のようになります。

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

最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。

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

入力例 2

3 2
##
##
#.
..
#.
#.

出力例 2

No

どのように (s, t) を選んでも A と B を一致させることはできません。

入力例 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

出力例 3

Yes

入力例 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

出力例 4

Yes

Score : 200 points

Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

For each j=1, 2, \dots, W, simultaneously do the following:
- simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
For each i = 1, 2, \dots, H, simultaneously do the following:
- simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

2 \leq H, W \leq 30
A_{i,j} is # or ., and so is B_{i,j}.
H and W are integers.

Input

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

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

Output

Print Yes if there is a conforming integer pair (s, t); print No otherwise.

Sample Input 1

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

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

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

We first apply a vertical shift to make A as follows.

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

Then we apply another vertical shift to make A as follows.

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

Finally, we apply a horizontal shift to make A as follows, which equals B.

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

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.

Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes

E - PC on the Table

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は部屋に PC を沢山置こうとしています。そこで最大何台の PC を部屋に置けるか調べるプログラムを書くことにしました。

H 個の長さ W の ., T からなる文字列 S_1,S_2,\ldots,S_H が与えられます。

高橋君は以下の操作を 0 回以上何回でも行うことができます。

1\leq i \leq H, 1 \leq j \leq W-1 を満たす整数であって、 S_i の j 番目の文字も j+1 番目の文字も T であるようなものを選ぶ。 S_i の j 番目の文字を P で置き換え、S_i の j+1 番目の文字を C で置き換える。

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を出力してください。

制約

1\leq H \leq 100
2\leq W \leq 100
H と W は整数である
S_i は ., T からなる長さ W の文字列

入力

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

H W 
S_1
S_2
\vdots
S_H

出力

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を改行区切りで出力せよ。

解が複数存在する場合、どれを出力しても正答とみなされる。

入力例 1

2 3
TTT
T.T

出力例 1

PCT
T.T

可能な操作回数の最大値は 1 です。

例えば、 (i,j)=(1,1) として操作を行うと、S_1 が PCT に変化します。

入力例 2

3 5
TTT..
.TTT.
TTTTT

出力例 2

PCT..
.PCT.
PCTPC

Score : 300 points

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

1\leq H \leq 100
2\leq W \leq 100
H and W are integers.
S_i is a string of length W consisting of . and T.

Input

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

H W 
S_1
S_2
\vdots
S_H

Output

Print a sequence of strings, S_1,S_2,\ldots,S_H, separated by newlines, possibly resulting from maximizing the number of times he performs the operation.

If multiple solutions exist, print any of them.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

F - Rotation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正整数 N,Q と、長さ N の英小文字からなる文字列 S が与えられます。

以下で説明されるクエリを Q 個処理してください。クエリは次の 2 種類のいずれかです。

1 x: 「S の末尾の文字を削除し、先頭に挿入する」という操作を x 回連続で行う。
2 x: S の x 番目の文字を出力する。

制約

2 \le N \le 5 \times 10^5
1 \le Q \le 5 \times 10^5
1 \le x \le N
|S|=N
S は英小文字からなる。
2 x の形式のクエリが 1 個以上与えられる。
N,Q,x はすべて整数。

入力

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

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

それぞれのクエリは以下の形式で与えられる。ここで、t は 1 または 2 である。

t x

出力

2 x の形式の各クエリについて、答えを一行に出力せよ。

入力例 1

出力例 1

b
a

1 個目のクエリのとき、S は abc なので 2 文字目の b を出力します。 2 個目のクエリのとき、S は abc から cab に変わります。 3 個目のクエリのとき、S は cab なので 2 文字目の a を出力します。

入力例 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

出力例 2

c
u
c
u

Score : 300 points

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
2 x: Print the x-th character of S.

Constraints

2 \le N \le 5 \times 10^5
1 \le Q \le 5 \times 10^5
1 \le x \le N
|S|=N
S consists of lowercase English letters.
At least one query in the format 2 x.
N, Q, x are all integers.

Input

Input is given from Standard Input in the following format:

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

Each query is in the following format, where t is 1 or 2:

t x

Output

For each query in the format 2 x, print the answer in a single line.

Sample Input 1

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

G - Jumping Takahashi 2

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君が住んでいる二次元平面上の街には N 個のジャンプ台があります。i 番目のジャンプ台は点 (x_i, y_i) にあり、ジャンプ台のパワーは P_i です。また高橋君のジャンプ力は S で表され、はじめ S=0 です。高橋君が訓練を 1 回行う度に S は 1 増えます。

高橋君は以下の条件を満たす場合に限り、i 番目のジャンプ台から j 番目のジャンプ台にジャンプすることができます。

P_iS\geq |x_i - x_j| +|y_i - y_j|

高橋君の目的は、適切に始点とするジャンプ台を決めることで、そのジャンプ台からどのジャンプ台にも何回かのジャンプで移動できるようにすることです。

目的を達成するためには高橋君は最低で何回訓練を行う必要があるでしょうか？

制約

2 \leq N \leq 200
-10^9 \leq x_i,y_i \leq 10^9
1 \leq P_i \leq 10^9
(x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
入力は全て整数

入力

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

N
x_1 y_1 P_1
\vdots
x_N y_N P_N

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君が 2 回訓練したとすると、 S=2 です。このとき、2 番目のジャンプ台から全てのジャンプ台に移動することができます。

例えば、4 番目のジャンプ台へは以下の方法で移動ができます。

2 番目のジャンプ台から 3 番目のジャンプ台へジャンプする。（ P_2 S = 10, |x_2-x_3| + |y_2-y_3| = 10 であり、 P_2 S \geq |x_2-x_3| + |y_2-y_3| を満たす。）
3 番目のジャンプ台から 4 番目のジャンプ台へジャンプする。（ P_3 S = 2, |x_3-x_4| + |y_3-y_4| = 1 であり、 P_3 S \geq |x_3-x_4| + |y_3-y_4| を満たす。）

入力例 2

出力例 2

Score : 400 points

Problem Statement

There are N trampolines on a two-dimensional planar town where Takahashi lives. The i-th trampoline is located at the point (x_i, y_i) and has a power of P_i. Takahashi's jumping ability is denoted by S. Initially, S=0. Every time Takahashi trains, S increases by 1.

Takahashi can jump from the i-th to the j-th trampoline if and only if:

P_iS\geq |x_i - x_j| +|y_i - y_j|.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

2 \leq N \leq 200
-10^9 \leq x_i,y_i \leq 10^9
1 \leq P_i \leq 10^9
(x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1 P_1
\vdots
x_N y_N P_N

Output

Print the answer.

Sample Input 1

Sample Output 1

If he trains twice, S=2, in which case he can reach any trampoline from the 2-nd one.

For example, he can reach the 4-th trampoline as follows.

Jump from the 2-nd to the 3-rd trampoline. (Since P_2 S = 10 and |x_2-x_3| + |y_2-y_3| = 10, it holds that P_2 S \geq |x_2-x_3| + |y_2-y_3|.)
Jump from the 3-rd to the 4-th trampoline. (Since P_3 S = 2 and |x_3-x_4| + |y_3-y_4| = 1, it holds that P_3 S \geq |x_3-x_4| + |y_3-y_4|.)

Sample Input 2