AtCoder Daily Training EASY 2026/03/12 16:00start

ログインしてください。

A - tcdr

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

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。
S から a, e, i, o, u をすべて取り除いて得られる文字列を出力してください。
なお、S は a, e, i, o, u 以外の文字を一つ以上含みます。

制約

S は英小文字からなる長さ 1 以上 100 以下の文字列
S は a, e, i, o, u 以外の文字を一つ以上含む

入力

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

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

tcdr

S = atcoder のとき、1, 4, 6 文字目を取り除いて tcdr を得ます。

入力例 2

xyz

出力例 2

xyz

入力例 3

aaaabbbbcccc

出力例 3

bbbbcccc

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.
Remove all occurrences of a, e, i, o, u from S and print the resulting string.
S contains at least one character other than a, e, i, o, u.

Constraints

S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
S contains at least one character other than a, e, i, o, u.

Input

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

Output

Print the answer.

Sample Input 1

atcoder

Sample Output 1

tcdr

For S = atcoder, remove the 1-st, 4-th, and 6-th characters to get tcdr.

Sample Input 2

xyz

Sample Output 2

xyz

Sample Input 3

aaaabbbbcccc

Sample Output 3

bbbbcccc

B - Candy Button

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

配点 : 150 点

問題文

不思議なボタンがあります。このボタンを押すと飴を 1 つもらえますが、前回飴をもらってからの経過時間が C 秒未満である場合はもらえません。

高橋君はこのボタンを N 回押してみることにしました。 i 回目にボタンを押すのは今から T_i 秒後です。

高橋君は何個の飴をもらうことができますか？

制約

1\leq N \leq 100
1\leq C\leq 1000
0\leq T_1 < T_2 < \dots < T_N \leq 1000
入力は全て整数

入力

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

N C
T_1 T_2 \dots T_N

出力

高橋君がもらうことのできる飴の個数を出力せよ。

入力例 1

6 5
1 3 7 8 10 12

出力例 1

高橋君はボタンを 6 回押します。

1 回目（今から 1 秒後）：初めてボタンを押すときは必ず飴を 1 つもらえます。
2 回目（今から 3 秒後）：前回飴をもらってからの経過時間が 3-1=2<C 秒なので、飴はもらえません。
3 回目（今から 7 秒後）：前回飴をもらってからの経過時間が 7-1=6\geq C 秒なので、飴を 1 つもらえます。
4 回目（今から 8 秒後）：前回飴をもらってからの経過時間が 8-7=1<C 秒なので、飴はもらえません。
5 回目（今から 10 秒後）：前回飴をもらってからの経過時間が 10-7=3<C 秒なので、飴はもらえません。
6 回目（今から 12 秒後）：前回飴をもらってからの経過時間が 12-7=5\geq C 秒なので、飴を 1 つもらえます。

よって、高橋君は飴を 3 個もらうことができます。

入力例 2

3 2
0 2 4

出力例 2

入力例 3

10 3
0 3 4 6 9 12 15 17 19 20

出力例 3

Score : 150 points

Problem Statement

There is a mysterious button. When you press this button, you receive one candy, unless less than C seconds have elapsed since you last received a candy.

Takahashi decided to press this button N times. He will press the button for the i-th time T_i seconds from now.

How many candies will he receive?

Constraints

1 \leq N \leq 100
1 \leq C \leq 1000
0 \leq T_1 < T_2 < \dots < T_N \leq 1000
All input values are integers.

Input

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

N C
T_1 T_2 \dots T_N

Output

Print the number of candies that Takahashi will receive.

Sample Input 1

6 5
1 3 7 8 10 12

Sample Output 1

Takahashi will press the button six times.

1st press (1 second from now): You always receive a candy when pressing the button for the first time.
2nd press (3 seconds from now): 3 - 1 = 2 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
3rd press (7 seconds from now): 7 - 1 = 6 \geq C seconds have elapsed since he last received a candy, so he receives a candy.
4th press (8 seconds from now): 8 - 7 = 1 < C second has elapsed since he last received a candy, so he does not receive a candy.
5th press (10 seconds from now): 10 - 7 = 3 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
6th press (12 seconds from now): 12 - 7 = 5 \geq C seconds have elapsed since he last received a candy, so he receives a candy.

Therefore, he receives three candies.

Sample Input 2

3 2
0 2 4

Sample Output 2

Sample Input 3

10 3
0 3 4 6 9 12 15 17 19 20

Sample Output 3

C - Daily Cookie 2

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

配点 : 200 点

問題文

A 問題と似た設定の問題です。A 問題とは、高橋君が食べるクッキーの選び方および求めるものが異なります。

N 個の箱が横一列に並んでおり、そのうちのいくつかの箱にはクッキーが入っています。

各箱の状態は長さ N の文字列 S によって表されます。具体的には、左から i\ (1\leq i\leq N) 番目の箱は、S の i 文字目が @ のときクッキーが 1 枚入っており、. のとき空き箱です。

高橋君は今からの D 日間、一日一回ずつ、その時点でクッキーが入っている箱のうち最も右にある箱のクッキーを選んで食べます。

N 個の箱それぞれについて、D 日間が経過した後にその箱にクッキーが入っているかを求めてください。

なお、S には @ が D 個以上含まれることが保証されます。

制約

1\leq D \leq N \leq 100
N,D は整数
S は @ と . からなる長さ N の文字列
S には @ が D 個以上含まれる

入力

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

N D
S

出力

長さ N の文字列を出力せよ。出力する文字列の i\ (1\leq i\leq N) 文字目は、D 日間が経過した後に左から i 番目の箱にクッキーが入っているならば @、入っていないならば . とせよ。

入力例 1

5 2
.@@.@

出力例 1

.@...

高橋君は以下のように行動します。

1 日目：左から 2,3,5 番目の箱にクッキーが入っている。このうちで最も右にある、左から 5 番目の箱に入っているクッキーを選んで食べる。
2 日目：左から 2,3 番目の箱にクッキーが入っている。このうちで最も右にある、左から 3 番目の箱に入っているクッキーを選んで食べる。
2 日間が経過した後、左から 2 番目の箱にのみクッキーが入っている。

よって、正しい出力は .@... です。

入力例 2

3 3
@@@

出力例 2

...

入力例 3

10 4
@@@.@@.@@.

出力例 3

@@@.......

Score: 200 points

Problem Statement

This problem shares a similar setting with Problem A. The way Takahashi chooses cookies and what you are required to find are different from Problem A.

There are N boxes arranged in a row, and some of these boxes contain cookies.

The state of these boxes is represented by a string S of length N. Specifically, the i-th box (1\leq i \leq N) from the left contains one cookie if the i-th character of S is @, and is empty if it is ..

Over the next D days, Takahashi will choose and eat one cookie per day from among the cookies in these boxes. On each day, he chooses the cookie in the rightmost box that contains a cookie at that point.

Determine, for each of the N boxes, whether it will contain a cookie after D days have passed.

It is guaranteed that S contains at least D occurrences of @.

Constraints

1 \leq D \leq N \leq 100
N and D are integers.
S is a string of length N consisting of @ and ..
S contains at least D occurrences of @.

Input

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

N D
S

Output

Print a string of length N. The i-th character (1 \leq i \leq N) of the string should be @ if the i-th box from the left contains a cookie after D days have passed, and . otherwise.

Sample Input 1

5 2
.@@.@

Sample Output 1

.@...

Takahashi acts as follows:

Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. Among these, the rightmost is the 5th box. He eats the cookie in this box.
Day 2: There are cookies in the 2nd and 3rd boxes. Among these, the rightmost is the 3rd box. He eats the cookie in this box.
After two days have passed, only the 2nd box from the left contains a cookie.

Therefore, the correct output is .@....

Sample Input 2

3 3
@@@

Sample Output 2

...

Sample Input 3

10 4
@@@.@@.@@.

Sample Output 3

@@@.......

D - Rectangle Detection

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

配点 : 200 点

問題文

高橋くんは、以下の方法で 10 個の文字列 S_1,S_2,\dots,S_{10} を生成しました。

まず、 S_i (1 \le i \le 10)= .......... ( . が 10 個並んだ文字列) とする。
次に、以下の条件を全て満たす 4 つの整数 A,B,C,D を選ぶ。
- 1 \le A \le B \le 10
- 1 \le C \le D \le 10
その後、以下の条件を全て満たす全ての整数組 (i,j) について、 S_i の j 文字目を # に書き換える。
- A \le i \le B
- C \le j \le D

以上の方法で生成された S_1,S_2,\dots,S_{10} が与えられるので、高橋くんが選んだ整数 A,B,C,D を求めてください。
なお、制約より A,B,C,D は一意に定まる (答えはただひとつ存在する) ことが証明できます。

制約

S_1,S_2,\dots,S_{10} は問題文中の方法で生成されうるそれぞれ長さ 10 の文字列

入力

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

S_1
S_2
\vdots
S_{10}

出力

答えを以下の形式で出力せよ。

A B
C D

入力例 1

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

出力例 1

5 8
4 9

高橋くんが選んだ整数は A=5,B=8,C=4,D=9 です。
このように選ぶことにより、 S_5,S_6,S_7,S_8 の 4 文字目から 9 文字目が # であり他の文字が . である 10 個の長さ 10 の文字列 S_1,S_2,\dots,S_{10} が生成されます。
これは入力で与えられた 10 個の文字列と一致します。

入力例 2

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

出力例 2

2 2
3 3

入力例 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

出力例 3

1 10
1 10

Score : 200 points

Problem Statement

Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.

First, let S_i (1 \le i \le 10)= .......... (10 .s in a row).
Next, choose four integers A, B, C, and D satisfying all of the following.
- 1 \le A \le B \le 10.
- 1 \le C \le D \le 10.
Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with #.
- A \le i \le B.
- C \le j \le D.

You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.

Constraints

S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.

Input

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

S_1
S_2
\vdots
S_{10}

Output

Print the answer in the following format:

A B
C D

Sample Input 1

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

Sample Output 1

5 8
4 9

Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.

Sample Input 2

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

Sample Output 2

2 2
3 3

Sample Input 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

Sample Output 3

1 10
1 10

E - Distribution

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

配点 : 300 点

問題文

N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。

i\, (1 \leq i \leq N) 番目のすぬけ君は時刻 t に宝石をもらうと S_i 単位時間後、すなわち時刻 t+S_i にその宝石を (i+1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 T_i に i 番目のすぬけ君に宝石を渡します。

全ての i\, (1 \leq i \leq N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
入力は全て整数である。

入力

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

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

出力

N 行出力せよ。i\, (1 \leq i \leq N) 行目には、i 番目のすぬけ君が初めて宝石をもらう時刻を出力すること。

入力例 1

3
4 1 5
3 10 100

出力例 1

3
7
8

時刻 13 までのすぬけ君と高橋君の行動を時系列順に並べます。

時刻 3 : 高橋君が 1 番目のすぬけ君に宝石を渡します。

時刻 7 : 1 番目のすぬけ君が 2 番目のすぬけ君に宝石を渡します。

時刻 8 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 10 : 高橋君が 2 番目のすぬけ君に宝石を渡します。

時刻 11 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 13 : 3 番目のすぬけ君が 1 番目のすぬけ君に宝石を渡します。

時刻 14 以降も彼らは宝石の受け渡しを行いますが、答えには影響しません。

入力例 2

4
100 100 100 100
1 1 1 1

出力例 2

S_i や T_i が相異なるとは限らないことに注意してください。

入力例 3

4
1 2 3 4
1 2 4 7

出力例 3

あるすぬけくんが同時刻に複数の宝石の受け渡しをする可能性があること、特に高橋くんとすぬけくんの両方から同時に宝石を貰う可能性があることに注意してください。

入力例 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

出力例 4

Score : 300 points

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the time when Snuke i receives a gem for the first time.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4