実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は友人との待ち合わせに遅刻しないよう、準備を進めています。高橋君は出発前にいくつかの準備作業をすべて終わらせる必要があります。
待ち合わせに間に合うためには、遅くとも T 時 0 分には家を出発しなければなりません。
高橋君には N 個の準備作業があり、i 番目の作業を完了するには A_i 分かかります。高橋君は同じ日の S 時 0 分から準備を開始し、N 個の作業をそれぞれちょうど 1 回ずつ、休憩なしで連続して行います。すべての作業にかかる時間の合計は A_1 + A_2 + \cdots + A_N 分です。
すべての準備を終えた時刻が T 時 0 分以前であれば、高橋君は待ち合わせに間に合うように出発できます。
高橋君が T 時 0 分までにすべての準備を終えて出発できるかどうかを判定してください。
制約
- 1 \leq N \leq 100
- 0 \leq S \leq 23
- 0 \leq T \leq 23
- S \leq T
- 1 \leq A_i \leq 60 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N S T A_1 A_2 \ldots A_N
- 1 行目には、準備作業の個数を表す整数 N 、準備開始時刻（時）を表す整数 S 、出発期限の時刻（時）を表す整数 T が、スペース区切りで与えられる。
- 2 行目には、各作業にかかる時間（分）を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
高橋君が T 時 0 分までにすべての準備を終えて出発できる場合は Yes を、できない場合は No を出力してください。
入力例 1
3 9 10 15 20 10
出力例 1
Yes
入力例 2
5 14 17 45 30 25 40 50
出力例 2
No
入力例 3
10 6 12 30 25 45 15 20 35 40 10 50 60
出力例 3
Yes
Score : 200 pts
Problem Statement
Takahashi is preparing so that he won't be late for a meeting with his friend. Takahashi needs to finish several preparation tasks before leaving.
To make it to the meeting on time, he must leave his house by T o'clock 0 minutes at the latest.
Takahashi has N preparation tasks, and the i-th task takes A_i minutes to complete. Takahashi starts preparing at S o'clock 0 minutes on the same day, and performs each of the N tasks exactly once, consecutively without any breaks. The total time for all tasks is A_1 + A_2 + \cdots + A_N minutes.
If he finishes all preparations at or before T o'clock 0 minutes, Takahashi can leave in time for the meeting.
Determine whether Takahashi can finish all preparations and leave by T o'clock 0 minutes.
Constraints
- 1 \leq N \leq 100
- 0 \leq S \leq 23
- 0 \leq T \leq 23
- S \leq T
- 1 \leq A_i \leq 60 (1 \leq i \leq N)
- All inputs are integers
Input
N S T A_1 A_2 \ldots A_N
- The first line contains three space-separated integers: N, the number of preparation tasks; S, the hour at which preparation starts; and T, the hour of the departure deadline.
- The second line contains space-separated integers A_1, A_2, \ldots, A_N, representing the time (in minutes) each task takes.
Output
If Takahashi can finish all preparations and leave by T o'clock 0 minutes, print Yes; otherwise, print No.
Sample Input 1
3 9 10 15 20 10
Sample Output 1
Yes
Sample Input 2
5 14 17 45 30 25 40 50
Sample Output 2
No
Sample Input 3
10 6 12 30 25 45 15 20 35 40 10 50 60
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は、N 台のスマートフォンの充電状況を監視するシステムを開発しています。
時刻 0 において、各スマートフォン i（1 \leq i \leq N）のバッテリー残量は A_i mAh です。各スマートフォン i は、時刻 0 以降、B_i mAh/s の一定の速度でバッテリーを消費します。ただし、バッテリー残量は 0 mAh 未満にはなりません。
すなわち、時刻 t（t \geq 0）におけるスマートフォン i のバッテリー残量は \max(A_i - B_i \times t,\ 0) mAh です。
時刻 T における N 台すべてのスマートフォンのバッテリー残量の合計を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq T \leq 10^9
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力はすべて整数
入力
N T A_1 B_1 A_2 B_2 \vdots A_N B_N
- 1 行目には、スマートフォンの台数を表す整数 N と、バッテリー残量の合計を求めたい時刻を表す整数 T が、スペース区切りで与えられる。
- 2 行目から N+1 行目では、各スマートフォンの情報が与えられる。
- 1 + i 行目には、スマートフォン i の初期バッテリー残量を表す整数 A_i と、毎秒のバッテリー消費量を表す整数 B_i が、スペース区切りで与えられる。
出力
時刻 T における全てのスマートフォンのバッテリー残量の合計を整数として 1 行で出力せよ。
入力例 1
3 5 100 10 30 8 50 20
出力例 1
50
入力例 2
4 10 200 15 80 10 150 30 60 5
出力例 2
60
入力例 3
5 1000000000 1000000000 1 500000000 2 100 1000000000 999999999 1 1 1
出力例 3
0
Score : 233 pts
Problem Statement
Takahashi is developing a system to monitor the charging status of N smartphones.
At time 0, the battery level of each smartphone i (1 \leq i \leq N) is A_i mAh. Each smartphone i consumes battery at a constant rate of B_i mAh/s from time 0 onwards. However, the battery level does not go below 0 mAh.
That is, the battery level of smartphone i at time t (t \geq 0) is \max(A_i - B_i \times t,\ 0) mAh.
Find the total battery level of all N smartphones at time T.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq T \leq 10^9
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All inputs are integers
Input
N T A_1 B_1 A_2 B_2 \vdots A_N B_N
- The first line contains an integer N representing the number of smartphones and an integer T representing the time at which to calculate the total battery level, separated by a space.
- Lines 2 through N+1 give the information for each smartphone.
- Line 1 + i contains an integer A_i representing the initial battery level of smartphone i and an integer B_i representing the battery consumption per second, separated by a space.
Output
Output the total battery level of all smartphones at time T as an integer on a single line.
Sample Input 1
3 5 100 10 30 8 50 20
Sample Output 1
50
Sample Input 2
4 10 200 15 80 10 150 30 60 5
Sample Output 2
60
Sample Input 3
5 1000000000 1000000000 1 500000000 2 100 1000000000 999999999 1 1 1
Sample Output 3
0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は化学実験を行うことになりました。
この実験では N 個の試薬をすべて、それぞれちょうど1回ずつ処理する必要があります。試薬 i (1 \leq i \leq N) の処理温度は H_i 度です。
実験装置の温度は最初 0 度に設定されています。試薬を処理するには、装置の温度をその試薬の処理温度にちょうど一致させる必要があります。高橋君は試薬を処理する順番を自由に決めることができます。すべての試薬を処理した後、装置の温度を 0 度に戻して実験を終了します。
装置の温度を a 度から b 度へ変更するとき、エネルギー消費量は |a - b| です。
試薬を処理する順番を (p_1, p_2, \ldots, p_N)（(1, 2, \ldots, N) の順列）としたとき、エネルギー消費量の合計は
$$|H_{p_1}| + |H_{p_2} - H_{p_1}| + \cdots + |H_{p_N} - H_{p_{N-1}}| + |H_{p_N}|$$
です。ここで、第1項は開始時の 0 度から最初の試薬の処理温度への変更コスト、最終項は最後の試薬の処理温度から 0 度に戻すコストに対応します。
高橋君は、試薬を処理する順番を最適に選ぶことで、エネルギー消費量の合計を最小化したいと考えています。エネルギー消費量の合計の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq H_i \leq 10^9
- 入力はすべて整数
入力
N H_1 H_2 \cdots H_N
- 1 行目には、試薬の個数を表す整数 N が与えられる。
- 2 行目には、各試薬の処理温度を表す N 個の整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
出力
エネルギー消費量の合計の最小値を整数として 1 行で出力してください。
入力例 1
3 5 -3 2
出力例 1
16
入力例 2
5 10 -5 3 -8 7
出力例 2
36
入力例 3
8 100 -200 50 -150 300 -50 200 -100
出力例 3
1000
Score : 300 pts
Problem Statement
Takahashi is going to conduct a chemistry experiment.
In this experiment, he needs to process all N reagents, each exactly once. The processing temperature of reagent i (1 \leq i \leq N) is H_i degrees.
The temperature of the experimental apparatus is initially set to 0 degrees. To process a reagent, the apparatus temperature must be set to exactly match the processing temperature of that reagent. Takahashi can freely choose the order in which to process the reagents. After processing all reagents, he must return the apparatus temperature to 0 degrees to finish the experiment.
When changing the apparatus temperature from a degrees to b degrees, the energy consumption is |a - b|.
If the order of processing the reagents is (p_1, p_2, \ldots, p_N) (a permutation of (1, 2, \ldots, N)), the total energy consumption is
$$|H_{p_1}| + |H_{p_2} - H_{p_1}| + \cdots + |H_{p_N} - H_{p_{N-1}}| + |H_{p_N}|$$
Here, the first term corresponds to the cost of changing from the initial 0 degrees to the processing temperature of the first reagent, and the last term corresponds to the cost of returning from the processing temperature of the last reagent to 0 degrees.
Takahashi wants to minimize the total energy consumption by optimally choosing the order in which to process the reagents. Find the minimum total energy consumption.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq H_i \leq 10^9
- All inputs are integers
Input
N H_1 H_2 \cdots H_N
- The first line contains an integer N, representing the number of reagents.
- The second line contains N integers H_1, H_2, \ldots, H_N separated by spaces, representing the processing temperature of each reagent.
Output
Output the minimum total energy consumption as an integer on a single line.
Sample Input 1
3 5 -3 2
Sample Output 1
16
Sample Input 2
5 10 -5 3 -8 7
Sample Output 2
36
Sample Input 3
8 100 -200 50 -150 300 -50 200 -100
Sample Output 3
1000
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君はショッピングモールの駐車場管理システムを開発しています。この駐車場には N 台分の駐車スペースが一列に並んでおり、入口側から順にスペース 1 、スペース 2 、...、スペース N と番号が付けられています。
今日は M 台の車が来場する予定があり、これらの車はすべて同じ時間帯に駐車場を利用します。 i 番目の車（ 1 \leq i \leq M ）は、スペース L_i からスペース R_i までの連続する駐車スペースのうち、いずれか 1 つに駐車することができます。
各車にはちょうど 1 つの駐車スペースを割り当てなければならず、同じ駐車スペースに 2 台以上の車を割り当てることはできません。
すべての車に駐車スペースを割り当てることが可能であれば Yes を、不可能であれば No を出力してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq L_i \leq R_i \leq N （ 1 \leq i \leq M ）
- 入力はすべて整数である
入力
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
- 1 行目には、駐車スペースの数 N と来場する車の台数 M が、スペース区切りで与えられる。
- 続く M 行のうち i 行目には、 i 番目の車が駐車可能なスペースの範囲を表す L_i と R_i が、スペース区切りで与えられる。
出力
すべての車に駐車スペースを割り当てることが可能であれば Yes を、不可能であれば No を 1 行で出力せよ。
入力例 1
5 3 1 2 2 3 1 3
出力例 1
Yes
入力例 2
4 5 1 2 1 2 3 4 3 4 2 3
出力例 2
No
入力例 3
10 7 1 5 2 6 3 7 1 3 5 8 7 10 8 10
出力例 3
Yes
Score : 400 pts
Problem Statement
Takahashi is developing a parking lot management system for a shopping mall. The parking lot has N parking spaces arranged in a row, numbered Space 1, Space 2, ..., Space N from the entrance side.
Today, M cars are scheduled to visit, and all of these cars will use the parking lot during the same time period. The i-th car (1 \leq i \leq M) can park in any one of the consecutive parking spaces from Space L_i to Space R_i.
Each car must be assigned exactly one parking space, and no parking space can be assigned to two or more cars.
If it is possible to assign a parking space to every car, output Yes; otherwise, output No.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
- All input values are integers
Input
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
- The first line contains the number of parking spaces N and the number of arriving cars M, separated by a space.
- The i-th of the following M lines contains L_i and R_i, representing the range of spaces where the i-th car can park, separated by a space.
Output
Print Yes on a single line if it is possible to assign a parking space to every car, or No if it is not possible.
Sample Input 1
5 3 1 2 2 3 1 3
Sample Output 1
Yes
Sample Input 2
4 5 1 2 1 2 3 4 3 4 2 3
Sample Output 2
No
Sample Input 3
10 7 1 5 2 6 3 7 1 3 5 8 7 10 8 10
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は N 個の整数からなる数列 A = (A_1, A_2, \ldots, A_N) を持っています。各要素 A_i は負の値をとることもあります。
高橋君はこの数列から連続する区間を選び、その要素の総和がちょうど整数 K に等しくなるようにしたいと考えています。ここで K は目標とする総和の値です。そのような区間の選び方が何通りあるかを求めてください。
より正確には、1 \leq l \leq r \leq N を満たす整数の組 (l, r) であって、
$$A_l + A_{l+1} + \cdots + A_r = K$$
を満たすものの個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \cdots A_N
- 1 行目には、数列の要素数を表す整数 N と、目標とする総和の値を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、数列の各要素を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
条件を満たす整数の組 (l, r) の個数を 1 行で出力せよ。
入力例 1
5 5 1 2 3 4 5
出力例 1
2
入力例 2
6 3 1 -1 2 3 -2 4
出力例 2
3
入力例 3
10 0 1 -1 0 0 2 -2 0 3 -3 0
出力例 3
28
Score : 433 pts
Problem Statement
Takahashi has a sequence of N integers A = (A_1, A_2, \ldots, A_N). Each element A_i may take a negative value.
Takahashi wants to select a contiguous subarray from this sequence such that the sum of its elements is exactly equal to the integer K, where K is the target sum value. Find the number of ways to choose such a subarray.
More precisely, find the number of pairs of integers (l, r) satisfying 1 \leq l \leq r \leq N such that
$$A_l + A_{l+1} + \cdots + A_r = K$$
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \cdots A_N
- The first line contains the integer N representing the number of elements in the sequence and the integer K representing the target sum value, separated by a space.
- The second line contains the integers A_1, A_2, \ldots, A_N representing each element of the sequence, separated by spaces.
Output
Print the number of pairs of integers (l, r) that satisfy the condition, on a single line.
Sample Input 1
5 5 1 2 3 4 5
Sample Output 1
2
Sample Input 2
6 3 1 -1 2 3 -2 4
Sample Output 2
3
Sample Input 3
10 0 1 -1 0 0 2 -2 0 3 -3 0
Sample Output 3
28