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

A - Double Click

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

配点 : 100 点

問題文

高橋君は、時刻 0 にパソコンの電源をつけ、それからマウスを N 回クリックしました。i(1 \le i \le N) 回目のクリックは時刻 T_i に行われました。

高橋君が時刻 x_1 と時刻 x_2 (ただし x_1 < x_2)にマウスを連続してクリックしたとき、x_2 - x_1 \le D であれば時刻 x_2 にダブルクリックが成立したと言います。

高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が 1 回もダブルクリックを成立させていないならば -1 を出力してください。

制約

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
入力はすべて整数

入力

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

N D
T_1 T_2 \dots T_N

出力

高橋君が 1 回でもダブルクリックを成立させたならば最初にダブルクリックが成立した時刻を、そうでないならば -1 を出力せよ。

入力例 1

4 500
300 900 1300 1700

出力例 1

高橋君は時刻 900,1300 にマウスをクリックしていて、1300 - 900 \le 500 であるため時刻 1300 にダブルクリックが成立しています。

時刻 1300 より前にダブルクリックは成立していないため、1300 を出力してください。

入力例 2

5 99
100 200 300 400 500

出力例 2

-1

高橋君は 1 回もダブルクリックを成立させていません。よって、-1 を出力してください。

入力例 3

4 500
100 600 1100 1600

出力例 3

高橋君が複数回ダブルクリックを成立させていても、そのうち最初の時刻のみを出力することに注意してください。

Score : 100 points

Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
All values in the input are integers.

Input

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

N D
T_1 T_2 \dots T_N

Output

If at least one double click was fired, print the time of the first such event; otherwise, print -1.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

If multiple double clicks were fired, be sure to print only the first such event.

B - 123233

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

配点 : 100 点

問題文

6 桁の正整数 N が与えられます。
この整数が以下の条件を全て満たすか判定してください。

N の各桁のうち、 1 は丁度 1 つである。
N の各桁のうち、 2 は丁度 2 つである。
N の各桁のうち、 3 は丁度 3 つである。

制約

N は 100000 \le N \le 999999 を満たす整数

入力

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

出力

N が問題文中の条件を全て満たすなら Yes 、そうでないなら No と 1 行に出力せよ。

入力例 1

出力例 1

Yes

123233 は問題文中の条件を満たすので、 Yes と出力します。

入力例 2

出力例 2

No

123234 は問題文中の条件を満たさないので、 No と出力します。

入力例 3

出力例 3

Yes

入力例 4

出力例 4

No

Score : 100 points

Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

Among the digits of N, the digit 1 appears exactly once.
Among the digits of N, the digit 2 appears exactly twice.
Among the digits of N, the digit 3 appears exactly three times.

Constraints

N is an integer satisfying 100000 \le N \le 999999.

Input

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

Output

Print Yes if N satisfies all the conditions described in the problem statement, and No otherwise, in one line.

Sample Input 1

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.

Sample Input 2

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.

Sample Input 3

Sample Output 3

Yes

Sample Input 4

Sample Output 4

No

C - 1D Akari

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

配点 : 250 点

問題文

. および # からなる文字列 S が与えられます。

以下の条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ求めてください。

T の長さは S の長さと等しい。
T は .、#、o からなる。
S_i= # であるとき、またそのときに限り T_i= # である。
T_i=T_j= o (i < j) ならば、 T_{i+1},\ldots,T_{j-1} の中に # が 1 つ以上存在する。

制約

S は . および # からなる長さ 1 以上 100 以下の文字列

入力

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

出力

条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ出力せよ。

そのような文字列が複数ある場合、どれを出力しても正答となる。

入力例 1

#..#.

出力例 1

#o.#o

T= #o.#o とすると全ての条件を満たすことが確認できます。

全ての条件を満たす T であって、 o の文字数が 2 より多い文字列は存在しないので #o.#o を出力すると正答となります。

この他にも #.o#o を出力しても正答となります。

入力例 2

出力例 2

入力例 3

.....

出力例 3

..o..

この他にも o....、.o...、...o.、....o を出力しても正答となります。

入力例 4

...#..#.##.#.

出力例 4

o..#.o#o##o#o

Score : 250 points

Problem Statement

You are given a string S consisting of . and #.

Among all strings T that satisfy all of the following conditions, find one with the maximum number of os.

The length of T is equal to the length of S.
T consists of ., #, or o.
T_i= # if and only if S_i= #.
If T_i=T_j= o (i < j), then there exists at least one # among T_{i+1},\ldots,T_{j-1}.

Constraints

S is a string consisting of . and # with length between 1 and 100, inclusive.

Input

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

Output

Output one string with the maximum number of os among all strings T that satisfy all conditions.

If there are multiple such strings, printing any of them will be considered correct.

Sample Input 1

#..#.

Sample Output 1

#o.#o

Setting T= #o.#o satisfies all conditions.

There is no string T that satisfies all conditions and has more than two os, so outputting #o.#o is correct.

Outputting #.o#o is also correct.

Sample Input 2

Sample Output 2

Sample Input 3

.....

Sample Output 3

..o..

Outputting o...., .o..., ...o., or ....o is also correct.

Sample Input 4

...#..#.##.#.

Sample Output 4

o..#.o#o##o#o

D - レ

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

配点 : 200 点

問題文

高橋君は漢文の勉強をしていて、漢字を読む順番が分からず困っています。高橋君を助けましょう！

1 から N までの N 個の整数が小さい方から順に 1 列に並んでいます。
整数の間に M 個の「レ」が挟まっています。i 個目の「レ」は、整数 a_i と整数 a_i + 1 の間にあります。

あなたは次の手順に従って、N 個の整数を 1 回ずつ全て読みます。

まず、頂点に 1 から N までの番号がついた N 頂点 M 辺の無向グラフ G を考える。i 本目の辺は頂点 a_i と頂点 a_i + 1 を結んでいる。
そして、読まれていない整数が無くなるまで次の操作を繰り返す。
- 読まれていない整数のうち最小のものを x とする。頂点 x が含まれる連結成分 C を選び、C に含まれる頂点の番号を大きい方から順に全て読む。

例えば、整数と「レ」が

という順番で並んでいる場合を考えます。(この場合 N = 5, M = 3, a = (1, 3, 4) です。)
このとき、整数が読まれる順番は以下の手順によって 2, 1, 5, 4, 3 に決定します。

最初、読まれていない整数のうち最小のものは 1 であり、グラフ G の頂点 1 を含む連結成分に含まれる頂点は \lbrace 1, 2 \rbrace である。よって 2, 1 がこの順で読まれる。
次に、読まれていない整数のうち最小のものは 3 であり、グラフ G の頂点 3 を含む連結成分に含まれる頂点は \lbrace 3, 4, 5 \rbrace である。よって 5, 4, 3 がこの順で読まれる。
すべての整数が読まれたので手順を終了する。

N, M, (a_1, a_2, \dots, a_M) が入力として与えられるので、 N 個の整数を読む順番を出力してください。

連結成分とは

あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが連結であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

制約

1 \leq N \leq 100
0 \leq M \leq N - 1
1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
入力される値は全て整数

入力

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

N M
a_1 a_2 \dots a_M

出力

答えを以下の形式で出力せよ。ここで p_i は、i 番目に読まれる整数を意味する。

p_1 p_2 \dots p_N

入力例 1

5 3
1 3 4

出力例 1

2 1 5 4 3

問題文の例にある通り、整数と「レ」が

という順で並んでいる場合は 2, 1, 5, 4, 3 の順で読みます。

入力例 2

5 0

出力例 2

1 2 3 4 5

「レ」が存在しない場合もあります。

入力例 3

10 6
1 2 3 7 8 9

出力例 3

4 3 2 1 5 6 10 9 8 7

Score : 200 points

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).

You read each of the N integers once by the following procedure.

Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
Repeat the following operation until there is no unread integer:
- let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:

At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
Now that all integers are read, terminate the procedure.

Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.

What is a connected component?

A subgraph of a graph is a graph obtained by choosing some vertices and edges from the original graph.
A graph is said to be connected if and only if one can travel between any two vertices in the graph via edges.
A connected component is a connected subgraph that is not contained in any larger connected subgraph.

Constraints

1 \leq N \leq 100
0 \leq M \leq N - 1
1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
All values in the input are integers.

Input

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

N M
a_1 a_2 \dots a_M

Output

Print the answer in the following format, where p_i is the i-th integers to read.

p_1 p_2 \dots p_N

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: 2, 1, 5, 4, and 3.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

E - Security 2

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

配点 : 300 点

問題文

AtCoder 社の入口には特殊なパスコード入力装置があり、この装置は文字列を 1 つ表示する画面と 2 つのボタンからなります。

画面に表示される文字列を t とします。 t ははじめ空文字列であり、ボタンを押すことで t に以下の変化が起きます。

ボタン A を押すと、t の末尾に 0 が追加される。
ボタン B を押すと、t に含まれるすべての数字が、それぞれ次の数字に置き換わる。ここで、0 から 8 までの数字については次の数字は 1 大きな数を表す数字とし、9 の次の数字は 0 とする。

たとえば、t が 1984 のときにボタン A を押すと t は 19840 に変化し、さらにボタン B を押すと t は 20951 に変化します。

文字列 S が与えられます。t が空文字列である状態からボタンを 0 回以上押して t を S に一致させるとき、ボタンを最少で何回押す必要があるかを求めてください。

制約

S は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 からなる文字列
1 \leq |S| \leq 5 \times 10^5 (|S| は S の長さをあらわす)

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

以下の順にボタンを押せば、t が 21 になります。

ボタン A を押す。t は 0 になる。
ボタン B を押す。t は 1 になる。
ボタン A を押す。t は 10 になる。
ボタン B を押す。t は 21 になる。

4 回より少ない回数ボタンを押して t を 21 にすることはできないので、4 を出力します。

入力例 2

出力例 2

入力例 3

2025524202552420255242025524

出力例 3

Score : 300 points

Problem Statement

At the entrance of AtCoder Inc., there is a special pass-code input device. The device consists of a screen displaying one string, and two buttons.

Let t be the string shown on the screen. Initially, t is the empty string. Pressing a button changes t as follows:

Pressing button A appends 0 to the end of t.
Pressing button B replaces every digit in t with the next digit: for digits 0 through 8 the next digit is the one whose value is larger by 1; the next digit after 9 is 0.

For example, if t is 1984 and button A is pressed, t becomes 19840; if button B is then pressed, t becomes 20951.

You are given a string S. Starting from the empty string, press the buttons zero or more times until t coincides with S. Find the minimum number of button presses required.

Constraints

S is a string consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
1 \le |S| \le 5 \times 10^{5}, where |S| is the length of S.

Input

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

Output

Output the answer.

Sample Input 1

Sample Output 1

The following sequence of presses makes t equal to 21.

Press button A. t becomes 0.
Press button B. t becomes 1.
Press button A. t becomes 10.
Press button B. t becomes 21.

It is impossible to obtain 21 with fewer than four presses, so output 4.

Sample Input 2

Sample Output 2

Sample Input 3

2025524202552420255242025524