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

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

H - Maximize Rating

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

配点 : 475 点

問題文

高橋君は N 回コンテストに参加し、i 回目に参加したコンテストにおいてパフォーマンス P_i を獲得しました。
高橋君はこの中から (1 つ以上) いくつかのコンテストを選び、それらの結果から計算される高橋君のレートを最大にしたいと考えています。

コンテストをうまく選んだとき、高橋君のレートとしてあり得る最大の値を求めてください。

ただし、高橋君のレート R は、高橋君の選んだコンテストの数が k 個であり、選んだコンテストにおけるパフォーマンスが 参加した順に それぞれ (Q_1,Q_2,\ldots,Q_k) であるとき、

\displaystyle R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}}

によって計算されます。

制約

1\leq N\leq 5000
1\leq P_i\leq 5000
入力はすべて整数

入力

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

N
P_1 P_2 \ldots P_N

出力

高橋君のレートとしてあり得る最大の値を出力せよ。
出力は、真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。

入力例 1

3
1000 600 1200

出力例 1

256.735020470879931

高橋君が 1 回目と 3 回目のコンテストを選んだ時、レートは、

\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502...

となり、この時レートが最大となります。

入力例 2

3
600 1000 1200

出力例 2

261.423219407873376

1,2,3 回目のコンテストすべてを選んだとき、レートが最大となります。

入力例 3

1
100

出力例 3

-1100.000000000000000

レートは負になることもあります。

Score : 475 points

Problem Statement

Takahashi participated in N contests and earned a performance P_i in the i-th contest.
He wants to choose some (at least one) contests from these and maximize his rating calculated from the results of those contests.

Find the maximum possible rating he can achieve by optimally choosing the contests.

Here, Takahashi's rating R is calculated as the following, where k is the number of chosen contests and (Q_1, Q_2, \ldots, Q_k) are the performances in the chosen contests in the order he participated:

\displaystyle R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}}.

Constraints

1\leq N\leq 5000
1\leq P_i\leq 5000
All input values are integers.

Input

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

N
P_1 P_2 \ldots P_N

Output

Print the maximum possible rating that Takahashi can achieve.
Your output will be considered correct if the absolute or relative error from the true value is at most 10^{-6}.

Sample Input 1

3
1000 600 1200

Sample Output 1

256.735020470879931

If Takahashi chooses the first and third contests, his rating will be:

\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502....

This is the maximum possible rating.

Sample Input 2

3
600 1000 1200

Sample Output 2

261.423219407873376

The rating is maximized when all the first, second, and third contests are selected.

Sample Input 3

1
100

Sample Output 3

-1100.000000000000000

The rating can also be negative.

I - x = a^b

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

配点 : 500 点

問題文

1 以上 N 以下の正整数 x であって、ある正整数 a と 2 以上の 正整数 b を用いて x=a^b と表現できるものはいくつありますか？

制約

入力は全て整数
1 \le N \le 10^{18}

入力

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

出力

答えを整数として出力せよ。

入力例 1

出力例 1

問題文中の条件を満たす整数は 1,4,8,9,16,25,27,32,36,49,64,81 の 12 個です。

入力例 2

1000000000000000000

出力例 2

1001003332

Score : 500 points

Problem Statement

How many integers x between 1 and N, inclusive, can be expressed as x = a^b using some positive integer a and a positive integer b not less than 2?

Constraints

All input values are integers.
1 \le N \le 10^{18}

Input

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

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

The integers that satisfy the conditions in the problem statement are 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81: there are 12.

Sample Input 2

1000000000000000000

Sample Output 2

1001003332