AtCoder Daily Training MEDIUM 2024/04/03 20:00start

C - Append

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

配点 : 200 点

問題文

空の数列 A があります。クエリが Q 個与えられるので、与えられた順に処理してください。
クエリは次の 2 種類のいずれかです。

1 x: A の末尾に x を追加する。
2 k: A の後ろから k 番目の値を求める。このクエリが与えられるとき、A の長さは k 以上であることが保証される。

制約

1 \leq Q \leq 100
1 種類目のクエリにおいて x は 1 \leq x \leq 10^9 を満たす整数
2 種類目のクエリにおいて k はその時点の数列 A の長さ以下の正の整数

入力

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

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

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

1 x

2 k

出力

2 種類目のクエリの個数を q として q 行出力せよ。
i 行目にはそのような i 回目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

30
20

最初 A は空である。
1 番目のクエリにより A の末尾に 20 が追加され A=(20) となる。
2 番目のクエリにより A の末尾に 30 が追加され A=(20,30) となる。
3 番目のクエリの答えは A=(20,30) の後ろから 1 番目の値の 30 である。
4 番目のクエリにより A の末尾に 40 が追加され A=(20,30,40) となる。
5 番目のクエリの答えは A=(20,30,40) の後ろから 3 番目の値の 20 である。

Score: 200 points

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

1 x: Append x to the end of A.
2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

1 \leq Q \leq 100
In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
In the second type of query, k is a positive integer not greater than the current length of sequence A.

Input

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

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

Each query is in one of the following two formats:

1 x

2 k

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain the answer to the i-th such query.

Sample Input 1

Sample Output 1

30
20

Initially, A is empty.
The first query appends 20 to the end of A, making A=(20).
The second query appends 30 to the end of A, making A=(20,30).
The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
The fourth query appends 40 to the end of A, making A=(20,30,40).
The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

D - typo

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

配点 : 200 点

問題文

文字列 S, T が与えられます。以下の操作を高々 1 回行うことで、S を T と一致させることができるかを判定してください。

S の隣り合う 2 文字を選び、入れ替える。

なお、上記の操作を一度も行わないことも可能です。

制約

S, T はそれぞれ英小文字のみからなる、長さ 2 以上 100 以下の文字列
S の長さと T の長さは等しい

入力

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

S
T

出力

問題文中の操作を高々 1 回行うことで S を T と一致させることができるなら Yes を、できないなら No を出力せよ。

入力例 1

abc
acb

出力例 1

Yes

S の 2 文字目と 3 文字目を入れ替えることで、S を T と一致させることができます。

入力例 2

aabb
bbaa

出力例 2

No

どのように操作を行っても、S を T と一致させることはできません。

入力例 3

abcde
abcde

出力例 3

Yes

S と T は既に一致しています。

Score : 200 points

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
S and T have the same length.

Input

Input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S and T equal by doing the operation in Problem Statement at most once, print Yes; otherwise, print No.

Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.

Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.

Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

E - Min Max Pair

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

配点 : 300 点

問題文

1 以上 N 以下の整数からなる長さ N の数列 a = (a_1, \dots, a_N) が与えられます。

以下の条件を全て満たす整数 i, j の組の総数を求めてください。

1 \leq i \lt j \leq N
\min(a_i, a_j) = i
\max(a_i, a_j) = j

制約

2 \leq N \leq 5 \times 10^5
1 \leq a_i \leq N \, (1 \leq i \leq N)
入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

4
1 3 2 4

出力例 1

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

入力例 2

10
5 8 2 2 1 6 7 2 9 10

出力例 2

Score : 300 points

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

1 \leq i \lt j \leq N
\min(a_i, a_j) = i
\max(a_i, a_j) = j

Constraints

2 \leq N \leq 5 \times 10^5
1 \leq a_i \leq N \, (1 \leq i \leq N)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

4
1 3 2 4

Sample Output 1

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

F - PC on the Table

実行時間制限: 2 sec / メモリ制限: 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

G - Union of Interval

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

配点 : 400 点

問題文

実数 L,R に対して、L 以上 R 未満からなる実数の集合を [L,R) と表します。このような形で表される集合を右半開区間といいます。

N 個の右半開区間 [L_i,R_i) が与えられます。これらの和集合を S とします。S を最小の個数の右半開区間の和集合として表してください。

制約

1 \leq N \leq 2\times 10^5
1 \leq L_i \lt R_i \leq 2\times 10^5
入力に含まれる値は全て整数である

入力

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

N
L_1 R_1
\vdots
L_N R_N

出力

S が最小で k 個の右半開区間の和集合で表せるとする。そのような k 個の右半開区間 [X_i,Y_i) を X_i の昇順で以下のように k 行出力せよ。

X_1 Y_1
\vdots
X_k Y_k

入力例 1

出力例 1

10 30
40 50

3 つの右半開区間 [10,20),[20,30),[40,50) の和集合は 2 つの右半開区間 [10,30),[40,50) の和集合と等しくなります。

入力例 2

出力例 2

10 60

3 つの右半開区間 [10,40),[30,60),[20,50) の和集合は 1 つの右半開区間 [10,60) と等しくなります。

Score : 400 points

Problem Statement

For real numbers L and R, let us denote by [L,R) the set of real numbers greater than or equal to L and less than R. Such a set is called a right half-open interval.

You are given N right half-open intervals [L_i,R_i). Let S be their union. Represent S as a union of the minimum number of right half-open intervals.

Constraints

1 \leq N \leq 2\times 10^5
1 \leq L_i \lt R_i \leq 2\times 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 R_1
\vdots
L_N R_N

Output

Let k be the minimum number of right half-open intervals needed to represent S as their union. Print k lines containing such k right half-open intervals [X_i,Y_i) in ascending order of X_i, as follows:

X_1 Y_1
\vdots
X_k Y_k

Sample Input 1

Sample Output 1

10 30
40 50

The union of the three right half-open intervals [10,20),[20,30),[40,50) equals the union of two right half-open intervals [10,30),[40,50).

Sample Input 2

Sample Output 2

10 60

The union of the three right half-open intervals [10,40),[30,60),[20,50) equals the union of one right half-open interval [10,60).