Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
半径 R の円の周長を出力してください。
制約
- 1 \leq R \leq 100
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられます。
R
出力
円の周長を出力せよ。 なお、想定解答との絶対誤差または相対誤差が 10^{−2} 以下であれば正解として扱われる。
入力例 1
1
出力例 1
6.28318530717958623200
10^{-2} 以下の絶対誤差・相対誤差が許容されるので、 6.28 も正解になりますが、6 は不正解となります。
入力例 2
73
出力例 2
458.67252742410977361942
Score : 100 points
Problem Statement
Print the circumference of a circle of radius R.
Constraints
- 1 \leq R \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
R
Output
Print the circumference of the circle. Your output is considered correct if and only if its absolute or relative error from our answer is at most 10^{-2}.
Sample Input 1
1
Sample Output 1
6.28318530717958623200
Since we accept an absolute or relative error of at most 10^{-2}, 6.28 is also an acceptable output, but 6 is not.
Sample Input 2
73
Sample Output 2
458.67252742410977361942
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋君の夏休みは N 日間です。
夏休みの宿題が M 個出されており、i 番目の宿題をやるには A_i 日間かかります。
複数の宿題を同じ日にやることはできず、また、宿題をやる日には遊ぶことができません。
夏休み中に全ての宿題を終わらせるとき、最大何日間遊ぶことができますか？
ただし、夏休み中に全ての宿題を終わらせることができないときは、かわりに -1 を出力してください。
制約
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^4
- 1 \leq A_i \leq 10^4
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 ... A_M
出力
高橋君が遊ぶことのできる日数、または、-1 を出力せよ。
入力例 1
41 2 5 6
出力例 1
30
例えば、最初の 5 日間で 1 番目の宿題をやり、その後 30 日間遊んで、最後の 6 日間で 2 番目の宿題をやることで、30 日間遊ぶことができます。
入力例 2
10 2 5 6
出力例 2
-1
宿題を終わらせることができません。
入力例 3
11 2 5 6
出力例 3
0
宿題を終わらせることはできますが、遊ぶことはできません。
入力例 4
314 15 9 26 5 35 8 9 79 3 23 8 46 2 6 43 3
出力例 4
9
Score : 200 points
Problem Statement
Takahashi has N days of summer vacation.
His teacher gave him M summer assignments. It will take A_i days for him to do the i-th assignment.
He cannot do multiple assignments on the same day, or hang out on a day he does an assignment.
What is the maximum number of days Takahashi can hang out during the vacation if he finishes all the assignments during this vacation?
If Takahashi cannot finish all the assignments during the vacation, print -1 instead.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^4
- 1 \leq A_i \leq 10^4
Input
Input is given from Standard Input in the following format:
N M A_1 ... A_M
Output
Print the maximum number of days Takahashi can hang out during the vacation, or -1.
Sample Input 1
41 2 5 6
Sample Output 1
30
For example, he can do the first assignment on the first 5 days, hang out on the next 30 days, and do the second assignment on the last 6 days of the vacation. In this way, he can safely spend 30 days hanging out.
Sample Input 2
10 2 5 6
Sample Output 2
-1
He cannot finish his assignments.
Sample Input 3
11 2 5 6
Sample Output 3
0
He can finish his assignments, but he will have no time to hang out.
Sample Input 4
314 15 9 26 5 35 8 9 79 3 23 8 46 2 6 43 3
Sample Output 4
9
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 人の社員からなる会社があり、各社員には 1,...,N の社員番号が割り当てられています。
社員番号 1 の社員以外の全ての社員には、自分より社員番号が小さい直属の上司がちょうど 1 人います。
X さんが Y さんの直属の上司であるとき、Y さんは X さんの直属の部下であるといいます。
社員番号 i の社員の直属の上司の社員番号が A_i であることが与えられます。各社員について直属の部下が何人いるか求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i < i
入力
入力は以下の形式で標準入力から与えられる。
N A_2 ... A_N
出力
社員番号 1,2,...,N のそれぞれの社員について、直属の部下が何人いるか、改行区切りで出力せよ。
入力例 1
5 1 1 2 2
出力例 1
2 2 0 0 0
社員番号 1 の社員の直属の部下は社員番号 2,3 の 2 人です。
社員番号 2 の社員の直属の部下は社員番号 4,5 の 2 人です。
社員番号 3,4,5 の社員には直属の部下はいません。
入力例 2
10 1 1 1 1 1 1 1 1 1
出力例 2
9 0 0 0 0 0 0 0 0 0
入力例 3
7 1 2 3 4 5 6
出力例 3
1 1 1 1 1 1 0
Score : 300 points
Problem Statement
A company has N members, who are assigned ID numbers 1, ..., N.
Every member, except the member numbered 1, has exactly one immediate boss with a smaller ID number.
When a person X is the immediate boss of a person Y, the person Y is said to be an immediate subordinate of the person X.
You are given the information that the immediate boss of the member numbered i is the member numbered A_i. For each member, find how many immediate subordinates it has.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i < i
Input
Input is given from Standard Input in the following format:
N A_2 ... A_N
Output
For each of the members numbered 1, 2, ..., N, print the number of immediate subordinates it has, in its own line.
Sample Input 1
5 1 1 2 2
Sample Output 1
2 2 0 0 0
The member numbered 1 has two immediate subordinates: the members numbered 2 and 3.
The member numbered 2 has two immediate subordinates: the members numbered 4 and 5.
The members numbered 3, 4, and 5 do not have immediate subordinates.
Sample Input 2
10 1 1 1 1 1 1 1 1 1
Sample Output 2
9 0 0 0 0 0 0 0 0 0
Sample Input 3
7 1 2 3 4 5 6
Sample Output 3
1 1 1 1 1 1 0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
10^{100}, 10^{100}+1, ..., 10^{100}+N の N+1 個の数があります。
この中から K 個以上の数を選ぶとき、その和としてあり得るものの個数を \bmod (10^9+7) で求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq N+1
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
和としてあり得るものの個数を \bmod (10^9+7) で出力せよ。
入力例 1
3 2
出力例 1
10
以下の 10 通りが考えられます。
- (10^{100})+(10^{100}+1)=2\times 10^{100}+1
- (10^{100})+(10^{100}+2)=2\times 10^{100}+2
- (10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\times 10^{100}+3
- (10^{100}+1)+(10^{100}+3)=2\times 10^{100}+4
- (10^{100}+2)+(10^{100}+3)=2\times 10^{100}+5
- (10^{100})+(10^{100}+1)+(10^{100}+2)=3\times 10^{100}+3
- (10^{100})+(10^{100}+1)+(10^{100}+3)=3\times 10^{100}+4
- (10^{100})+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+5
- (10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+6
- (10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\times 10^{100}+6
入力例 2
200000 200001
出力例 2
1
全てを選ぶしかないので 1 通りです。
入力例 3
141421 35623
出力例 3
220280457
Score : 400 points
Problem Statement
We have N+1 integers: 10^{100}, 10^{100}+1, ..., 10^{100}+N.
We will choose K or more of these integers. Find the number of possible values of the sum of the chosen numbers, modulo (10^9+7).
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq N+1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the number of possible values of the sum, modulo (10^9+7).
Sample Input 1
3 2
Sample Output 1
10
The sum can take 10 values, as follows:
- (10^{100})+(10^{100}+1)=2\times 10^{100}+1
- (10^{100})+(10^{100}+2)=2\times 10^{100}+2
- (10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\times 10^{100}+3
- (10^{100}+1)+(10^{100}+3)=2\times 10^{100}+4
- (10^{100}+2)+(10^{100}+3)=2\times 10^{100}+5
- (10^{100})+(10^{100}+1)+(10^{100}+2)=3\times 10^{100}+3
- (10^{100})+(10^{100}+1)+(10^{100}+3)=3\times 10^{100}+4
- (10^{100})+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+5
- (10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+6
- (10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\times 10^{100}+6
Sample Input 2
200000 200001
Sample Output 2
1
We must choose all of the integers, so the sum can take just 1 value.
Sample Input 3
141421 35623
Sample Output 3
220280457
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 人の幼児が左右一列に並んでおり、左から i 番目の幼児の活発度は A_i です。
あなたは一回だけ、幼児たちを好きな順番に並び替えさせることができます。
はじめ左から x 番目に並んでいた幼児が左から y 番目に移動するとき、うれしさが A_x \times |x-y| だけ生じます。
幼児のうれしさの合計が最大でいくつになるか求めてください。
制約
- 2 \leq N \leq 2000
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
幼児のうれしさの合計の最大値を出力せよ。
入力例 1
4 1 3 4 2
出力例 1
20
左から 1 番目の幼児を 3 番目に、2 番目の幼児を 4 番目に、3 番目の幼児を 1 番目に、4 番目の幼児を 2 番目に並ばせると、うれしさの合計は 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 になります。
入力例 2
6 5 5 6 1 1 1
出力例 2
58
入力例 3
6 8 6 9 1 2 1
出力例 3
85
Score : 500 points
Problem Statement
There are N children standing in a line from left to right. The activeness of the i-th child from the left is A_i.
You can rearrange these children just one time in any order you like.
When a child who originally occupies the x-th position from the left in the line moves to the y-th position from the left, that child earns A_x \times |x-y| happiness points.
Find the maximum total happiness points the children can earn.
Constraints
- 2 \leq N \leq 2000
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Print the maximum total happiness points the children can earn.
Sample Input 1
4 1 3 4 2
Sample Output 1
20
If we move the 1-st child from the left to the 3-rd position from the left, the 2-nd child to the 4-th position, the 3-rd child to the 1-st position, and the 4-th child to the 2-nd position, the children earns 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 happiness points in total.
Sample Input 2
6 5 5 6 1 1 1
Sample Output 2
58
Sample Input 3
6 8 6 9 1 2 1
Sample Output 3
85
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N までの番号がつけられた N 個の頂点を持つ木があります。この木の i 番目の辺は頂点 a_i と b_i を結んでいます。 また、各頂点には色が塗られており、 頂点 i に塗られている色は c_i です。ここで、各頂点に塗られている色は 1 以上 N 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。
k=1,2,...,N に対して、以下の問題を解いてください。
- 色 k が塗られている頂点を一度以上通るような単純パスの数を求めよ
補足: 頂点 u から頂点 v へ向かう単純パスと、頂点 v から頂点 u へ向かう単純パスは区別しません。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq c_i \leq N
- 1 \leq a_i,b_i \leq N
- 与えられるグラフは木である。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
c_1 c_2 ... c_N
a_1 b_1
:
a_{N-1} b_{N-1}
出力
k=1,2,...,N に対する問題の答えを、順番に改行区切りで出力せよ。
入力例 1
3 1 2 1 1 2 2 3
出力例 1
5 4 0
頂点 i と頂点 j を結ぶ単純パスを、P_{i,j} と表します。
色 1 が塗られている頂点を一度以上通る単純パスは、
P_{1,1}\,,\,
P_{1,2}\,,\,
P_{1,3}\,,\,
P_{2,3}\,,\,
P_{3,3}
の 5 つあります。
色 2 が塗られている頂点を一度以上通る単純パスは、
P_{1,2}\,,\,
P_{1,3}\,,\,
P_{2,2}\,,\,
P_{2,3}
の 4 つあります。
色 3 が塗られている頂点を一度以上通る単純パスはありません。
入力例 2
1 1
出力例 2
1
入力例 3
2 1 2 1 2
出力例 3
2 2
入力例 4
5 1 2 3 4 5 1 2 2 3 3 4 3 5
出力例 4
5 8 10 5 5
入力例 5
8 2 7 2 5 4 1 7 5 3 1 1 2 2 7 4 5 5 6 6 8 7 8
出力例 5
18 15 0 14 23 0 23 0
Score : 600 points
Problem Statement
We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i. Additionally, each vertex is painted in a color, and the color of Vertex i is c_i. Here, the color of each vertex is represented by an integer between 1 and N (inclusive). The same integer corresponds to the same color; different integers correspond to different colors.
For each k=1, 2, ..., N, solve the following problem:
- Find the number of simple paths that visit a vertex painted in the color k one or more times.
Note: The simple paths from Vertex u to v and from v to u are not distinguished.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq c_i \leq N
- 1 \leq a_i,b_i \leq N
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
c_1 c_2 ... c_N
a_1 b_1
:
a_{N-1} b_{N-1}
Output
Print the answers for k = 1, 2, ..., N in order, each in its own line.
Sample Input 1
3 1 2 1 1 2 2 3
Sample Output 1
5 4 0
Let P_{i,j} denote the simple path connecting Vertex i and j.
There are 5 simple paths that visit a vertex painted in the color 1 one or more times:
P_{1,1}\,,\,
P_{1,2}\,,\,
P_{1,3}\,,\,
P_{2,3}\,,\,
P_{3,3}
There are 4 simple paths that visit a vertex painted in the color 2 one or more times:
P_{1,2}\,,\,
P_{1,3}\,,\,
P_{2,2}\,,\,
P_{2,3}
There are no simple paths that visit a vertex painted in the color 3 one or more times.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
2 1 2 1 2
Sample Output 3
2 2
Sample Input 4
5 1 2 3 4 5 1 2 2 3 3 4 3 5
Sample Output 4
5 8 10 5 5
Sample Input 5
8 2 7 2 5 4 1 7 5 3 1 1 2 2 7 4 5 5 6 6 8 7 8
Sample Output 5
18 15 0 14 23 0 23 0