AtCoder Daily Training EASY 2026/07/27 18:00start

A - camel Case

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

配点 : 100 点

問題文

英大文字および英小文字からなる文字列 S が与えられます。
ここで、 S のうちちょうど 1 文字だけが英大文字であり、それ以外は全て英小文字です。
大文字が S の先頭から何文字目に登場するか出力してください。
ただし、S の先頭の文字を 1 文字目とします。

制約

S は英大文字および英小文字からなる長さ 2 以上 100 以下の文字列
S に大文字はちょうど 1 つ含まれる。

入力

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

出力

大文字が S の先頭から何文字目に登場するかを、整数で出力せよ。

入力例 1

aBc

出力例 1

aBc の先頭から 1 文字目は a , 2 文字目は B , 3 文字目は c であり、このうち大文字は 2 文字目です。
よって、2 を出力します。

入力例 2

xxxxxxXxxx

出力例 2

S=xxxxxxXxxx の 7 文字目に、大文字である X が登場しています。よって、7 を出力します。

入力例 3

Zz

出力例 3

Score : 100 points

Problem Statement

You are given a string S consisting of uppercase and lowercase English letters.
Here, exactly one character of S is uppercase, and the others are all lowercase.
Find the integer x such that the x-th character of S is uppercase.
Here, the initial character of S is considered the 1-st one.

Constraints

S is a string of length between 2 and 100, inclusive, consisting of uppercase and lowercase English letters.
S has exactly one uppercase letter.

Input

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

Output

Print the integer x such that the x-th character of S is uppercase.

Sample Input 1

aBc

Sample Output 1

The 1-st character of aBc is a, the 2-nd is B, and the 3-rd is c; the 2-nd character is uppercase.
Thus, 2 should be printed.

Sample Input 2

xxxxxxXxxx

Sample Output 2

An uppercase letter X occurs as the 7-th character of S=xxxxxxXxxx, so 7 should be printed.

Sample Input 3

Zz

Sample Output 3

B - Triple Four

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

配点 : 100 点

問題文

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

A の中に同じ要素が 3 つ以上連続する箇所が存在するか判定してください。

より厳密には、 1 以上 N-2 以下の整数 i であって A_i=A_{i+1}=A_{i+2} を満たすものが存在するか判定してください。

制約

3\le N\le 100
1\le A_i\le 100
入力される値は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

A の中に同じ要素が 3 つ以上連続する箇所が存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

5
1 4 4 4 2

出力例 1

Yes

A=(1,4,4,4,2) です。 4 が 3 つ連続している箇所が存在するので、 Yes を出力してください。

入力例 2

6
2 4 4 2 2 4

出力例 2

No

A=(2,4,4,2,2,4) です。同じ要素が 3 つ以上連続している箇所は存在しないので、 No を出力してください。

入力例 3

8
1 4 2 5 7 7 7 2

出力例 3

Yes

入力例 4

10
1 2 3 4 5 6 7 8 9 10

出力例 4

No

入力例 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 5

Yes

Score : 100 points

Problem Statement

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

Determine whether there is a place in A where the same element appears three or more times in a row.

More formally, determine whether there exists an integer i with 1 \le i \le N-2 such that A_i = A_{i+1} = A_{i+2}.

Constraints

3 \le N \le 100
1 \le A_i \le 100
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

If there is a place in A where the same element appears three or more times in a row, print Yes. Otherwise, print No.

Sample Input 1

5
1 4 4 4 2

Sample Output 1

Yes

We have A=(1,4,4,4,2). There is a place where 4 appears three times in a row, so print Yes.

Sample Input 2

6
2 4 4 2 2 4

Sample Output 2

No

We have A=(2,4,4,2,2,4). There is no place where the same element appears three or more times in a row, so print No.

Sample Input 3

8
1 4 2 5 7 7 7 2

Sample Output 3

Yes

Sample Input 4

10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

No

Sample Input 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

Yes

C - String Shifting

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

D - Trick Taking

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

配点 : 200 点

問題文

プレイヤー 1 、プレイヤー 2 、\ldots 、プレイヤー N と番号がつけられた N 人のプレイヤーがカードゲームで対戦します。
各プレイヤーはカードを 1 枚場に出します。

各カードは色と値の 2 つの属性を持ち、どちらの属性も正整数で表されます。
i = 1, 2, \ldots, N について、プレイヤー i が場に出したカードの色は C_i であり、値は R_i です。 R_1, R_2, \ldots, R_N はすべて異なります。

N 人のプレイヤーの中から 1 人の勝者を下記の方法で決めます。

色が T であるカードが 1 枚以上場に出された場合、色が T であるカードのうち値が最大のものを出したプレイヤーが勝者である。
色が T であるカードが場に 1 枚も出されなかった場合、プレイヤー 1 が出したカードと同じ色のカードのうち値が最大のものを出したプレイヤーが勝者である。（プレイヤー 1 自身も勝者となり得ることに注意してください。）

勝者となるプレイヤーの番号を出力してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq T \leq 10^9
1 \leq C_i \leq 10^9
1 \leq R_i \leq 10^9
i \neq j \implies R_i \neq R_j
入力はすべて整数

入力

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

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

出力

答えを出力せよ。

入力例 1

4 2
1 2 1 2
6 3 4 5

出力例 1

色が 2 であるカードが 1 枚以上場に出されています。よって、色が 2 であるカードのうち値が最大の 5 のカードを出した、プレイヤー 4 が勝者です。

入力例 2

4 2
1 3 1 4
6 3 4 5

出力例 2

色が 2 であるカードが 1 枚も場に出されていません。よって、プレイヤー 1 が出したカードの色と同じ色（すなわち色 1 ）のカードのうち値が最大の 6 のカードを出した、プレイヤー 1 が勝者です。

入力例 3

2 1000000000
1000000000 1
1 1000000000

出力例 3

Score : 200 points

Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq T \leq 10^9
1 \leq C_i \leq 10^9
1 \leq R_i \leq 10^9
i \neq j \implies R_i \neq R_j
All values in the input are integers.

Input

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

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

Output

Print the answer.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

E - Sum of Numbers Greater Than Me

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

配点 : 300 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

i=1,\ldots,N のそれぞれについて次の問題を解いてください。

問題：A の要素のうち A_i より大きな要素全ての和を求めよ。

制約

1 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^6
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

各 1\leq k\leq N について、i=k に対する問題の答えを B_k とする。B_1,\ldots,B_N をこの順に空白区切りで出力せよ。

入力例 1

5
1 4 1 4 2

出力例 1

10 0 10 0 8

i=1 のとき A_1=1 より大きな要素の和は 4+4+2=10
i=2 のとき A_2=4 より大きな要素の和は 0
i=3 のとき A_3=1 より大きな要素の和は 4+4+2=10
i=4 のとき A_4=4 より大きな要素の和は 0
i=5 のとき A_5=2 より大きな要素の和は 4+4=8

入力例 2

10
31 42 59 26 53 58 97 93 23 54

出力例 2

456 414 190 487 361 249 0 97 513 307

入力例 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

For each i=1,\ldots,N, solve the following problem.

Problem: Find the sum of all elements in A that are greater than A_i.

Constraints

1 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^6
All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

For each 1\leq k\leq N, let B_k be the answer to the problem when i=k. Print B_1,\ldots,B_N in this order, separated by spaces.

Sample Input 1

5
1 4 1 4 2

Sample Output 1

10 0 10 0 8

For i=1, the sum of elements greater than A_1=1 is 4+4+2=10.
For i=2, the sum of elements greater than A_2=4 is 0.
For i=3, the sum of elements greater than A_3=1 is 4+4+2=10.
For i=4, the sum of elements greater than A_4=4 is 0.
For i=5, the sum of elements greater than A_5=2 is 4+4=8.

Sample Input 2

10
31 42 59 26 53 58 97 93 23 54

Sample Output 2

456 414 190 487 361 249 0 97 513 307

Sample Input 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0