実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は会社の経理担当として、今月の従業員へのボーナス支給を管理しています。
会社には N 人の従業員がおり、それぞれの従業員には業績に応じた報酬額が決まっています。i 番目の従業員の報酬額は P_i 円です。
社長から次のような指示がありました。「報酬額が K の倍数である従業員には、特別手当を支給したい。まずは該当する従業員の報酬額の合計を教えてほしい。」
高橋君を手伝って、報酬額が K の倍数（すなわち P_i が K で割り切れる）である従業員の報酬額の合計を求めてください。該当する従業員がいない場合、合計は 0 です。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq 10^9
- 入力はすべて整数
入力
N K P_1 P_2 \ldots P_N
- 1 行目には、従業員の人数を表す整数 N と、倍数判定に用いる整数 K が、スペース区切りで与えられる。
- 2 行目には、各従業員の報酬額を表す N 個の整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
出力
報酬額が K の倍数である従業員の報酬額の合計を 1 行で出力してください。
入力例 1
5 3 6 7 9 12 5
出力例 1
27
入力例 2
8 5 10 25 7 15 30 8 100 3
出力例 2
180
入力例 3
10 1000000 500000 1000000 2000000 3000000 750000 4000000 1234567 5000000 999999 6000000
出力例 3
21000000
Score : 200 pts
Problem Statement
Takahashi is in charge of accounting at his company and is managing this month's bonus payments to employees.
The company has N employees, and each employee has a compensation amount determined by their performance. The compensation amount for the i-th employee is P_i yen.
The company president gave the following instruction: "I would like to give a special allowance to employees whose compensation amount is a multiple of K. First, please tell me the total of the compensation amounts for the applicable employees."
Help Takahashi find the total of the compensation amounts for employees whose compensation amount is a multiple of K (that is, P_i is divisible by K). If there are no such employees, the total is 0.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq 10^9
- All inputs are integers
Input
N K P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of employees and an integer K used for the divisibility check, separated by a space.
- The second line contains N integers P_1, P_2, \ldots, P_N representing the compensation amounts of each employee, separated by spaces.
Output
Print the total of the compensation amounts for employees whose compensation amount is a multiple of K, on a single line.
Sample Input 1
5 3 6 7 9 12 5
Sample Output 1
27
Sample Input 2
8 5 10 25 7 15 30 8 100 3
Sample Output 2
180
Sample Input 3
10 1000000 500000 1000000 2000000 3000000 750000 4000000 1234567 5000000 999999 6000000
Sample Output 3
21000000
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は学校のクラス担任として、生徒たちの成績管理を行っています。クラスには N 人の生徒がおり、生徒には 1 から N までの番号が付けられています。i 番目の生徒の初期の点数は S_i 点です。
学期末になり、成績表の更新作業を行うことになりました。更新は合計 M 回行われます。j 回目の更新では、生徒 P_j の点数が V_j 点に書き換えられます。同じ生徒に対して複数回の更新が行われることもあり、その場合は更新のたびに点数が上書きされます。
すべての更新が完了した後、点数が K 点未満の生徒は補習対象となります。高橋君のために、補習対象となる生徒の人数を求めてください。ただし、K 点ちょうどの生徒は補習対象に含まれません。
制約
- 1 \leq N \leq 10^5
- 0 \leq M \leq 10^5
- 0 \leq K \leq 100
- 0 \leq S_i \leq 100 (1 \leq i \leq N)
- 1 \leq P_j \leq N (1 \leq j \leq M)
- 0 \leq V_j \leq 100 (1 \leq j \leq M)
- 入力はすべて整数である
入力
N M K S_1 S_2 \cdots S_N P_1 V_1 P_2 V_2 \vdots P_M V_M
- 1 行目には、生徒の人数を表す N 、更新の回数を表す M 、補習の基準点を表す K が、スペース区切りで与えられる。
- 2 行目には、各生徒の初期の点数を表す S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
- S_i は i 番目の生徒の初期の点数を表す。
- 3 行目から 2 + M 行目には、更新の内容が与えられる（M = 0 の場合、この部分は存在しない）。
- 2 + j 行目には、j 回目の更新で点数が変更される生徒の番号 P_j と、変更後の点数 V_j が、スペース区切りで与えられる。
出力
すべての更新が完了した後、点数が K 点未満である補習対象の生徒の人数を 1 行で出力してください。
入力例 1
5 3 60 45 72 58 81 39 1 65 3 62 5 55
出力例 1
1
入力例 2
3 0 50 30 50 70
出力例 2
1
入力例 3
10 6 70 85 42 67 91 55 78 63 49 72 88 2 75 4 68 5 70 7 71 8 45 2 69
出力例 3
4
Score : 233 pts
Problem Statement
Takahashi is managing student grades as the homeroom teacher of a school class. There are N students in the class, numbered from 1 to N. The initial score of the i-th student is S_i points.
At the end of the term, it is time to update the report cards. A total of M updates are performed. In the j-th update, the score of student P_j is changed to V_j points. The same student may be updated multiple times, in which case their score is overwritten with each update.
After all updates are completed, students with a score strictly less than K points are required to attend supplementary lessons. For Takahashi's sake, determine the number of students who are required to attend supplementary lessons. Note that students with exactly K points are not included.
Constraints
- 1 \leq N \leq 10^5
- 0 \leq M \leq 10^5
- 0 \leq K \leq 100
- 0 \leq S_i \leq 100 (1 \leq i \leq N)
- 1 \leq P_j \leq N (1 \leq j \leq M)
- 0 \leq V_j \leq 100 (1 \leq j \leq M)
- All input values are integers
Input
N M K S_1 S_2 \cdots S_N P_1 V_1 P_2 V_2 \vdots P_M V_M
- The first line contains N representing the number of students, M representing the number of updates, and K representing the threshold score for supplementary lessons, separated by spaces.
- The second line contains the initial scores S_1, S_2, \ldots, S_N of each student, separated by spaces.
- S_i represents the initial score of the i-th student.
- Lines 3 through 2 + M contain the details of the updates (if M = 0, this part does not exist).
- Line 2 + j contains the student number P_j whose score is changed in the j-th update and the new score V_j, separated by a space.
Output
After all updates are completed, output in a single line the number of students whose score is strictly less than K points and are therefore required to attend supplementary lessons.
Sample Input 1
5 3 60 45 72 58 81 39 1 65 3 62 5 55
Sample Output 1
1
Sample Input 2
3 0 50 30 50 70
Sample Output 2
1
Sample Input 3
10 6 70 85 42 67 91 55 78 63 49 72 88 2 75 4 68 5 70 7 71 8 45 2 69
Sample Output 3
4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は庭師として働いており、一列に並んだ花壇の手入れを任されています。
花壇は N 個あり、それぞれの花壇には 1 から N までの番号が付けられています。各花壇 i（ 1 \leq i \leq N ）には、現在 A_i 本の花が植えられています。
高橋君の上司によると、花壇の列が美しい状態であるための条件は「すべての隣り合う花壇について、花の本数の差の絶対値が K 以下であること」だそうです。すなわち、手入れ後の各花壇 i の花の本数を B_i としたとき、すべての i（ 1 \leq i \leq N - 1 ）について |B_i - B_{i+1}| \leq K が成り立つとき、花壇の列は美しいとみなされます。
高橋君は新しく花を植えることはできますが、すでに植えられている花を抜くことはできません。具体的には、各花壇 i に対して 0 本以上の花を追加し、花の本数を A_i 本から B_i 本に増やすことができます。ここで、各 B_i は B_i \geq A_i を満たす整数でなければなりません。
高橋君は、花壇の列を美しい状態にするために追加する花の合計本数 \displaystyle\sum_{i=1}^{N} (B_i - A_i) を最小化したいと考えています。この最小値を求めてください。
なお、すべての B_i を十分大きな同じ値にすれば条件を満たせるため、花の追加のみで美しい状態にすることは常に可能です。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、花壇の数を表す整数 N と、隣り合う花壇間で許容される花の本数の差を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各花壇 i に現在植えられている花の本数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
花壇の列を美しい状態にするために追加が必要な花の合計本数の最小値を 1 行で出力せよ。
入力例 1
3 2 1 5 3
出力例 1
2
入力例 2
5 3 2 4 5 3 1
出力例 2
0
入力例 3
7 10 5 30 15 50 20 100 85
出力例 3
235
Score : 333 pts
Problem Statement
Takahashi works as a gardener and is in charge of maintaining a row of flower beds.
There are N flower beds, each numbered from 1 to N. Each flower bed i (1 \leq i \leq N) currently has A_i flowers planted in it.
According to Takahashi's boss, the condition for the row of flower beds to be in a beautiful state is that "for all adjacent flower beds, the absolute difference in the number of flowers is at most K." In other words, if we denote the number of flowers in each flower bed i after maintenance as B_i, then the row of flower beds is considered beautiful when |B_i - B_{i+1}| \leq K holds for all i (1 \leq i \leq N - 1).
Takahashi can plant new flowers but cannot remove flowers that are already planted. Specifically, for each flower bed i, he can add 0 or more flowers to increase the number of flowers from A_i to B_i. Here, each B_i must be an integer satisfying B_i \geq A_i.
Takahashi wants to minimize the total number of flowers added \displaystyle\sum_{i=1}^{N} (B_i - A_i) in order to make the row of flower beds beautiful. Find this minimum value.
Note that it is always possible to achieve a beautiful state by only adding flowers, since the condition can be satisfied by setting all B_i to the same sufficiently large value.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of flower beds and an integer K representing the allowed difference in the number of flowers between adjacent flower beds, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the number of flowers currently planted in each flower bed i, separated by spaces.
Output
Output in one line the minimum total number of flowers that need to be added to make the row of flower beds beautiful.
Sample Input 1
3 2 1 5 3
Sample Output 1
2
Sample Input 2
5 3 2 4 5 3 1
Sample Output 2
0
Sample Input 3
7 10 5 30 15 50 20 100 85
Sample Output 3
235
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は運送会社で配達計画を担当しています。
今日は N 個の荷物を K 台のトラックで配達する計画を立てる必要があります。
各荷物には 1 から N までの番号が付けられており、荷物 i の重さは A_i です。
配達の効率化のため、荷物 1, 2, \ldots, N をこの順に並べた列を、それぞれ 1 個以上の荷物からなる K 個の連続区間に分割し、各区間の荷物をそれぞれ 1 台のトラックに割り当てることにしました。すべての荷物はちょうど 1 つの区間に属し、K 個の区間と K 台のトラックは 1 対 1 に対応します。
各トラックについて、そのトラックに割り当てられた荷物の重さの合計を、そのトラックの 負担量 と呼ぶことにします。
高橋君は、K 台のトラックの負担量のうち最も小さい値をできるだけ大きくしたいと考えています。
すべての分割方法を考えたとき、「K 台のトラックの負担量の最小値」として達成可能な最大値を求めてください。
制約
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、荷物の個数を表す整数 N と、トラックの台数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各荷物の重さを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
最適な分割を行ったときの、K 台のトラックの負担量の最小値として達成可能な最大値を 1 行で出力してください。
入力例 1
5 2 1 2 3 4 5
出力例 1
6
入力例 2
7 3 3 1 4 1 5 9 2
出力例 2
6
入力例 3
10 4 100 200 150 300 50 250 400 100 350 200
出力例 3
450
Score : 400 pts
Problem Statement
Takahashi is in charge of delivery planning at a shipping company.
Today, he needs to create a plan to deliver N packages using K trucks.
Each package is numbered from 1 to N, and the weight of package i is A_i.
To improve delivery efficiency, he decided to arrange the packages 1, 2, \ldots, N in this order and divide them into K contiguous segments, each containing at least 1 package, and assign the packages in each segment to one truck. Every package belongs to exactly one segment, and there is a one-to-one correspondence between the K segments and the K trucks.
For each truck, the sum of the weights of the packages assigned to that truck is called the load of that truck.
Takahashi wants to maximize the smallest load among the K trucks.
Considering all possible ways to divide the packages, find the maximum possible value of "the minimum load among the K trucks."
Constraints
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of packages and an integer K representing the number of trucks, separated by a space.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the weight of each package, separated by spaces.
Output
Print in one line the maximum possible value of the minimum load among the K trucks when the packages are divided optimally.
Sample Input 1
5 2 1 2 3 4 5
Sample Output 1
6
Sample Input 2
7 3 3 1 4 1 5 9 2
Sample Output 2
6
Sample Input 3
10 4 100 200 150 300 50 250 400 100 350 200
Sample Output 3
450
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は登山ガイドとして働いており、ある山脈にある N 個の山の情報を管理しています。山には 1 から N までの番号が付けられており、i 番目の山の標高は A_i メートルです（1 \leq i \leq N）。
高橋君のもとには、観光客から Q 個の問い合わせが届きました。j 番目（1 \leq j \leq Q）の問い合わせでは、L_j 番目から R_j 番目までの山が指定され、その中で最も標高が高い山の標高を知りたいという内容です。
各問い合わせに対して、指定された範囲の山の標高の最大値を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- 入力はすべて整数
入力
N Q A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 1 行目には、山の個数を表す整数 N と、問い合わせの個数を表す整数 Q が、スペース区切りで与えられる。
- 2 行目には、各山の標高を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- A_i は i 番目の山の標高（メートル）を表す。
- 続く Q 行のうち j 行目（1 \leq j \leq Q、入力全体では 2 + j 行目）には、j 番目の問い合わせで指定される範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。
出力
Q 行出力せよ。j 行目（1 \leq j \leq Q）には、j 番目の問い合わせに対する答え、すなわち L_j 番目から R_j 番目までの山の標高の最大値を出力せよ。
入力例 1
5 3 100 250 180 320 150 1 3 2 5 4 4
出力例 1
250 320 320
入力例 2
8 5 1500 2300 1800 3776 2500 1200 2800 1900 1 8 3 6 1 4 5 8 2 2
出力例 2
3776 3776 3776 2800 2300
入力例 3
15 10 500 1200 800 3500 2200 1800 4200 900 3100 2700 1500 4800 2000 3300 1100 1 15 1 7 7 12 10 15 3 5 6 10 12 12 1 1 8 14 5 9
出力例 3
4800 4200 4800 4800 3500 4200 4800 500 4800 4200
Score : 433 pts
Problem Statement
Takahashi works as a mountain guide and manages information about N mountains in a mountain range. The mountains are numbered from 1 to N, and the elevation of the i-th mountain is A_i meters (1 \leq i \leq N).
Takahashi has received Q queries from tourists. The j-th query (1 \leq j \leq Q) specifies the mountains from the L_j-th to the R_j-th, and asks for the highest elevation among them.
For each query, find the maximum elevation among the mountains in the specified range.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- All inputs are integers
Input
N Q A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- The first line contains an integer N representing the number of mountains and an integer Q representing the number of queries, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the elevations of each mountain, separated by spaces.
- A_i represents the elevation (in meters) of the i-th mountain.
- In the following Q lines, the j-th line (1 \leq j \leq Q, which is the (2 + j)-th line of the entire input) contains the left endpoint L_j and the right endpoint R_j of the range specified by the j-th query, separated by a space.
Output
Output Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to the j-th query, that is, the maximum elevation among the mountains from the L_j-th to the R_j-th.
Sample Input 1
5 3 100 250 180 320 150 1 3 2 5 4 4
Sample Output 1
250 320 320
Sample Input 2
8 5 1500 2300 1800 3776 2500 1200 2800 1900 1 8 3 6 1 4 5 8 2 2
Sample Output 2
3776 3776 3776 2800 2300
Sample Input 3
15 10 500 1200 800 3500 2200 1800 4200 900 3100 2700 1500 4800 2000 3300 1100 1 15 1 7 7 12 10 15 3 5 6 10 12 12 1 1 8 14 5 9
Sample Output 3
4800 4200 4800 4800 3500 4200 4800 500 4800 4200