AtCoder Daily Training EASY 2026/09/21 18:00start

A - Raise Both Hands

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君はたこ焼きを作ってすぬけ君に振る舞うことにしました。高橋君はすぬけ君に、たこ焼きを食べたいならば左手のみを挙げて、そうでないならば右手のみを挙げるよう指示しました。

すぬけ君が挙げた手の情報は整数 L, R によって与えられます。すぬけ君は L = 1 のとき、またそのときに限り左手を挙げており、R = 1 のとき、またそのときに限り右手を挙げています。すぬけ君は指示に従わず、両手を挙げることも手を挙げないこともあります。

すぬけ君が片方の手のみを挙げている場合、すぬけ君がたこ焼きを食べたいならば Yes を、そうでないならば No を出力してください。すぬけ君が両手を挙げているか、手を挙げていないときは Invalid と出力してください。

ただし、すぬけ君が片方の手のみを挙げている場合は必ず指示に従った行動を取っているものとします。

制約

L, R は 0 または 1

入力

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

L R

出力

問題文の指示に従って Yes, No, Invalid のいずれかを出力せよ。

入力例 1

1 0

出力例 1

Yes

すぬけ君はたこ焼きを食べたいので左手のみを挙げています。

入力例 2

1 1

出力例 2

Invalid

すぬけ君は両手を挙げています。

Score : 100 points

Problem Statement

Takahashi decided to make takoyaki (octopus balls) and serve it to Snuke. Takahashi instructed Snuke to raise only his left hand if he wants to eat takoyaki, and only his right hand otherwise.

You are given the information about which hand Snuke is raising as two integers L and R. He is raising his left hand if and only if L = 1, and raising his right hand if and only if R = 1. He might not follow the instructions and could raise both hands or not raise any hand at all.

If Snuke is raising only one hand, print Yes if he wants to eat takoyaki, and No if he does not. If he is raising both hands or not raising any hand, print Invalid.

Assume that if Snuke is raising only one hand, he is always following the instructions.

Constraints

Each of L and R is 0 or 1.

Input

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

L R

Output

Print Yes, No, or Invalid according to the instructions in the problem statement.

Sample Input 1

1 0

Sample Output 1

Yes

Snuke wants to eat takoyaki, so he is raising only his left hand.

Sample Input 2

1 1

Sample Output 2

Invalid

Snuke is raising both hands.

B - First ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A, B, C からなる文字列 S が与えられます。S は A, B, C を全て含むことが保証されます。

S を左から 1 文字ずつ見ていったときに、はじめて次の条件を満たした状態になるのは、左から何文字目まで見たときですか？

A, B, C が全て 1 回以上出現している。

制約

3 \leq N \leq 100
S は A, B, C からなる長さ N の文字列
S は A, B, C を全て含む

入力

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

N
S

出力

答えを出力せよ。

入力例 1

5
ACABB

出力例 1

左から 4 文字目までに A は 2 回, B は 1 回, C は 1 回出現していて、条件を満たします。
3 文字目以前では条件を満たさないので答えは 4 です。

入力例 2

4
CABC

出力例 2

左から 3 文字目までに A, B, C は 1 回ずつ出現していて、条件を満たします。

入力例 3

30
AABABBBABABBABABCABACAABCBACCA

出力例 3

Score : 100 points

Problem Statement

You are given a string S consisting of A, B, and C. S is guaranteed to contain all of A, B, and C.

If the characters of S are checked one by one from the left, how many characters will have been checked when the following condition is satisfied for the first time?

All of A, B, and C have appeared at least once.

Constraints

3 \leq N \leq 100
S is a string of length N consisting of A, B, and C.
S contains all of A, B, and C.

Input

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

N
S

Output

Print the answer.

Sample Input 1

5
ACABB

Sample Output 1

In the first four characters from the left, A, B, and C appear twice, once, and once, respectively, satisfying the condition.
The condition is not satisfied by checking three or fewer characters, so the answer is 4.

Sample Input 2

4
CABC

Sample Output 2

In the first three characters from the left, each of A, B, and C appears once, satisfying the condition.

Sample Input 3

30
AABABBBABABBABABCABACAABCBACCA

Sample Output 3

C - Unique Nicknames

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

人 1, 人 2, \dots 人 N の N 人の人がいます。人 i の姓は s_i、名は t_i です。

N 人の人すべてにあだ名をつけることを考えます。人 i のあだ名 a_i は以下の条件を満たす必要があります。

a_i は人 i の姓あるいは名と一致する。言い換えると、a_i = s_i または a_i = t_i の少なくとも一方が成り立つ。
a_i は自分以外の人の姓および名のどちらとも一致しない。言い換えると、1 \leq j \leq N, i \neq j を満たすすべての整数 j について a_i \neq s_j かつ a_i \neq t_j が成り立つ。

N 人全員に条件を満たすあだ名をつけることは可能でしょうか。可能ならば Yes を、そうでないならば No を出力してください。

制約

2 \leq N \leq 100
N は整数である。
s_i,t_i は英小文字からなる 1 文字以上 10 文字以下の文字列である。

入力

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

N
s_1 t_1
s_2 t_2
\vdots
s_N t_N

出力

N 人すべてにあだ名をつけることが可能ならば Yes を、そうでないならば No を出力せよ。

入力例 1

3
tanaka taro
tanaka jiro
suzuki hanako

出力例 1

Yes

a_1 = taro, a_2 = jiro, a_3 = hanako とすれば、これは問題文にあるあだ名の条件を満たしています。(a_3 は suzuki でもよいです。)
ここで、a_1 = tanaka とはできないことに注意してください。なぜならば人 2 の姓 s_2 もまた tanaka であるため、あだ名の条件の 2 つ目を満たさなくなるからです。

入力例 2

3
aaa bbb
xxx aaa
bbb yyy

出力例 2

No

問題文の条件を満たすあだ名のつけ方は存在しません。

入力例 3

2
tanaka taro
tanaka taro

出力例 3

No

同姓同名である人の組が存在する場合もあります。

入力例 4

3
takahashi chokudai
aoki kensho
snu ke

出力例 4

Yes

a_1 = chokudai, a_2 = kensho, a_3 = ke とすればよいです。

Score : 200 points

Problem Statement

There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.

Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.

a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.

Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.

Constraints

2 \leq N \leq 100
N is an integer.
s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.

Input

Input is given from Standard Input in the following format:

N
s_1 t_1
s_2 t_2
\vdots
s_N t_N

Output

If it is possible to give nicknames to all the N people, print Yes; otherwise, print No.

Sample Input 1

3
tanaka taro
tanaka jiro
suzuki hanako

Sample Output 1

Yes

The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.

Sample Input 2

3
aaa bbb
xxx aaa
bbb yyy

Sample Output 2

No

There is no way to give nicknames satisfying the conditions in the Problem Statement.

Sample Input 3

2
tanaka taro
tanaka taro

Sample Output 3

No

There may be a pair of people with the same family name and the same given name.

Sample Input 4

3
takahashi chokudai
aoki kensho
snu ke

Sample Output 4

Yes

We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.

D - String Shifting

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

空でない文字列に対し、先頭の文字を末尾に移動する操作を左シフト、末尾の文字を先頭に移動する操作を右シフトと呼びます。

例えば、abcde に対して左シフトを 1 回行うと bcdea となり、右シフトを 2 回行うと deabc となります。

英小文字からなる空でない文字列 S が与えられます。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものを求めてください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 S, T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

S は英小文字からなる。
S の長さは 1 以上 1000 以下である。

入力

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

出力

2 行にわたって出力せよ。S に対し左シフトと右シフトをそれぞれ好きな回数（0 回でもよい）行って得られる文字列のうち、辞書順で最小のものと最大のものをそれぞれ S_{\min}, S_{\max} とおいたとき、1 行目には S_{\min} を、2 行目には S_{\max} を出力せよ。

入力例 1

aaba

出力例 1

aaab
baaa

操作によって、aaab , aaba , abaa , baaa の 4 通りの文字列を得ることができます。これらのうち辞書順で最小、最大のものはそれぞれ aaab , baaa です。

入力例 2

出力例 2

z
z

どのように操作を行っても、得られる文字列は z のみです。

入力例 3

abracadabra

出力例 3

aabracadabr
racadabraab

Score : 200 points

Problem Statement

On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.

For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.

You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

S consists of lowercase English letters.
The length of S is between 1 and 1000 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Print two lines. The first line should contain S_{\min}, and the second line should contain S_{\max}. Here, S_{\min} and S_{\max} are respectively the lexicographically smallest and largest strings obtained by performing zero or more left shifts and zero or more right shifts on S.

Sample Input 1

aaba

Sample Output 1

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

Sample Input 2

Sample Output 2

z
z

Any sequence of operations results in z.

Sample Input 3

abracadabra

Sample Output 3

aabracadabr
racadabraab

E - Vanish

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。

以下の操作をちょうど K 回行った後の A の各要素の和として考えられる最小値を求めてください。

整数 x を選ぶ。A_i = x なる各 i について A_i の値を 0 に置き換える。

制約

1 \leq K \leq N \leq 3 \times 10^5
1 \leq A_i \leq 10^9
入力される値はすべて整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

6 2
7 2 7 2 2 9

出力例 1

はじめ、A = (7, 2, 7, 2, 2, 9) です。

x = 9 として操作を行うと、A = (7, 2, 7, 2, 2, 0) となります。

次に x = 7 として操作を行うと、A = (0, 2, 0, 2, 2, 0) となります。

このとき、A の各要素の和は 0 + 2 + 0 + 2 + 2 + 0 = 6 となります。

入力例 2

8 6
1 2 3 4 1 2 3 4

出力例 2

入力例 3

10 2
3 3 4 1 1 3 3 1 5 1

出力例 3

Score : 300 points

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N).

Find the minimum possible sum of all elements of A after performing the following operation exactly K times.

Choose an integer x. For each i such that A_i = x, replace the value of A_i with 0.

Constraints

1 \leq K \leq N \leq 3 \times 10^5
1 \leq A_i \leq 10^9
All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Output the answer.

Sample Input 1

6 2
7 2 7 2 2 9

Sample Output 1

Initially, A = (7, 2, 7, 2, 2, 9).

Performing the operation with x = 9 gives A = (7, 2, 7, 2, 2, 0).

Next, performing the operation with x = 7 gives A = (0, 2, 0, 2, 2, 0).

At this point, the sum of all elements of A is 0 + 2 + 0 + 2 + 2 + 0 = 6.

Sample Input 2

8 6
1 2 3 4 1 2 3 4

Sample Output 2

Sample Input 3

10 2
3 3 4 1 1 3 3 1 5 1