実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 166 点
問題文
高橋君は庭に花壇を作ることにしました。花壇は横に細長い形をしており、そこに N 本の花を一列に植える予定です。
花壇の横幅は W センチメートルで、左端を位置 0 cm、右端を位置 W cm とします。花はそれぞれ大きさを無視できるものとし、1 番目の花を左端（位置 0 cm）に、N 番目の花を右端（位置 W cm）に植えます。N 本の花は、隣り合う花同士の間隔がすべて等しくなるように等間隔に配置します。すなわち、i 番目 (1 \leq i \leq N) の花は位置 \frac{(i-1) \times W}{N-1} cm に植えられ、隣り合う花の間隔はいずれも \frac{W}{N-1} センチメートルとなります。
花が健康に育つためには、隣り合う花同士の間隔を十分に確保する必要があります。具体的には、隣り合う花の間隔が K センチメートル以上でなければなりません。
高橋君は、上記の等間隔配置でこの条件を満たせるかどうかを確認したいです。条件を満たせる場合は Yes を、満たせない場合は No を出力してください。
制約
- 2 \leq N \leq 100
- 1 \leq W \leq 1000
- 1 \leq K \leq 1000
- 入力はすべて整数
入力
N W K
1 行目には、花の本数を表す整数 N、花壇の横幅（センチメートル）を表す整数 W、必要な最小間隔（センチメートル）を表す整数 K が、スペース区切りで与えられる。
出力
等間隔に配置したときに隣り合う花の間隔が K センチメートル以上である場合は Yes を、そうでない場合は No を 1 行で出力せよ。
入力例 1
5 100 20
出力例 1
Yes
入力例 2
10 180 25
出力例 2
No
入力例 3
51 500 15
出力例 3
No
Score : 166 pts
Problem Statement
Takahashi has decided to make a flower bed in his garden. The flower bed is long and narrow, and he plans to plant N flowers in a row.
The width of the flower bed is W centimeters, with the left end at position 0 cm and the right end at position W cm. Each flower can be considered as a point (its size is negligible). The 1st flower is planted at the left end (position 0 cm), and the Nth flower is planted at the right end (position W cm). The N flowers are placed at equal intervals so that the spacing between all adjacent flowers is the same. Specifically, the ith flower (1 \leq i \leq N) is planted at position \frac{(i-1) \times W}{N-1} cm, and the spacing between any two adjacent flowers is \frac{W}{N-1} centimeters.
For the flowers to grow healthily, the spacing between adjacent flowers must be sufficiently large. Specifically, the spacing between adjacent flowers must be at least K centimeters.
Takahashi wants to check whether this equal-interval arrangement satisfies the condition. If the condition is satisfied, output Yes; otherwise, output No.
Constraints
- 2 \leq N \leq 100
- 1 \leq W \leq 1000
- 1 \leq K \leq 1000
- All inputs are integers
Input
N W K
The first line contains three space-separated integers: N representing the number of flowers, W representing the width of the flower bed (in centimeters), and K representing the required minimum spacing (in centimeters).
Output
If the spacing between adjacent flowers in the equal-interval arrangement is at least K centimeters, output Yes; otherwise, output No on a single line.
Sample Input 1
5 100 20
Sample Output 1
Yes
Sample Input 2
10 180 25
Sample Output 2
No
Sample Input 3
51 500 15
Sample Output 3
No
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は海沿いの街を訪れています。
海から陸に向かって一直線に、N 棟の建物が並んでいます。建物には海に近い方から順に 1, 2, \ldots, N と番号が付けられており、建物 1 が最も海に近く、建物 N が最も海から遠くにあります。建物 i の高さは H_i です。すべての建物の幅は同じで、隙間なく一直線上に並んでいます。
高橋君は海上の十分に遠い地点からこの建物の列を正面に眺めています。手前の建物に遮られずに見える建物を「海から見える」建物と呼ぶことにし、次のように定めます。
- 建物 1 は常に海から見えます。
- i \geq 2 のとき、建物 1, 2, \ldots, i-1 の高さの最大値を M とします。H_i > M であれば建物 i は海から見えます。H_i \leq M であれば建物 i は海から見えません。
すなわち、建物 i が海から見えるのは、それより手前（海側）にあるすべての建物よりも厳密に高い場合に限ります。
海から見える建物の個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N H_1 H_2 \ldots H_N
- 1 行目には、建物の棟数 N が与えられる。
- 2 行目には、各建物の高さ H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
出力
海から見える建物の個数を 1 行で出力せよ。
入力例 1
5 3 1 4 1 5
出力例 1
3
入力例 2
8 10 5 15 8 15 20 12 25
出力例 2
4
入力例 3
12 100 50 80 120 90 110 150 140 200 180 250 300
出力例 3
6
Score : 233 pts
Problem Statement
Takahashi is visiting a town along the coast.
There are N buildings lined up in a straight line from the sea toward the land. The buildings are numbered 1, 2, \ldots, N in order from the closest to the sea, where building 1 is closest to the sea and building N is farthest from the sea. The height of building i is H_i. All buildings have the same width and are lined up in a straight line with no gaps between them.
Takahashi is viewing this row of buildings head-on from a sufficiently distant point on the sea. A building that can be seen without being blocked by buildings in front of it is called a building "visible from the sea," defined as follows:
- Building 1 is always visible from the sea.
- For i \geq 2, let M be the maximum height among buildings 1, 2, \ldots, i-1. If H_i > M, then building i is visible from the sea. If H_i \leq M, then building i is not visible from the sea.
In other words, building i is visible from the sea if and only if it is strictly taller than all buildings in front of it (on the sea side).
Find the number of buildings visible from the sea.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N H_1 H_2 \ldots H_N
- The first line gives the number of buildings N.
- The second line gives the heights of each building H_1, H_2, \ldots, H_N, separated by spaces.
Output
Print the number of buildings visible from the sea in one line.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
3
Sample Input 2
8 10 5 15 8 15 20 12 25
Sample Output 2
4
Sample Input 3
12 100 50 80 120 90 110 150 140 200 180 250 300
Sample Output 3
6
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は工場の品質管理システムを開発しています。このシステムでは、製造ラインに設置されたセンサーから取得したデータを監視し、異常な期間を検出する必要があります。
センサーは N 回の計測を行い、第 1 回目から第 N 回目まで順番にデータが記録されています。第 i 回目（1 \leq i \leq N）の計測で得られた値は「品質指標」と呼ばれる整数値 A_i です。品質指標は正の値、0、または負の値をとり得ます。
品質管理の基準として、連続するちょうど K 回分の計測における品質指標の合計が 0 以下になる場合、その区間を「異常期間」と判定します。より正確には、各開始位置 j（1 \leq j \leq N - K + 1）に対して、
A_j + A_{j+1} + \cdots + A_{j+K-1} \leq 0
が成り立つとき、開始位置 j の区間（第 j 回目から第 j+K-1 回目まで）は異常期間です。
異常期間と判定される区間の個数、すなわち上の条件を満たす開始位置 j の個数を求めてください。異なる開始位置に対応する区間は、たとえ互いに重なり合っていてもそれぞれ別々に数えます。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、計測回数を表す整数 N と、異常判定に用いる区間の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各計測の品質指標を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
異常期間と判定される区間の個数を 1 行で出力してください。
入力例 1
5 3 2 -1 -3 4 1
出力例 1
2
入力例 2
8 4 1 -2 3 -4 2 -1 -3 5
出力例 2
4
入力例 3
15 5 100 -50 -30 -25 10 -200 150 80 -100 -60 20 -10 5 -15 30
出力例 3
7
Score : 333 pts
Problem Statement
Takahashi is developing a quality control system for a factory. This system needs to monitor data collected from sensors installed on the manufacturing line and detect abnormal periods.
The sensor performs N measurements, and data is recorded in order from the 1-st to the N-th measurement. The value obtained at the i-th measurement (1 \leq i \leq N) is an integer A_i called the "quality index." The quality index can be positive, 0, or negative.
As a quality control criterion, if the sum of quality indices over a window of exactly K consecutive measurements is 0 or less, that interval is classified as an "abnormal period." More precisely, for each starting position j (1 \leq j \leq N - K + 1), if
$A_j + A_{j+1} + \cdots + A_{j+K-1} \leq 0$
holds, then the interval starting at position j (from the j-th to the (j+K-1)-th measurement) is an abnormal period.
Find the number of intervals classified as abnormal periods, that is, the number of starting positions j satisfying the above condition. Intervals corresponding to different starting positions are counted separately, even if they overlap with each other.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of measurements and an integer K representing the length of the interval used for anomaly detection, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the quality index of each measurement, separated by spaces.
Output
Print the number of intervals classified as abnormal periods in a single line.
Sample Input 1
5 3 2 -1 -3 4 1
Sample Output 1
2
Sample Input 2
8 4 1 -2 3 -4 2 -1 -3 5
Sample Output 2
4
Sample Input 3
15 5 100 -50 -30 -25 10 -200 150 80 -100 -60 20 -10 5 -15 30
Sample Output 3
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は広大な果樹園を経営しています。果樹園には N 本の果物の木があり、木 1, 木 2, \ldots, 木 N と番号が付けられています。それぞれの木からは複数回収穫することができます。
木 i（1 \leq i \leq N）は、初回の収穫で F_i 個の果物が採れますが、収穫を重ねるごとに木が疲弊し、採れる量が減っていきます。具体的には、木 i の疲弊度を D_i とすると、木 i から k 回目（k = 1, 2, 3, \ldots）に収穫したときに得られる果物の個数は \max(F_i - (k-1) \times D_i, \ 0) 個です。すなわち、同じ木から収穫するたびに疲弊度の分だけ収穫量が減少し、0 未満にはなりません。なお、ある木から何回目の収穫であるかはその木ごとに独立に数え、他の木の収穫状況には影響されません。
高橋君は、各木から何回ずつ収穫するかを自由に決めることができます。収穫しない木があっても構いません。ただし、収穫期間の制約により、すべての木に対する収穫回数の合計は M 回以下でなければなりません。異なる木からの収穫も、同じ木からの複数回の収穫も、すべて合わせて M 回以下です。なお、収穫量が 0 個となる収穫を行うことも許されますが、そのような収穫も 1 回として数えます。
このとき、得られる果物の個数の合計の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq F_i \leq 10^9
- 1 \leq D_i \leq 10^9
- 入力はすべて整数である
入力
N M F_1 D_1 F_2 D_2 \vdots F_N D_N
- 1 行目には、果物の木の本数を表す整数 N と、収穫できる合計回数の上限を表す整数 M が、スペース区切りで与えられる。
- 2 行目から N 行にわたって、各果物の木の情報が与えられる。
- 1 + i 行目（1 \leq i \leq N）には、木 i の初回収穫量 F_i と疲弊度 D_i が、スペース区切りで与えられる。
出力
高橋君が得られる果物の個数の合計の最大値を整数で 1 行に出力してください。
入力例 1
3 5 10 3 8 5 6 1
出力例 1
36
入力例 2
2 8 20 2 5 1
出力例 2
104
入力例 3
5 10 100 30 50 10 80 25 1000000000 1000000000 30 5
出力例 3
1000000495
Score : 366 pts
Problem Statement
Takahashi manages a vast orchard. The orchard has N fruit trees, numbered Tree 1, Tree 2, \ldots, Tree N. Each tree can be harvested multiple times.
Tree i (1 \leq i \leq N) yields F_i fruits on the first harvest, but the tree becomes exhausted with each successive harvest, and the yield decreases. Specifically, if the exhaustion rate of tree i is D_i, then the number of fruits obtained from the k-th harvest (k = 1, 2, 3, \ldots) of tree i is \max(F_i - (k-1) \times D_i, \ 0). That is, each time the same tree is harvested, the yield decreases by the exhaustion rate, and it does not go below 0. Note that the harvest count for each tree is tracked independently, and is not affected by the harvest status of other trees.
Takahashi can freely decide how many times to harvest each tree. It is also fine to not harvest some trees at all. However, due to constraints on the harvesting period, the total number of harvests across all trees must be at most M. This includes harvests from different trees as well as multiple harvests from the same tree, all counted together toward the limit of M. Note that performing a harvest that yields 0 fruits is allowed, but such a harvest still counts as one harvest.
Find the maximum total number of fruits that can be obtained.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq F_i \leq 10^9
- 1 \leq D_i \leq 10^9
- All inputs are integers
Input
N M F_1 D_1 F_2 D_2 \vdots F_N D_N
- The first line contains the integer N representing the number of fruit trees and the integer M representing the upper limit on the total number of harvests, separated by a space.
- The following N lines give the information for each fruit tree.
- The (1 + i)-th line (1 \leq i \leq N) contains the initial harvest yield F_i and the exhaustion rate D_i of tree i, separated by a space.
Output
Print the maximum total number of fruits Takahashi can obtain, as an integer on a single line.
Sample Input 1
3 5 10 3 8 5 6 1
Sample Output 1
36
Sample Input 2
2 8 20 2 5 1
Sample Output 2
104
Sample Input 3
5 10 100 30 50 10 80 25 1000000000 1000000000 30 5
Sample Output 3
1000000495
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は自分の部屋の本棚を整理することにしました。
本棚には N 冊の本が一列に並んでいます。これらの本は第 1 巻から第 N 巻までの全 N 巻からなるシリーズで、各巻がちょうど1冊ずつあります。現在、左から i 番目の位置には第 A_i 巻の本が置かれています。
高橋君は本を巻の順に並べたいと思っています。具体的には、左から i 番目の位置に第 i 巻の本が置かれている状態にしたいです。
高橋君は次の操作を好きな回数だけ繰り返し行うことができます。
- 隣り合う2冊の本を入れ替える。すなわち、整数 j （1 \leq j \leq N-1）を1つ選び、左から j 番目の位置にある本と左から j+1 番目の位置にある本を入れ替える。
本を巻の順に並べるために必要な操作回数の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- (A_1, A_2, \ldots, A_N) は (1, 2, \ldots, N) の順列である
- 入力はすべて整数
入力
N A_1 A_2 \ldots A_N
- 1 行目には、本の冊数を表す整数 N が与えられる。
- 2 行目には、現在の本の並び順を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。A_i は左から i 番目の位置に置かれている本の巻番号を表す。
出力
本を巻の順に並べるために必要な操作回数の最小値を 1 行で出力してください。
入力例 1
5 3 1 2 5 4
出力例 1
3
入力例 2
8 8 7 6 5 4 3 2 1
出力例 2
28
入力例 3
15 2 1 4 3 6 5 8 7 10 9 12 11 14 13 15
出力例 3
7
Score : 466 pts
Problem Statement
Takahashi has decided to organize the bookshelf in his room.
There are N books lined up in a row on the bookshelf. These books form a series consisting of all N volumes from volume 1 to volume N, with exactly one copy of each volume. Currently, the i-th position from the left holds volume A_i.
Takahashi wants to arrange the books in order of their volume numbers. Specifically, he wants the i-th position from the left to hold volume i.
Takahashi can perform the following operation any number of times:
- Swap two adjacent books. That is, choose an integer j (1 \leq j \leq N-1) and swap the book at the j-th position from the left with the book at the (j+1)-th position from the left.
Find the minimum number of operations required to arrange the books in order of their volume numbers.
Constraints
- 1 \leq N \leq 2 \times 10^5
- (A_1, A_2, \ldots, A_N) is a permutation of (1, 2, \ldots, N)
- All inputs are integers
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of books.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the current arrangement of the books. A_i represents the volume number of the book placed at the i-th position from the left.
Output
Print the minimum number of operations required to arrange the books in order of their volume numbers, on a single line.
Sample Input 1
5 3 1 2 5 4
Sample Output 1
3
Sample Input 2
8 8 7 6 5 4 3 2 1
Sample Output 2
28
Sample Input 3
15 2 1 4 3 6 5 8 7 10 9 12 11 14 13 15
Sample Output 3
7