Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
あるイベントには N 人が参加し、i 番目の人の交通費は A_i 円でした。
イベントの主催者である高橋くんは、交通費補助額の上限額 x を設定して、人 i には交通費補助額として \min(x,A_i) 円を支給することとしました。ここで x は非負整数である必要があります。
高橋くんの予算が M 円であり、N 人に渡す交通費補助額の総和を M 円以下にしたいとき、交通費補助額の上限額 x は最大でいくらにできますか？
ただし、交通費補助額の上限額を無限に大きくできる場合は代わりにそのことを報告してください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq M \leq 2\times 10^{14}
- 1\leq A_i \leq 10^9
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A_1 A_2 \ldots A_{N}
出力
予算の条件を満たすときの交通費補助額の上限額 x の最大値を整数として出力せよ。
ただし、交通費補助額の上限額を無限に大きくできる場合は代わりに infinite と出力せよ。
入力例 1
4 8 1 3 2 4
出力例 1
2
交通費補助額の上限額を 2 円にすると、N 人に渡す交通費補助額の総和は \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 円となり、予算の 8 円以下となります。
交通費補助額の上限額を 3 円にすると、N 人に渡す交通費補助額の総和は \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 円となり、予算の 8 円を超えてしまいます。
よって、交通費補助額の上限額の最大値は 2 円となります。
入力例 2
3 20 5 3 2
出力例 2
infinite
交通費補助額の上限額を無限に大きくできます。
入力例 3
10 23 2 5 6 5 2 1 7 9 7 2
出力例 3
2
Score : 300 points
Problem Statement
There are N people participating in an event, and the transportation cost for the i-th person is A_i yen.
Takahashi, the organizer of the event, decided to set a maximum limit x for the transportation subsidy. The subsidy for person i will be \min(x, A_i) yen. Here, x must be a non-negative integer.
Given that Takahashi's budget is M yen, and he wants the total transportation subsidy for all N people to be at most M yen, what is the maximum possible value of the subsidy limit x?
If the subsidy limit can be made infinitely large, report that instead.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^{14}
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A_1 A_2 \ldots A_{N}
Output
Print the maximum value of the subsidy limit x that satisfies the budget condition, as an integer.
If the subsidy limit can be made infinitely large, print infinite instead.
Sample Input 1
4 8 1 3 2 4
Sample Output 1
2
If the subsidy limit is set to 2 yen, the total transportation subsidy for all N people is \min(2,1) + \min(2,3) + \min(2,2) + \min(2,4) = 7 yen, which is within the budget of 8 yen.
If the subsidy limit is set to 3 yen, the total transportation subsidy for all N people is \min(3,1) + \min(3,3) + \min(3,2) + \min(3,4) = 9 yen, which exceeds the budget of 8 yen.
Therefore, the maximum possible value of the subsidy limit is 2 yen.
Sample Input 2
3 20 5 3 2
Sample Output 2
infinite
The subsidy limit can be made infinitely large.
Sample Input 3
10 23 2 5 6 5 2 1 7 9 7 2
Sample Output 3
2
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋くんは数直線上に N 個のプレゼントを置きました。そのうち i 個目のプレゼントは座標 A_i に置かれました。
あなたは数直線上の長さ M の半開区間 [x,x+M) を選び、そこに含まれるプレゼントを全て獲得します。
より詳しくは、以下の手順でプレゼントを獲得します。
- まず、実数 x をひとつ選択する。
- その後、プレゼントのうち置かれている座標が x \le A_i < x+M を満たすものを全て獲得する。
最大でいくつのプレゼントを獲得することができますか?
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- 0 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
8 6 2 3 5 7 11 13 17 19
出力例 1
4
例えば、半開区間 [1.5,7.5) を指定します。
このとき、座標 2,3,5,7 にある 4 つのプレゼントを全て獲得することができ、これが獲得可能な最大の個数です。
入力例 2
10 1 3 1 4 1 5 9 2 6 5 3
出力例 2
2
同一の座標に複数のプレゼントが置いてあることもあります。
入力例 3
10 998244353 100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
出力例 3
7
Score : 300 points
Problem Statement
Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.
You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.
- First, choose one real number x.
- Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.
What is the maximum number of gifts you can acquire?
Constraints
- All input values are integers.
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- 0 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
8 6 2 3 5 7 11 13 17 19
Sample Output 1
4
For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.
Sample Input 2
10 1 3 1 4 1 5 9 2 6 5 3
Sample Output 2
2
There may be multiple gifts at the same coordinate.
Sample Input 3
10 998244353 100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
円周上に N 個の点が等間隔に並んでおり、時計回りに 1,2,\ldots,N と番号がつけられています。
M 本の相異なる直線があり、i 本目の直線は異なる 2 つの点、点 A_i と点 B_i を通る直線です。(1 \leq i \leq M)
以下の 2 つの条件をともに満たすような整数の組 (i,j) の個数を求めてください。
- 1 \leq i < j \leq M
- i 本目の直線と j 本目の直線は交わる
制約
- 2 \leq N \leq 10^6
- 1 \leq M \leq 3 \times 10^{5}
- 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
- (A_i,B_i) \neq (A_j,B_j) (i \neq j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
答えを出力せよ。
入力例 1
8 3 1 5 1 8 2 4
出力例 1
2
次の図のように円周上に 8 個の点と 3 本の直線があります。
1 本目の直線と 2 本目の直線は交わります。1 本目の直線と 3 本目の直線は交わりません。2 本目の直線と 3 本目の直線は交わります。(i,j)=(1,2),(2,3) の 2 つの組が条件を満たすため、2 を出力します。
入力例 2
5 10 2 5 1 5 1 2 2 4 2 3 1 3 1 4 3 5 3 4 4 5
出力例 2
40
Score : 400 points
Problem Statement
There are N equally spaced points on a circle labeled clockwise as 1,2,\ldots,N.
There are M distinct lines, where the i-th line passes through two distinct points A_i and B_i (1 \leq i \leq M).
Find the number of pairs (i,j) satisfying:
- 1 \le i < j \le M, and
- the i-th and j-th lines intersect.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq M \leq 3 \times 10^{5}
- 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
- (A_i,B_i) \neq (A_j,B_j) (i \neq j)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Print the answer.
Sample Input 1
8 3 1 5 1 8 2 4
Sample Output 1
2
As shown in the diagram below, there are eight points and three lines on the circle.
The 1st and 2nd lines intersect. The 1st and 3rd lines do not intersect. The 2nd and 3rd lines intersect. Since the pairs (i,j)=(1,2),(2,3) satisfy the conditions, print 2.
Sample Input 2
5 10 2 5 1 5 1 2 2 4 2 3 1 3 1 4 3 5 3 4 4 5
Sample Output 2
40
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。以下の条件を全て満たす正整数組 (i,j,k) の個数を求めてください。
- 1\leq i < j < k\leq N
- A_i = A_k
- A_i \neq A_j
制約
- 3\leq N\leq 3\times 10^5
- 1\leq A_i \leq N
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを整数として出力せよ。
入力例 1
5 1 2 1 3 2
出力例 1
3
条件を全て満たす正整数組 (i,j,k) は以下の 3 個です。
- (i,j,k)=(1,2,3)
- (i,j,k)=(2,3,5)
- (i,j,k)=(2,4,5)
入力例 2
7 1 2 3 4 5 6 7
出力例 2
0
条件を全て満たす正整数組 (i,j,k) が存在しない場合もあります。
入力例 3
13 9 7 11 7 3 8 1 13 11 11 11 6 13
出力例 3
20
Score : 450 points
Problem Statement
You are given a sequence of positive integers of length N: A=(A_1,A_2,\ldots,A_N). Find the number of triples of positive integers (i,j,k) that satisfy all of the following conditions:
- 1\leq i < j < k\leq N,
- A_i = A_k,
- A_i \neq A_j.
Constraints
- 3\leq N\leq 3\times 10^5
- 1\leq A_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer as an integer.
Sample Input 1
5 1 2 1 3 2
Sample Output 1
3
The following three triples of positive integers (i,j,k) satisfy the conditions:
- (i,j,k)=(1,2,3)
- (i,j,k)=(2,3,5)
- (i,j,k)=(2,4,5)
Sample Input 2
7 1 2 3 4 5 6 7
Sample Output 2
0
There may be no triples of positive integers (i,j,k) that satisfy the conditions.
Sample Input 3
13 9 7 11 7 3 8 1 13 11 11 11 6 13
Sample Output 3
20
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
頂点に 1 から N の番号が、辺に 1 から N-1 の番号が付いた N 頂点 N-1 辺の重み付き無向連結グラフ G が与えられます。辺 i は頂点 a_i と頂点 b_i を結んでおり、その重みは c_i です。
Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。
- 整数 u_i,v_i,w_i が与えられる。G の頂点 u_i,v_i の間に重み w_i の辺を追加する。その後、G の最小全域木に含まれる辺の重みの和を出力する。
制約
- 2\leq N\leq 2 \times 10^5
- 1\leq Q\leq 2 \times 10^5
- 1\leq a_i\lt b_i\leq N
- 1\leq u_i\lt v_i\leq N
- 1\leq c_i,w_i\leq 10
- クエリを処理する前のグラフは連結
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q
出力
Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。
入力例 1
4 4 1 2 6 2 3 5 2 4 4 1 3 3 1 2 3 1 4 10 3 4 1
出力例 1
12 10 10 7
各クエリで辺を追加した後のグラフを示しています。最小全域木に含まれる辺は赤色で塗られています。
入力例 2
8 6 1 8 8 1 6 10 1 5 8 2 6 6 6 7 6 1 3 9 2 4 7 1 3 4 1 6 7 3 4 6 1 5 1 7 8 4 3 5 3
出力例 2
49 46 45 38 34 33
Score : 550 points
Problem Statement
You are given a weighted undirected connected graph G with N vertices and N-1 edges, where vertices are numbered 1 to N and edges are numbered 1 to N-1. Edge i connects vertices a_i and b_i with a weight of c_i.
You are given Q queries to process sequentially. The i-th query is described as follows:
- You are given integers u_i, v_i, w_i. Add an edge with weight w_i between vertices u_i and v_i in G. Then, print the sum of the weights of the edges in a minimum spanning tree of G.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq a_i < b_i \leq N
- 1 \leq u_i < v_i \leq N
- 1 \leq c_i, w_i \leq 10
- The graph is connected before processing the queries.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
4 4 1 2 6 2 3 5 2 4 4 1 3 3 1 2 3 1 4 10 3 4 1
Sample Output 1
12 10 10 7
Here is the graph after adding the edge for each query. The edges included in the minimum spanning tree are colored red.
Sample Input 2
8 6 1 8 8 1 6 10 1 5 8 2 6 6 6 7 6 1 3 9 2 4 7 1 3 4 1 6 7 3 4 6 1 5 1 7 8 4 3 5 3
Sample Output 2
49 46 45 38 34 33