AtCoder Daily Training HARD 2024/07/09 19:30start

E - ABC conjecture

Time Limit: 2 sec / Memory Limit: 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 - Sort

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

(1,2,\ldots,N) の並び替えである数列 A=(A_1,\ldots,A_N) が与えられます。
次の操作を 0 回以上 N-1 回以下行うことで、A を (1,2,\ldots,N) にしてください。

操作：1\leq i < j \leq N を満たす整数の組 (i,j) を自由に選ぶ。A の i 番目と j 番目の要素を入れ替える。

なお、制約の条件下で必ず A を (1,2,\ldots,N) にできることが証明できます。

制約

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) は (1,2,\ldots,N) の並び替えである
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

操作回数を K として、K+1 行出力せよ。
1 行目には K を出力せよ。
l+1 行目 (1\leq l \leq K) には l 回目の操作で選ぶ整数 i,j を空白区切りで出力せよ。
問題文中の条件を満たすどのような出力も正解とみなされる。

入力例 1

5
3 4 1 2 5

出力例 1

2
1 3
2 4

操作により数列は次のように変化します。

最初 A=(3,4,1,2,5) である。
1 回目の操作で 1 番目の要素と 3 番目の要素を入れ替える。A=(1,4,3,2,5) になる。
2 回目の操作で 2 番目の要素と 4 番目の要素を入れ替える。A=(1,2,3,4,5) になる。

この他、次のような出力でも正解とみなされます。

入力例 2

4
1 2 3 4

出力例 2

入力例 3

3
3 1 2

出力例 3

2
1 2
2 3

Score: 300 points

Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

Let K be the number of operations. Print K+1 lines.
The first line should contain K.
The (l+1)-th line (1\leq l \leq K) should contain the integers i and j chosen for the l-th operation, separated by a space.
Any output that satisfies the conditions in the problem statement will be considered correct.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

Initially, A=(3,4,1,2,5).
The first operation swaps the first and third elements, making A=(1,4,3,2,5).
The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

Sample Input 2

4
1 2 3 4

Sample Output 2

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

G - Cutting Woods

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ L メートルの直線状の木材があります。
x = 1, 2, \dots, L - 1 に対して、木材の左端から x メートルの地点には目印として線 x が引かれています。

Q 個のクエリが与えられます。 i 番目のクエリは数の組 (c_i, x_i) によって表されます。
以下の説明に従ってクエリを i の昇順に処理してください。

c_i = 1 のとき : 線 x_i がある地点で木材を 2 つに切る。
c_i = 2 のとき : 線 x_i を含む木材を選び、その長さを出力する。

ただし c_i = 1, 2 の両方に対して、線 x_i はクエリを処理する時点で切られていないことが保証されます。

制約

1 \leq L \leq 10^9
1 \leq Q \leq 2 \times 10^5
c_i = 1, 2 (1 \leq i \leq Q)
1 \leq x_i \leq L - 1 (1 \leq i \leq Q)
全ての i (1 \leq i \leq Q) に対して次が成り立つ: 1 \leq j \lt i かつ (c_j,x_j) = (1, x_i) を満たす j は存在しない。
入力は全て整数である。

入力

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

L Q
c_1 x_1
c_2 x_2
\vdots
c_Q x_Q

出力

c_i = 2 を満たすクエリの回数と等しい行数だけ出力せよ。 j 行目では j 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

出力例 1

5
3

1 番目のクエリ時点では木材は一度も切られていないので、線 2 を含む木材の長さは 5 メートルです。よって 5 を出力します。
2 番目のクエリによって、木材は 3 メートルの木材と 2 メートルの木材に分割されます。
3 番目のクエリ時点では線 2 を含む木材の長さは 3 メートルなので、3 を出力します。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 400 points

Problem Statement

We have a long piece of timber with a length of L meters.
For each x = 1, 2, \dots, L - 1, there is a mark called Mark x at x meters from the left end of the piece.

You are given Q queries, the i-th of which is represented as a pair of numbers (c_i, x_i).
Process the queries in ascending order of i as described below.

If c_i = 1: cut the piece at Mark x_i into two.
If c_i = 2: choose the piece with Mark x_i on it and print its length.

Here, for both kinds of queries c_i = 1, 2, it is guaranteed that there will have been no cut at Mark x_i when the query is to be processed.

Constraints

1 \leq L \leq 10^9
1 \leq Q \leq 2 \times 10^5
c_i = 1, 2 (1 \leq i \leq Q)
1 \leq x_i \leq L - 1 (1 \leq i \leq Q)
For every i (1 \leq i \leq Q), the following holds: there is no j such that 1 \leq j \lt i and (c_j,x_j) = (1, x_i).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L Q
c_1 x_1
c_2 x_2
\vdots
c_Q x_Q

Output

Print the number of lines equal to the number of queries c_i = 2. In the j-th line, print the response to the j-th such query.

Sample Input 1

Sample Output 1

5
3

At the time of the first query, no cut has been made, so the piece with Mark 2 has a length of 5 meters. Thus, you should print 5.
In the second query, the piece is cut into two pieces with lengths of 3 and 2 meters.
At the time of the third query, the piece with Mark 2 has a length of 3 meters, so you should print 3.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

H - Yet Another Sigma Problem

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

文字列 x,y に対して f(x,y) を以下で定義します。

x,y の最長共通接頭辞の長さを f(x,y) とする。

英小文字からなる N 個の文字列 (S_1,\ldots,S_N) が与えられます。次の式の値を求めてください。

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)

制約

2\leq N\leq 3\times 10^5
S_i は英小文字からなる文字列
1\leq |S_i|
|S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5
入力される数値は全て整数

入力

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

N 
S_1 \ldots S_N

出力

答えを出力せよ。

入力例 1

3
ab abc arc

出力例 1

f(S_1,S_2)=2
f(S_1,S_3)=1
f(S_2,S_3)=1

なので、答えは f(S_1,S_2)+f(S_1,S_3)+f(S_2,S_3) = 4 です。

入力例 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

出力例 2

Score: 500 points

Problem Statement

For strings x and y, define f(x, y) as follows:

f(x, y) is the length of the longest common prefix of x and y.

You are given N strings (S_1, \ldots, S_N) consisting of lowercase English letters. Find the value of the following expression:

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j).

Constraints

2 \leq N \leq 3\times 10^5
S_i is a string consisting of lowercase English letters.
1 \leq |S_i|
|S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5
All input numbers are integers.

Input

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

N 
S_1 \ldots S_N

Output

Print the answer.

Sample Input 1

3
ab abc arc

Sample Output 1

f(S_1,S_2)=2
f(S_1,S_3)=1
f(S_2,S_3)=1

Thus, the answer is f(S_1,S_2) + f(S_1,S_3) + f(S_2,S_3) = 4.

Sample Input 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

Sample Output 2

I - String Cards

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

カードが N 枚あり、i 番目のカードには文字列 S_i が書かれています。

この中からちょうど K 枚選び、好きな順序で繋げてできる文字列のうち辞書順最小のものを求めてください。

制約

1 \leq K \leq N \leq 50
1 \leq |S_i| \leq 50
S_i は英小文字からなる

入力

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

N K
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

4 3
ode
zaaa
r
atc

出力例 1

atcoder

カードの中に書かれている文字を、反転させたり並び替えたりすることはできません。
たとえば 1 枚目のカードに書かれている ode を、edo や deo のように使うことはできません。

入力例 2

5 2
z
z
zzz
z
zzzzzz

出力例 2

zz

S_i = S_j を満たす i,j(i\neq j) の組が存在することもあります。

Score : 500 points

Problem Statement

We have N cards. The i-th card has a string S_i written on it.

Find the lexicographically smallest string that can be obtained by choosing K of these cards and concatenating them in any order.

Constraints

1 \leq K \leq N \leq 50
1 \leq |S_i| \leq 50
S_i consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N K
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

4 3
ode
zaaa
r
atc

Sample Output 1

atcoder

Note that it is not possible to reverse or permute the string written on a card.
For example, ode written on the first card cannot be used as edo or deo.

Sample Input 2

5 2
z
z
zzz
z
zzzzzz

Sample Output 2

zz

There may be a pair i, j (i\neq j) such that S_i = S_j.