AtCoder Daily Training EASY 2024/03/27 16:00start

A - Arithmetic Progression

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

初項が A、末項が B、公差が D であるような等差数列を出力してください。

なお、そのような等差数列が存在する入力のみが与えられます。

制約

1 \leq A \leq B \leq 100
1\leq D \leq 100
初項が A、末項が B、公差が D であるような等差数列が存在する
入力は全て整数

入力

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

A B D

出力

初項が A、末項が B、公差が D であるような等差数列の項を順に空白区切りで出力せよ。

入力例 1

3 9 2

出力例 1

3 5 7 9

初項が 3、末項が 9、公差が 2 であるような等差数列は (3,5,7,9) です。

入力例 2

10 10 1

出力例 2

初項が 10、末項が 10、公差が 1 であるような等差数列は (10) です。

Score: 100 points

Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

1 \leq A \leq B \leq 100
1 \leq D \leq 100
There is an arithmetic sequence with first term A, last term B, and common difference D.
All input values are integers.

Input

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

A B D

Output

Print the terms of the arithmetic sequence with first term A, last term B, and common difference D, in order, separated by spaces.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

B - 202<s>3</s>

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字と数字からなる文字列 S が入力されます。
S は 2023 で終わることが保証されます。
S の最後の文字を 4 に変更し、変更後の文字列を出力してください。

制約

S は英小文字と数字からなる長さ 4 以上 100 以下の文字列
S は 2023 で終わる。

入力

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

出力

答えを出力せよ。

入力例 1

hello2023

出力例 1

hello2024

hello2023 の最後の文字を 4 に変更すると、 hello2024 となります。

入力例 2

worldtourfinals2023

出力例 2

worldtourfinals2024

入力例 3

出力例 3

S が 2023 で終わることが保証されていますが、 S が 2023 そのものである場合もあります。

入力例 4

20232023

出力例 4

20232024

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters and digits.
S is guaranteed to end with 2023.
Change the last character of S to 4 and print the modified string.

Constraints

S is a string of length between 4 and 100, inclusive, consisting of lowercase English letters and digits.
S ends with 2023.

Input

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

Output

Print the answer.

Sample Input 1

hello2023

Sample Output 1

hello2024

Changing the last character of hello2023 to 4 yields hello2024.

Sample Input 2

worldtourfinals2023

Sample Output 2

worldtourfinals2024

Sample Input 3

Sample Output 3

S is guaranteed to end with 2023, possibly being 2023 itself.

Sample Input 4

20232023

Sample Output 4

20232024

C - Counting Arrays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 個の数列が与えられます。
数列 i は、長さが L_i で j (1 \leq j \leq L_i) 番目の要素が a_{i,j} であるような数列です。

数列 i と数列 j は、 L_i = L_j かつすべての k (1 \leq k \leq L_i) に対して a_{i,k} = a_{j,k} が成り立つ時に同じであるとみなします。
同じ数列は 1 種類として数えるとき、数列 1 から数列 N の中に全部で何種類の数列がありますか？

制約

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
すべての数列の要素の個数の和、すなわち \sum_{i=1}^N L_i は 2 \times 10^5 を超えない。
入力はすべて整数である。

入力

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

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

出力

数列の種類数を出力せよ。

入力例 1

出力例 1

入力例 1 で与えられている数列は以下の 4 個です。

数列 1 : (1, 2)
数列 2 : (1, 1)
数列 3 : (2, 1)
数列 4 : (1, 2)

このうち数列 1 と数列 4 は同じ数列で、それ以外は互いに異なる数列なので全部で 3 種類の数列があります。

入力例 2

出力例 2

入力例 2 で与えられている数列は以下の 5 個です。

数列 1 : (1)
数列 2 : (1)
数列 3 : (2)
数列 4 : (1, 1)
数列 5 : (1, 1, 1)

入力例 3

1
1 1

出力例 3

Score : 200 points

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}

Output

Print the number of different sequences.

Sample Input 1

Sample Output 1

Sample Input 1 contains four sequences:

Sequence 1 : (1, 2)
Sequence 2 : (1, 1)
Sequence 3 : (2, 1)
Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

Sample Output 2

Sample Input 2 contains five sequences:

Sequence 1 : (1)
Sequence 2 : (1)
Sequence 3 : (2)
Sequence 4 : (1, 1)
Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

D - Longest Segment

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

二次元平面上に N 個の点があります。i 個目の点の座標は (x_i,y_i) です。

この中から 2 個の点を選ぶとき、それらを結ぶ線分の長さの最大値を求めてください。

制約

2 \leq N \leq 100
-1000 \leq x_i,y_i \leq 1000
(x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
入力はすべて整数

入力

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

N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N

出力

2 点を結ぶ線分の長さの最大値を出力せよ。

想定解との絶対誤差または相対誤差が 10^{-6} 以下であれば正解とみなされる。

入力例 1

出力例 1

1.4142135624

1 個目の点と 3 個目の点を選んだときそれらを結ぶ線分の長さは \sqrt 2 = 1.41421356237\dots となり、これが最大です。

入力例 2

出力例 2

1455.7159750446

Score : 200 points

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

2 \leq N \leq 100
-1000 \leq x_i,y_i \leq 1000
(x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
\hspace{0.4cm} \vdots
x_N y_N

Output

Print the maximum length of a segment connecting two of the points.

Your answer will be considered correct when the absolute or relative error from the judge's answer is at most 10^{-6}.

Sample Input 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

Sample Output 2

1455.7159750446

E - (K+1)-th Largest Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。 K = 0, 1, 2, \ldots, N-1 のそれぞれについて、下記の問題を解いてください。

1 以上 N 以下の整数 i であって、次の条件を満たすものの個数を求めよ。

A に含まれる整数のうち A_i より大きいものはちょうど K 種類である。

制約

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には K = i-1 の場合の問題の答えを出力せよ。

入力例 1

6
2 7 1 8 2 8

出力例 1

例として、K = 2 の場合の問題の答えを以下で求めます。

A_1 = 2 に関して、A に含まれる整数のうち A_1 より大きいものは、7, 8 の 2 種類です。
A_2 = 7 に関して、A に含まれる整数のうち A_2 より大きいものは、8 の 1 種類です。
A_3 = 1 に関して、A に含まれる整数のうち A_3 より大きいものは、2, 7, 8 の 3 種類です。
A_4 = 8 に関して、A に含まれる整数のうち A_4 より大きいものは、0 種類です（存在しません）。
A_5 = 2 に関して、A に含まれる整数のうち A_5 より大きいものは、7, 8 の 2 種類です。
A_6 = 8 に関して、A に含まれる整数のうち A_6 より大きいものは、0 種類です（存在しません）。

よって、A に含まれる整数のうちA_i より大きいものがちょうど K = 2 種類であるような i は、i = 1 と i = 5 の 2 つです。よって、K = 2 の場合の答えは 2 です。

入力例 2

1
1

出力例 2

入力例 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

出力例 3

Score : 300 points

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.

Find the number of integers i between 1 and N (inclusive) such that:

A contains exactly K distinct integers greater than A_i.

Constraints

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

Input

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

N
A_1 A_2 \ldots A_N

Output

Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain the answer for K = i-1.

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

For example, we will find the answer for K=2.

Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).

Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.

Sample Input 2

1
1

Sample Output 2

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3