AtCoder Daily Training EASY 2026/01/07 20:00start

A - Permute to Maximize

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 以上 9 以下の数字 A,B,C が与えられます。

A,B,C を好きな順番で並べて繋げることで作れる 3 桁の整数のうち、値が最大のものを求めてください。

制約

A,B,C は 1 以上 9 以下の数字

入力

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

A B C

出力

答えを出力せよ。

入力例 1

3 2 4

出力例 1

A,B,C を好きな順番で並べて繋げることで作れる 3 桁の整数は 324, 342, 234, 243, 432, 423 の 6 通りであり、このうち値が最大のものは 432 です。

入力例 2

7 7 7

出力例 2

777 のみを作ることができます。

入力例 3

9 1 9

出力例 3

Score : 100 points

Problem Statement

You are given three digits A,B,C between 1 and 9, inclusive.

Find the maximum value among all 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them.

Constraints

A,B,C are digits between 1 and 9, inclusive.

Input

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

A B C

Output

Output the answer.

Sample Input 1

3 2 4

Sample Output 1

There are six 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them: 324, 342, 234, 243, 432, 423; the maximum value among them is 432.

Sample Input 2

7 7 7

Sample Output 2

Only 777 can be formed.

Sample Input 3

9 1 9

Sample Output 3

B - Exponential or Quadratic

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

2^n \gt n^2 ですか？

制約

n は 1 以上 10^9 以下の整数

入力

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

出力

2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。

入力例 1

出力例 1

Yes

2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。

入力例 2

出力例 2

No

n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。

入力例 3

623947744

出力例 3

Yes

Score : 100 points

Problem Statement

Does 2^n \gt n^2 hold?

Constraints

n is an integer between 1 and 10^9 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

If 2^n \gt n^2, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

C - Most Frequent Substrings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。

長さ K の文字列 t の出現回数を、以下を満たす整数 i の個数として定義します。

1 \leq i \leq N-K+1
S の i 文字目から i+K-1 文字目までからなる部分文字列が t に一致する。

長さ K の文字列に対する出現回数の最大値 x を求めてください。また、出現回数が x となるような長さ K の文字列をすべて辞書順昇順に出力してください。

制約

N, K は整数
S は英小文字からなる長さ N の文字列
1 \leq K \leq N \leq 100

入力

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

N K
S

出力

2 行出力せよ。

1 行目には、長さ K の文字列に対する出現回数の最大値 x を出力せよ。

2 行目には、出現回数が x となるような長さ K の文字列を辞書順昇順に、空白区切りで出力せよ。

入力例 1

9 3
ovowowovo

出力例 1

2
ovo owo

出現回数 2 の文字列として、以下が挙げられます。

文字列 ovo について、i=1,7 が条件を満たすことから、ovo の出現回数は 2 です。
文字列 owo について、i=3,5 が条件を満たすことから、owo の出現回数は 2 です。

出現回数が 2 よりも大きいような長さ 3 の文字列は存在しないので、求める最大値は 2 です。

一方で、出現回数が 2 よりも小さい文字列として、以下が挙げられます。

文字列 vow について、i=2 が条件を満たすことから、vow の出現回数は 1 です。
文字列 ooo について、条件を満たす i が存在しないことから、ooo の出現回数は 0 です。

入力例 2

9 1
ovowowovo

出力例 2

5
o

入力例 3

35 3
thequickbrownfoxjumpsoverthelazydog

出力例 3

2
the

Score : 200 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Define the number of occurrences of a string t of length K as the number of integers i that satisfy the following condition:

1 \leq i \leq N-K+1
The substring of S from the i-th character to the (i+K-1)-th character matches t.

Find the maximum value x of the number of occurrences of a string of length K. Also, output all strings of length K with x occurrences in ascending lexicographical order.

Constraints

N, K are integers.
S is a string of length N consisting of lowercase English letters.
1 \leq K \leq N \leq 100

Input

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

N K
S

Output

Output two lines.

The first line should contain the maximum value x of the number of occurrences of a string of length K.

The second line should contain all strings of length K with x occurrences in ascending lexicographical order, separated by spaces.

Sample Input 1

9 3
ovowowovo

Sample Output 1

2
ovo owo

The following strings have two occurrences:

For the string ovo, i=1,7 satisfy the condition, so the number of occurrences of ovo is 2.
For the string owo, i=3,5 satisfy the condition, so the number of occurrences of owo is 2.

There is no string of length 3 with more than two occurrences, so the maximum value is 2.

On the other hand, the following are examples of strings with fewer than two occurrences:

For the string vow, i=2 satisfies the condition, so the number of occurrences of vow is 1.
For the string ooo, there is no i that satisfies the condition, so the number of occurrences of ooo is 0.

Sample Input 2

9 1
ovowowovo

Sample Output 2

5
o

Sample Input 3

35 3
thequickbrownfoxjumpsoverthelazydog

Sample Output 3

2
the

D - 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

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.