AtCoder Daily Training EASY 2024/06/05 18:00start

A - Not Overflow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 N が与えられます。 N が -2^{31} 以上かつ 2^{31} 未満ならば Yes を、そうでないならば No を出力してください。

制約

-2^{63} \leq N < 2^{63}
N は整数である。

入力

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

出力

N が -2^{31} 以上かつ 2^{31} 未満ならば Yes を、そうでないならば No を出力せよ。

入力例 1

出力例 1

Yes

10 は -2^{31} 以上かつ 2^{31} 未満であるので、Yes を出力します。

入力例 2

-9876543210

出力例 2

No

-9876543210 は -2^{31} 未満であるので、No を出力します。

入力例 3

483597848400000

出力例 3

No

483597848400000 は 2^{31} 以上であるので、No を出力します。

Score : 100 points

Problem Statement

You are given an integer N. If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.

Constraints

-2^{63} \leq N < 2^{63}
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

10 is between -2^{31} and 2^{31}-1, so Yes should be printed.

Sample Input 2

-9876543210

Sample Output 2

No

-9876543210 is less than -2^{31}, so No should be printed.

Sample Input 3

483597848400000

Sample Output 3

No

483597848400000 is greater than 2^{31}-1, so No should be printed.

B - Echo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の英小文字からなる文字列 S が与えられます。
S の i 文字目を S_i と記します。
S_1,S_1,S_2,S_2,\dots,S_N,S_N をこの順に連結した長さ 2N の文字列を出力してください。
例えば、 S が beginner のときは bbeeggiinnnneerr と出力してください。

制約

N は 1 \le N \le 50 を満たす整数
S は長さ N の英小文字からなる文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

8
beginner

出力例 1

bbeeggiinnnneerr

問題文中の例と同じです。

入力例 2

3
aaa

出力例 2

aaaaaa

Score : 100 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

N is an integer such that 1 \le N \le 50.
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa

C - Climbing Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 個の台が一列に並んでおり、左から i 番目の台の高さは H_i です。

高橋君は最初、左端の台の上に立っています。

高橋君は高い所が好きなので、次のルールで可能な限り移動を繰り返します。

いま立っているのが右端の台ではなく、かつ、右隣にある台の高さが自分がいま立っている台より高いとき、右隣の台に移動する

最終的に高橋君が立っている台の高さを求めてください。

制約

2 \leq N \leq 10^5
1 \leq H_i \leq 10^9
入力に含まれる値は全て整数である

入力

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

N
H_1 \ldots H_N

出力

答えを出力せよ。

入力例 1

5
1 5 10 4 2

出力例 1

最初、高橋君は左端にある高さ 1 の台に立っています。右隣の台の高さは 5 であり、いま立っている台より高いので、右隣の台に移動します。

移動後、高橋君は左から 2 番目にある高さ 5 の台に立っています。右隣の台の高さは 10 であり、いま立っている台より高いので、右隣の台に移動します。

移動後、高橋君は左から 3 番目にある高さ 10 の台に立っています。右隣の台の高さは 4 であり、いま立っている台より低いので、高橋君は移動をやめます。

よって、最終的に高橋君が立っている台の高さは 10 です。

入力例 2

3
100 1000 100000

出力例 2

入力例 3

4
27 1828 1828 9242

出力例 3

Score : 200 points

Problem Statement

There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.

Takahashi is initially standing on the leftmost platform.

Since he likes heights, he will repeat the following move as long as possible.

If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.

Find the height of the final platform he will stand on.

Constraints

2 \leq N \leq 10^5
1 \leq H_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
H_1 \ldots H_N

Output

Print the answer.

Sample Input 1

5
1 5 10 4 2

Sample Output 1

Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.

He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.

He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.

Thus, the height of the final platform Takahashi will stand on is 10.

Sample Input 2

3
100 1000 100000

Sample Output 2

Sample Input 3

4
27 1828 1828 9242

Sample Output 3

D - Takahashi's Secret

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君には N 人の友達がいます。N 人の友達はそれぞれ、友達 1 、友達 2 、\ldots 、友達 N というあだ名で呼ばれています。

ある日、高橋君はある恥ずかしい秘密を、友達の一人である友達 X に知られてしまいました。
i = 1, 2, \ldots, N について、友達 i が高橋君の秘密を知ったとき、友達 A_i がまだ高橋君の秘密を知らなければ、友達 i は高橋君の秘密を友達 A_i にも教えてしまいます。

高橋君の秘密は最終的に何人の友達に知られることになるでしょうか？

制約

2 \leq N \leq 10^5
1 \leq X \leq N
1 \leq A_i \leq N
A_i \neq i
入力はすべて整数

入力

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

N X
A_1 A_2 \cdots A_N

出力

答えを出力せよ。

入力例 1

4 2
3 1 1 2

出力例 1

高橋君の秘密は以下の流れで友達 1 、友達 2 、友達 3 の 3 人に知れ渡ります。

ある日、高橋君は秘密を友達 2 に知られてしまいました。
秘密を知った友達 2 は、その秘密を友達 1 に教えます。
秘密を知った友達 1 は、その秘密を友達 3 に教えます。

高橋君の秘密は最終的に 3 人の友達に知られることになるため、3 を出力します。

入力例 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

出力例 2

Score : 200 points

Problem Statement

Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.

One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.

How many of Takahashi's friends will learn the secret in the end?

Constraints

2 \leq N \leq 10^5
1 \leq X \leq N
1 \leq A_i \leq N
A_i \neq i
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

4 2
3 1 1 2

Sample Output 1

Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.

One day, Takahashi let Friend 2 learn the secret.
Friend 2 shares it with Friend 1.
Friend 1 shares it with Friend 3.

In the end, three of his friends learn the secret, so we print 3.

Sample Input 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

Sample Output 2

E - Dash

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

二次元平面の点 (0,0) に高橋君がいます。初め、高橋君の体力は H です。また、二次元平面には M 個の体力を回復するアイテムがあり、i 個目のアイテムは点 (x_i,y_i) に置いてあります。

高橋君は、これから N 回の移動をします。i 回目の移動は以下の方法で行われます。

今高橋君がいる点を (x,y) とする。体力を 1 消費し、S の i 番目の文字 S_i に応じて以下の点に移動する。
- S_i が R のとき： (x+1,y)
- S_i が L のとき： (x-1,y)
- S_i が U のとき： (x,y+1)
- S_i が D のとき： (x,y-1)
高橋君の体力が負になった場合、高橋君は倒れてしまい、移動をやめる。そうでない場合、移動した点にアイテムがあり、かつ高橋君の体力が K 未満ならば、移動した点に置かれたアイテムを消費し、高橋君の体力が K になる。

高橋君が一度も倒れることなく N 回の移動を行えるか判定してください。

制約

1\leq N,M,H,K\leq 2\times 10^5
S は R, L, U, D からなる長さ N の文字列
|x_i|,|y_i| \leq 2\times 10^5
(x_i,y_i) は互いに異なる
S 以外の入力は全て整数

入力

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

N M H K
S
x_1 y_1
\vdots
x_M y_M

出力

高橋君が一度も倒れることなく N 回の移動を行える場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

4 2 3 1
RUDL
-1 -1
1 0

出力例 1

Yes

初め高橋君の体力は 3 です。以下で移動を説明します。

1 回目の移動： S_i が R なので点 (1,0) に移動する。高橋君の体力は 2 に減る。点 (1,0) にはアイテムが置いてあるが、高橋君の体力は K=1 以上なのでアイテムは消費されない。
2 回目の移動： S_i が U なので点 (1,1) に移動する。高橋君の体力は 1 に減る。
3 回目の移動： S_i が D なので点 (1,0) に移動する。高橋君の体力は 0 に減る。点 (1,0) にはアイテムが置いてあり、体力は K=1 未満なのでアイテムを消費し、体力が 1 になる。
4 回目の移動： S_i が L なので点 (0,0) に移動する。高橋君の体力は 0 に減る。

以上より、高橋君は倒れずに 4 回の移動を行えるので、Yes を出力してください。体力は 0 になってもいいことに注意してください。

入力例 2

5 2 1 5
LDRLD
0 0
-1 -1

出力例 2

No

初め高橋君の体力は 1 です。以下で移動を説明します。

1 回目の移動： S_i が L なので点 (-1,0) に移動する。高橋君の体力は 0 に減る。
2 回目の移動： S_i が D なので点 (-1,-1) に移動する。高橋君の体力は -1 に減る。体力が -1 になってしまったので、高橋君は倒れてしまい、移動をやめる。

以上より、高橋君は倒れてしまうので、No を出力してください。

高橋君がはじめいる点 (0,0) にはアイテムが置いてありますが、移動後にアイテムは消費されるので、1 回目の移動前にアイテムを消費しないことに注意してください。

Score : 300 points

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:
- (x+1,y) if S_i is R;
- (x-1,y) if S_i is L;
- (x,y+1) if S_i is U;
- (x,y-1) if S_i is D.
If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

1\leq N,M,H,K\leq 2\times 10^5
S is a string of length N consisting of R, L, U, and D.
|x_i|,|y_i| \leq 2\times 10^5
(x_i, y_i) are pairwise distinct.
All values in the input are integers, except for S.

Input

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

N M H K
S
x_1 y_1
\vdots
x_M y_M

Output

Print Yes if he can complete the N moves without being stunned; print No otherwise.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.
2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.
3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.
4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.
2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.