Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
1, 2, \ldots, N の番号がついた N 人の人が二次元平面上におり、人 i は座標 (X_i,Y_i) で表される地点にいます。
人 1 がウイルスに感染しました。ウイルスに感染した人から距離が D 以内にいる人にウイルスはうつります。
ただし、距離はユークリッド距離、すなわち 2 点 (a_1, a_2) と (b_1, b_2) に対し、この 2 点間の距離が \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2} であるものとして定められています。
十分に時間が経過した、すなわち人 i がウイルスに感染しているならば 人 i との距離が D 以内にいるすべての人がウイルスに感染している状態になったときに、各 i について人 i がウイルスに感染しているか判定してください。
制約
- 1 \leq N, D \leq 2000
- -1000 \leq X_i, Y_i \leq 1000
- i \neq j のとき (X_i, Y_i) \neq (X_j, Y_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
N 行出力せよ。i 行目には、人 i がウイルスに感染しているならば Yes を、そうでないならば No を出力せよ。
入力例 1
4 5 2 -1 3 1 8 8 0 5
出力例 1
Yes Yes No Yes
人 1 と人 2 の距離は \sqrt 5 であるため、人 2 はウイルスに感染します。
また、人 2 と人 4 の距離は 5 であるため、人 4 はウイルスに感染します。
人 3 は距離 5 以内に人がいないので、ウイルスに感染することはありません。
入力例 2
3 1 0 0 -1000 -1000 1000 1000
出力例 2
Yes No No
入力例 3
9 4 3 2 6 -1 1 6 6 5 -2 -3 5 3 2 -3 2 1 2 6
出力例 3
Yes No No Yes Yes Yes Yes Yes No
Score : 300 points
Problem Statement
There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).
Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.
Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.
After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.
Constraints
- 1 \leq N, D \leq 2000
- -1000 \leq X_i, Y_i \leq 1000
- (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print N lines. The i-th line should contain Yes if person i is infected with the virus, and No otherwise.
Sample Input 1
4 5 2 -1 3 1 8 8 0 5
Sample Output 1
Yes Yes No Yes
The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.
Sample Input 2
3 1 0 0 -1000 -1000 1000 1000
Sample Output 2
Yes No No
Sample Input 3
9 4 3 2 6 -1 1 6 6 5 -2 -3 5 3 2 -3 2 1 2 6
Sample Output 3
Yes No No Yes Yes Yes Yes Yes No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
N 種類のビーンズが 1 粒ずつあります。 i 種類目のビーンズはおいしさが A_i で色が C_i です。ビーンズは混ぜられており、色でしか区別することができません。
あなたはビーンズの色を 1 つ選び、その色のビーンズをどれか 1 粒食べます。ビーンズの色をうまく選ぶことで、食べる可能性のあるビーンズのおいしさの最小値を最大化してください。
制約
- 1 \leq N \leq 2 \times 10^{5}
- 1 \leq A_i \leq 10^{9}
- 1 \leq C_i \leq 10^{9}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 C_1 A_2 C_2 \vdots A_N C_N
出力
食べる可能性のあるビーンズのおいしさの最小値の最大値を整数として出力せよ。
入力例 1
4 100 1 20 5 30 5 40 1
出力例 1
40
同じ色のビーンズは互いに区別がつかないことに注意してください。
選ぶことができる色は 色 1 と 色 5 です。
- 色 1 のビーンズは 2 種類あり、美味しさはそれぞれ 100, 40 です。よって、色 1 を選んだときのおいしさの最小値は 40 です。
- 色 5 のビーンズは 2 種類あり、美味しさはそれぞれ 20, 30 です。よって、色 5 を選んだときのおいしさの最小値は 20 です。
おいしさの最小値を最大化するには 色 1 を選べばよいため、そのときの最小値である 40 を出力します。
入力例 2
10 68 3 17 2 99 2 92 4 82 4 10 3 100 2 78 1 3 1 35 4
出力例 2
35
Score: 250 points
Problem Statement
There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.
You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.
Constraints
- 1 \leq N \leq 2 \times 10^{5}
- 1 \leq A_i \leq 10^{9}
- 1 \leq C_i \leq 10^{9}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 C_1 A_2 C_2 \vdots A_N C_N
Output
Print as an integer the maximum value of the minimum possible deliciousness of the bean you eat.
Sample Input 1
4 100 1 20 5 30 5 40 1
Sample Output 1
40
Note that beans of the same color cannot be distinguished from each other.
You can choose color 1 or color 5.
- There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
- There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.
To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.
Sample Input 2
10 68 3 17 2 99 2 92 4 82 4 10 3 100 2 78 1 3 1 35 4
Sample Output 2
35
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ N の数列 A=(A_0,\ldots,A_{N-1}) があります。
次の条件を全て満たす整数の組 (x,y,z,w) が存在するか判定してください。
- 0 \leq x < y < z < w \leq N
- A_x + A_{x+1} + \ldots + A_{y-1} = P
- A_y + A_{y+1} + \ldots + A_{z-1} = Q
- A_z + A_{z+1} + \ldots + A_{w-1} = R
制約
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq P,Q,R \leq 10^{15}
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N P Q R
A_0 A_1 \ldots A_{N-1}
出力
条件を満たす組が存在するなら Yes、存在しないなら No を出力せよ。
入力例 1
10 5 7 5 1 3 2 2 2 3 1 4 3 2
出力例 1
Yes
(x,y,z,w)=(1,3,6,8) が条件を満たします。
入力例 2
9 100 101 100 31 41 59 26 53 58 97 93 23
出力例 2
No
入力例 3
7 1 1 1 1 1 1 1 1 1 1
出力例 3
Yes
Score : 400 points
Problem Statement
There is a sequence A=(A_0,\ldots,A_{N-1}) of length N.
Determine if there exists a tuple of integers (x,y,z,w) that satisfies all of the following conditions:
- 0 \leq x < y < z < w \leq N
- A_x + A_{x+1} + \ldots + A_{y-1} = P
- A_y + A_{y+1} + \ldots + A_{z-1} = Q
- A_z + A_{z+1} + \ldots + A_{w-1} = R
Constraints
- 3 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq P,Q,R \leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P Q R
A_0 A_1 \ldots A_{N-1}
Output
If there exists a tuple that satisfies the conditions, print Yes; otherwise, print No.
Sample Input 1
10 5 7 5 1 3 2 2 2 3 1 4 3 2
Sample Output 1
Yes
(x,y,z,w)=(1,3,6,8) satisfies the conditions.
Sample Input 2
9 100 101 100 31 41 59 26 53 58 97 93 23
Sample Output 2
No
Sample Input 3
7 1 1 1 1 1 1 1 1 1 1
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
1 から N の番号がついた N 人の人がいます。
高橋君は 1 から N までの整数を並び替えた列 P = (P_1, P_2, \dots, P_N) を 1 つ選んで、 人 P_1, 人 P_2, \dots, 人 P_N の順番に 1 人ずつキャンディを配ることにしました。
人 i は人 X_i のことが嫌いなので、高橋君が人 i より先に人 X_i にキャンディを配った場合、人 i に不満度 C_i がたまります。そうでない場合の人 i の不満度は 0 です。
高橋君が P を自由に選べるとき、全員の不満度の和の最小値はいくつになりますか？
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq X_i \leq N
- X_i \neq i
- 1 \leq C_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X_1 X_2 \dots X_N C_1 C_2 \dots C_N
出力
答えを出力せよ。
入力例 1
3 2 3 2 1 10 100
出力例 1
10
P = (1, 3, 2) とすれば不満度が正になるのは人 2 だけで、この時全員の不満度の和は 10 になります。
これより不満度の和を小さくすることはできないので、答えは 10 です。
入力例 2
8 7 3 5 5 8 4 1 2 36 49 73 38 30 85 27 45
出力例 2
57
Score : 500 points
Problem Statement
There are N people numbered 1 through N.
Takahashi has decided to choose a sequence P = (P_1, P_2, \dots, P_N) that is a permutation of integers from 1 through N, and give a candy to Person P_1, Person P_2, \dots, and Person P_N, in this order.
Since Person i dislikes Person X_i, if Takahashi gives a candy to Person X_i prior to Person i, then Person i gains frustration of C_i; otherwise, Person i's frustration is 0.
Takahashi may arbitrarily choose P. What is the minimum possible sum of their frustration?
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq X_i \leq N
- X_i \neq i
- 1 \leq C_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X_1 X_2 \dots X_N C_1 C_2 \dots C_N
Output
Print the answer.
Sample Input 1
3 2 3 2 1 10 100
Sample Output 1
10
If he lets P = (1, 3, 2), only Person 2 gains a positive amount of frustration, in which case the sum of their frustration is 10.
Since it is impossible to make the sum of frustration smaller, the answer is 10.
Sample Input 2
8 7 3 5 5 8 4 1 2 36 49 73 38 30 85 27 45
Sample Output 2
57
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 個の頂点と M 本の辺からなる単純（自己ループおよび多重辺を持たない）かつ連結な無向グラフが与えられます。
i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結びます。
下記の 2 つの条件をともに満たす整数列 (A_1, A_2, \ldots, A_k) を長さ k のパスと呼びます。
- すべての i = 1, 2, \dots, k について、1 \leq A_i \leq N 。
- すべての i = 1, 2, \ldots, k-1 について、頂点 A_i と頂点 A_{i+1} は辺で直接結ばれている。
空列も長さ 0 のパスとみなします。
S = s_1s_2\ldots s_N を 0 と 1 のみからなる長さ N の文字列とします。 パス A = (A_1, A_2, \ldots, A_k) が下記を満たすとき、パス A を S に関する良いパスと呼びます。
- すべての i = 1, 2, \ldots, N について、次を満たす。
- s_i = 0 ならば、A に含まれる i の個数は偶数である。
- s_i = 1 ならば、A に含まれる i の個数は奇数である。
S として考えられる文字列（すなわち、0 と 1 のみからなる長さ N の文字列）は 2^N 個ありますが、そのすべてにわたる「 S に関する良いパスのうち最短のものの長さ」の総和を出力してください。
この問題の制約下において、0 と 1 からなる長さ N のどのような文字列を S として選んでも、S に関する良いパスが少なくとも 1 つ存在することが示せます。
制約
- 2 \leq N \leq 17
- N-1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq u_i, v_i \leq N
- 与えられるグラフは単純かつ連結
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
答えを出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
14
- S = 000 のとき、空列 () は S に関する最短の良いパスであり、その長さは 0 です。
- S = 100 のとき、(1) は S に関する最短の良いパスであり、その長さは 1 です。
- S = 010 のとき、(2) は S に関する最短の良いパスであり、その長さは 1 です。
- S = 110 のとき、(1, 2) は S に関する最短の良いパスであり、その長さは 2 です。
- S = 001 のとき、(3) は S に関する最短の良いパスであり、その長さは 1 です。
- S = 101 のとき、(1, 2, 3, 2) は S に関する最短の良いパスであり、その長さは 4 です。
- S = 011 のとき、(2, 3) は S に関する最短の良いパスであり、その長さは 2 です。
- S = 111 のとき、(1, 2, 3) は S に関する最短の良いパスであり、その長さは 3 です。
よって、求める答えは 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14 です。
入力例 2
5 5 4 2 2 3 1 3 2 1 1 5
出力例 2
108
Score : 500 points
Problem Statement
You are given a simple connected undirected graph with N vertices and M edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
A sequence (A_1, A_2, \ldots, A_k) is said to be a path of length k if both of the following two conditions are satisfied:
- For all i = 1, 2, \dots, k, it holds that 1 \leq A_i \leq N.
- For all i = 1, 2, \ldots, k-1, Vertex A_i and Vertex A_{i+1} are directly connected by an edge.
An empty sequence is regarded as a path of length 0.
Let S = s_1s_2\ldots s_N be a string of length N consisting of 0 and 1. A path A = (A_1, A_2, \ldots, A_k) is said to be a good path with respect to S if the following conditions are satisfied:
- For all i = 1, 2, \ldots, N, it holds that:
- if s_i = 0, then A has even number of i's.
- if s_i = 1, then A has odd number of i's.
There are 2^N possible S (in other words, there are 2^N strings of length N consisting of 0 and 1). Find the sum of "the length of the shortest good path with respect to S" over all those S.
Under the Constraints of this problem, it can be proved that, for any string S of length N consisting of 0 and 1, there is at least one good path with respect to S.
Constraints
- 2 \leq N \leq 17
- N-1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq u_i, v_i \leq N
- The given graph is simple and connected.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print the answer.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
14
- For S = 000, the empty sequence () is the shortest good path with respect to S, whose length is 0.
- For S = 100, (1) is the shortest good path with respect to S, whose length is 1.
- For S = 010, (2) is the shortest good path with respect to S, whose length is 1.
- For S = 110, (1, 2) is the shortest good path with respect to S, whose length is 2.
- For S = 001, (3) is the shortest good path with respect to S, whose length is 1.
- For S = 101, (1, 2, 3, 2) is the shortest good path with respect to S, whose length is 4.
- For S = 011, (2, 3) is the shortest good path with respect to S, whose length is 2.
- For S = 111, (1, 2, 3) is the shortest good path with respect to S, whose length is 3.
Therefore, the sought answer is 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14.
Sample Input 2
5 5 4 2 2 3 1 3 2 1 1 5
Sample Output 2
108