AtCoder Daily Training MEDIUM 2024/11/07 20:30start

C - Typing

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

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S をキーボードで入力しようとしました。

高橋君は画面を見ずにキーボードだけを見てタイピングをしていました。

誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキーが壊れていたため誤って入力された文字は消去されず、実際に入力された文字列は文字列 T となりました。

また、英小文字以外のキーを誤って押してしまうことはありませんでした。

T のうち高橋君が誤って入力した文字でないものを正しく入力された文字であると定めます。

正しく入力された文字が T の何文字目であるか答えてください。

制約

S, T は長さ 1 以上 2 \times 10^5 以下の英小文字からなる文字列
T は問題文中の手続きにより得られる文字列

入力

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

S
T

出力

S の長さを |S| として、正しく入力された文字が A_1, A_2, \ldots, A_{|S|} 文字目であるとき A_1, A_2, \ldots, A_{|S|} の値をこの順に空白区切りで出力せよ。

ただし、出力は昇順になるようにせよ。すなわち、各 1 \leq i \leq |S| - 1 に対して A_i < A_{i + 1} を満たすようにせよ。

入力例 1

abc
axbxyc

出力例 1

1 3 6

高橋君のタイピングの一連の流れは以下のようになります。

a を入力する。
b を入力しようとするが、誤って x を入力してしまう。
バックスペースキーを押すが、文字の削除は行われない。
b を入力する。
c を入力しようとするが、誤って x を入力してしまう。
バックスペースキーを押すが、文字の削除は行われない。
c を入力しようとするが、誤って y を入力してしまう。
バックスペースキーを押すが、文字の削除は行われない。
c を入力する。

正しく入力された文字は 1, 3, 6 文字目です。

入力例 2

aaaa
bbbbaaaa

出力例 2

5 6 7 8

入力例 3

atcoder
atcoder

出力例 3

1 2 3 4 5 6 7

高橋君が誤った文字を入力することはありませんでした。

Score: 200 points

Problem Statement

Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.

He was typing while looking only at the keyboard, not the screen.

Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.

He did not mistakenly press any keys other than those for lowercase English letters.

The characters in T that were not mistakenly typed are called correctly typed characters.

Determine the positions in T of the correctly typed characters.

Constraints

S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
T is a string obtained by the procedure described in the problem statement.

Input

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

S
T

Output

Let |S| be the length of S. If the correctly typed characters are the A_1-th, A_2-th, \ldots, A_{|S|}-th characters of T, print the values of A_1, A_2, \ldots, A_{|S|} in this order, separated by spaces.

Ensure that the output is in ascending order. That is, A_i < A_{i + 1} should hold for each 1 \leq i \leq |S| - 1.

Sample Input 1

abc
axbxyc

Sample Output 1

1 3 6

The sequence of Takahashi's typing is as follows:

Type a.
Try to type b but mistakenly type x.
Press the backspace key, but the character is not deleted.
Type b.
Try to type c but mistakenly type x.
Press the backspace key, but the character is not deleted.
Try to type c but mistakenly type y.
Press the backspace key, but the character is not deleted.
Type c.

The correctly typed characters are the first, third, and sixth characters.

Sample Input 2

aaaa
bbbbaaaa

Sample Output 2

5 6 7 8

Sample Input 3

atcoder
atcoder

Sample Output 3

1 2 3 4 5 6 7

Takahashi did not mistakenly type any characters.

D - Triple Metre

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

配点 : 200 点

問題文

文字列 S が文字列 T の部分文字列であるとは、次の条件を満たすような整数 i, j (1 \leq i \leq j \leq |T|) が存在することを言います。

T の i 文字目から j 文字目までを順番を変えずに抜き出してできる文字列が S と一致する。

文字列 T を oxx を 10^5 個結合した文字列として定めます。
文字列 S が与えられるので、 S が T の部分文字列である場合は Yes を、そうでない場合は No を出力してください。

制約

S は o と x のみからなる文字列である。
S の長さは 1 以上 10 以下である。

入力

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

出力

S が条件を満たす場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

xoxxoxxo

出力例 1

Yes

T のはじめの方を抜き出すと oxxoxxoxxoxx... となっています。
T の 3 文字目から 10 文字目までを抜き出した文字列は S と一致するので、 S は T の部分文字列です。よって Yes を出力します。

入力例 2

xxoxxoxo

出力例 2

No

T から文字列をどのように抜き出しても S と一致しないので、S は T の部分文字列でありません。よって No を出力します。

入力例 3

ox

出力例 3

Yes

Score : 200 points

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

S is a string consisting of o and x.
The length of S is between 1 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

If S satisfies the condition, print Yes; otherwise, print No.

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

E - ABC conjecture

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

配点 : 300 点

問題文

正の整数 N が与えられます。

A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。

なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。

制約

1 \leq N \leq 10^{11}
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。

入力例 2

出力例 2

入力例 3

100000000000

出力例 3

5745290566750

Score : 300 points

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

1 \leq N \leq 10^{11}
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

Sample Output 2

Sample Input 3

100000000000

Sample Output 3

5745290566750

F - Balls and Bag Query

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

配点 : 300 点

問題文

空の袋があります。クエリが Q 個与えられるので、順番に処理してください。

クエリは次の 3 種類です。

1 x : 整数 x が書かれたボールを 1 つ袋に入れる。
2 x : 整数 x が書かれたボールを 1 つ袋の中から取り出して外に捨てる。このクエリが与えられるとき、袋の中に整数 x が書かれたボールが存在することが保証される。
3 : 袋の中にあるボールに書かれている整数の種類数を出力する。

制約

1 \leq Q \leq 2 \times 10^{5}
1 \leq x \leq 10^{6}
2 種類目のクエリが与えられるとき、袋の中に整数 x が書かれたボールが存在する。
3 種類目のクエリが 1 つ以上存在する。
入力はすべて整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

i 番目のクエリ \text{query}_i は以下の 3 つの形式のいずれかで与えられる。

1 x

2 x

出力

3 種類目のクエリが K 個あるとき、K 行出力せよ。 i 行目(1 \leq i \leq K) では、i 番目の 3 種類目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

3
2
3

はじめ、袋の中は空です。

1 番目のクエリ 1 3 で袋の中に 3 が書かれたボールが 1 つ入ります。

2 番目のクエリ 1 1 で袋の中に 1 が書かれたボールが 1 つ入ります。

3 番目のクエリ 1 4 で袋の中に 4 が書かれたボールが 1 つ入ります。

4 番目のクエリ 3 で袋の中に 1, 3, 4 の 3 種類のボールが入っているため、3 を出力します。

5 番目のクエリ 2 1 で袋の中から 1 が書かれたボールを 1 つ取り出します。

6 番目のクエリ 3 で袋の中に 3, 4 の 2 種類のボールが入っているため、2 を出力します。

7 番目のクエリ 1 5 で袋の中に 5 が書かれたボールが 1 つ入ります。

8 番目のクエリ 3 で袋の中に 3, 4, 5 の 3 種類のボールが入っているため、3 を出力します。

入力例 2

出力例 2

1
1

Score : 300 points

Problem Statement

You have an empty bag. You are given Q queries, which must be processed in order.

There are three types of queries.

1 x : Put one ball with the integer x written on it into the bag.
2 x : Remove one ball with the integer x written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer x written on it when this query is given.
3 : Print the number of different integers written on the balls in the bag.

Constraints

1 \leq Q \leq 2 \times 10^{5}
1 \leq x \leq 10^{6}
When a query of the second type is given, the bag has a ball with the integer x written on it.
There is at least one query of the third type.
All input values are integers.

Input

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The i-th query \text{query}_i is given in one of the following three formats:

1 x

2 x

Output

If there are K queries of the third type, print K lines. The i-th line (1 \leq i \leq K) should contain the answer to the i-th query of the third type.

Sample Input 1

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer 3 written on it enters the bag.

For the second query 1 1, a ball with the integer 1 written on it enters the bag.

For the third query 1 4, a ball with the integer 4 written on it enters the bag.

For the fourth query 3, the bag has balls with the integers 1, 3, 4, so print 3.

For the fifth query 2 1, a ball with the integer 1 written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers 3, 4, so print 2.

For the seventh query 1 5, a ball with the integer 5 written on it enters the bag.

For the eighth query 3, the bag has balls with the integers 3, 4, 5, so print 3.

Sample Input 2

Sample Output 2

1
1

G - Prefix K-th Max

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

配点 : 400 点

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N)、および正整数 K が与えられます。

i=K,K+1,\ldots,N について、以下を求めてください。

P の先頭 i 項のうち、K 番目に大きい値

制約

1 \leq K \leq N \leq 5 \times 10^5
(P_1,P_2,\ldots,P_N) は (1,2,\ldots,N) の並び替えによって得られる
入力はすべて整数

入力

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

N K
P_1 P_2 \ldots P_N

出力

i=K,K+1,\ldots,N についてこの順に、問題文中で問われている値を改行区切りで出力せよ。

入力例 1

3 2
1 2 3

出力例 1

1
2

P の先頭 2 項、すなわち (P_1,P_2)=(1,2) の中で K=2 番目に大きい値は 1 となります。
P の先頭 3 項、すなわち (P_1,P_2,P_3)=(1,2,3) の中で K=2 番目に大きい値は 2 となります。

入力例 2

11 5
3 7 2 5 11 6 1 9 8 10 4

出力例 2

Score : 400 points

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

The K-th greatest value among the first i terms of P.

Constraints

1 \leq K \leq N \leq 5 \times 10^5
(P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \ldots P_N

Output

For each i=K, K+1, \ldots, N, in this order, print the specified value in Problem Statement, separated by newlines.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

11 5
3 7 2 5 11 6 1 9 8 10 4

Sample Output 2