AtCoder Daily Training EASY 2026/07/17 16:00start

A - Majority

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある提案に対し、N 人の人が賛成か反対かを表明しています。なお、N は奇数です。

i \, (i = 1, 2, \dots, N) 番目の人の意見は文字列 S_i で表され、S_i = For のとき賛成しており、S_i = Against のとき反対しています。

過半数の人がこの提案に賛成しているかどうかを判定してください。

制約

N は 1 以上 99 以下の奇数
全ての i = 1, 2, \dots, N に対し、S_i = For または S_i = Against

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 人のうち過半数が提案に賛成しているならば Yes、そうでなければ No と出力せよ。

入力例 1

3
For
Against
For

出力例 1

Yes

提案に賛成している人数は 2 人であり、これは半数を超えているので Yes と出力します。

入力例 2

5
Against
Against
For
Against
For

出力例 2

No

提案に賛成している人数は 2 人であり、これは半数以下なので No と出力します。

入力例 3

1
For

出力例 3

Yes

Score : 100 points

Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

N is an odd number between 1 and 99, inclusive.
S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print Yes if the majority of the N people agree with the proposal; print No otherwise.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

B - Shout Everyday

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

AtCoder 王国の住民は A 時になるとたこ焼きへの愛を叫ぶことになっています。

AtCoder 王国に住む高橋君は毎日 B 時に就寝し C 時に起床します。高橋君は、起きているときはたこ焼きへの愛を叫ぶことができ、寝ているときは叫ぶことができません。高橋君が毎日たこ焼きへの愛を叫ぶことができているか判定してください。ただし、一日は 24 時間であり、高橋君が寝ている時間は 24 時間未満であるとします。

制約

0\leq A,B,C\lt 24
A,B,C は相異なる
入力は全て整数

入力

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

A B C

出力

高橋君が毎日たこ焼きへの愛を叫ぶことができているならば Yes を、そうでないならば No を出力せよ。

入力例 1

21 8 14

出力例 1

Yes

高橋君は毎日 8 時に就寝し 14 時に起床します。21 時には起きているため、高橋君は毎日たこ焼きへの愛を叫ぶことができます。よって Yes を出力します。

入力例 2

0 21 7

出力例 2

No

高橋君は毎日 21 時に就寝し 7 時に起床します。0 時には起きていないため、高橋君は毎日たこ焼きへの愛を叫ぶことができません。よって No を出力します。

入力例 3

10 7 17

出力例 3

No

Score : 150 points

Problem Statement

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at A o'clock every day.

Takahashi, who lives in the Kingdom of AtCoder, goes to bed at B o'clock and wakes up at C o'clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

Constraints

0\leq A,B,C\lt 24
A, B, and C are pairwise different.
All input values are integers.

Input

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

A B C

Output

Print Yes if Takahashi can shout his love for takoyaki every day, and No otherwise.

Sample Input 1

21 8 14

Sample Output 1

Yes

Takahashi goes to bed at 8 o'clock and wakes up at 14 o'clock every day. He is awake at 21 o'clock, so he can shout his love for takoyaki every day. Therefore, print Yes.

Sample Input 2

0 21 7

Sample Output 2

No

Takahashi goes to bed at 21 o'clock and wakes up at 7 o'clock every day. He is not awake at 0 o'clock, so he cannot shout his love for takoyaki every day. Therefore, print No.

Sample Input 3

10 7 17

Sample Output 3

No

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 - Pepper Addiction

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君はコショウが大好きです。

M 種類のコショウがレストランに置いてあり、それぞれを種類 1,2,\dots,M と呼びます。　このレストランに種類 j ( 1 \le j \le M ) のコショウは C_j g だけあります。

高橋君はこの店で N 個の料理を注文しました。
相性の都合で i ( 1 \le i \le N ) 番目の料理には種類 A_i のコショウしかかけることができず、 i 番目の料理にかけられるコショウの量の上限は B_i g です。
また、高橋君がこれらの料理にかけられるのはレストランに置いてあるコショウのみです。つまり、種類 j のコショウを合計 C_j g を超えてかけることはできません。

高橋君は、料理にかけたコショウの量の合計を最大にするようにどの料理にどれだけのコショウをかけるかを決めます。
このとき、高橋君は合計何 g のコショウを料理にかけることができますか？

制約

入力は全て整数
1 \le N,M \le 1000
1 \le A_i \le M
1 \le B_i,C_i \le 10^6

入力

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

N M
C_1 C_2 \dots C_M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを整数として出力せよ。

入力例 1

出力例 1

この入力では 5 種類のコショウがあり、種類 1,2,3,4,5 のコショウがそれぞれ 4,4,8,3,7 g あります。
以下のようにすると料理にかけたコショウの量の合計が 15 g となり、これが達成可能な最大です。

1 番目の料理に種類 1 のコショウを 2 g かける。
2 番目の料理にはコショウをかけない。
3 番目の料理に種類 5 のコショウを 2 g かける。
4 番目の料理に種類 4 のコショウを 3 g かける。
5 番目の料理に種類 2 のコショウを 1 g かける。
6 番目の料理に種類 5 のコショウを 4 g かける。
7 番目の料理に種類 2 のコショウを 3 g かける。

入力例 2

1 1
1
1 1

出力例 2

入力例 3

15 10
7 94 100 82 63 81 75 2 76 73
10 44
5 77
10 47
7 32
2 82
5 90
3 37
6 70
6 28
3 25
2 26
10 56
1 69
5 46
7 26

出力例 3

Score : 200 points

Problem Statement

Takahashi loves pepper.

A restaurant has M types of pepper, called type 1,2,\dots,M. There are C_j grams of type j (1 \le j \le M) pepper at this restaurant.

He ordered N dishes at this restaurant.
Due to compatibility, only type A_i pepper can be sprinkled on dish i (1 \le i \le N), and the upper limit on the amount of pepper that can be sprinkled on dish i is B_i grams.
Also, he can only use the pepper available at the restaurant. That is, the total amount of type j pepper sprinkled cannot exceed C_j grams.

He decides how much pepper to sprinkle on each dish to maximize the total amount of pepper sprinkled on the dishes.
How many grams of pepper in total can he sprinkle on the dishes?

Constraints

All input values are integers.
1 \le N,M \le 1000
1 \le A_i \le M
1 \le B_i,C_i \le 10^6

Input

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

N M
C_1 C_2 \dots C_M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer as an integer.

Sample Input 1

Sample Output 1

In this input, there are five types of pepper, with 4,4,8,3,7 grams of type 1,2,3,4,5 pepper respectively.
The following gives a total of 15 grams of pepper sprinkled on the dishes, which is the maximum achievable.

Sprinkle 2 grams of type 1 pepper on dish 1.
Sprinkle no pepper on dish 2.
Sprinkle 2 grams of type 5 pepper on dish 3.
Sprinkle 3 grams of type 4 pepper on dish 4.
Sprinkle 1 gram of type 2 pepper on dish 5.
Sprinkle 4 grams of type 5 pepper on dish 6.
Sprinkle 3 grams of type 2 pepper on dish 7.

Sample Input 2

1 1
1
1 1

Sample Output 2

Sample Input 3

15 10
7 94 100 82 63 81 75 2 76 73
10 44
5 77
10 47
7 32
2 82
5 90
3 37
6 70
6 28
3 25
2 26
10 56
1 69
5 46
7 26

Sample Output 3

E - Min Difference

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

それぞれ N 個、M 個の正整数からなる 2 つの数列 A=(A_1,A_2, \ldots ,A_N) と B=(B_1, \ldots ,B_M) が与えられます。

それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差の最小値、すなわち、 \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert を求めてください。

制約

1 \leq N,M \leq 2\times 10^5
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
入力は全て整数である。

入力

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

出力

答えを出力せよ。

入力例 1

2 2
1 6
4 9

出力例 1

それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差としてあり得るのは、 \lvert 1-4\rvert=3 、 \lvert 1-9\rvert=8 、 \lvert 6-4\rvert=2 、 \lvert 6-9\rvert=3 の 4 つです。この中で最小である 2 を出力します。

入力例 2

1 1
10
10

出力例 2

入力例 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

出力例 3

Score : 300 points

Problem Statement

You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

Output

Print the answer.

Sample Input 1

2 2
1 6
4 9

Sample Output 1

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.

Sample Input 2

1 1
10
10

Sample Output 2

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24