Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君と青木君は、文化祭の模擬店で N 種類のお菓子を販売するために準備をしています。
i 番目の種類のお菓子について、高橋君が A_i 個、青木君が B_i 個を持ち寄りました。同じ種類のお菓子であれば、高橋君のものと青木君のものに区別はなく、合わせて A_i + B_i 個として扱います。
これらのお菓子をすべて箱に詰めて販売ブースへ運びます。
箱は必要なだけいくつでも用意できます。1 つの箱にはお菓子を 1 個以上 K 個以下入れることができますが、異なる種類のお菓子を同じ箱に入れることはできません。
ある種類のお菓子の合計が 0 個の場合、その種類のために箱を使う必要はありません。
すべてのお菓子を余りなく箱に詰めるために必要な箱の数の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9
- 0 \leq B_i \leq 10^9
- 入力はすべて整数である
- この制約の下で、答えは 64-bit 符号付き整数に収まる
入力
入力は以下の形式で与えられる。
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
1 行目には、お菓子の種類数 N と、1 箱あたりに入れられるお菓子の最大個数 K がスペース区切りで与えられる。
続く N 行のうち i 行目には、i 番目の種類について高橋君が用意した個数 A_i と青木君が用意した個数 B_i がスペース区切りで与えられる。
出力
すべてのお菓子を運ぶために必要な箱の数の最小値を 1 行で出力してください。
入力例 1
3 5 1 2 4 0 3 5
出力例 1
4
入力例 2
4 3 0 0 1 2 3 0 2 5
出力例 2
5
入力例 3
8 7 2 3 7 0 6 6 0 5 14 1 8 13 0 0 20 4
出力例 3
15
入力例 4
15 10 100 0 0 1 9 9 10 10 123 456 999999999 1 500000000 500000000 17 23 0 0 42 58 1000000000 1000000000 314159265 271828182 5 4 19 0 0 999999999
出力例 4
558598835
入力例 5
1 1000000000 0 0
出力例 5
0
Score : 233 pts
Problem Statement
Takahashi and Aoki are preparing to sell N types of sweets at their booth for the school cultural festival.
For the i-th type of sweet, Takahashi brought A_i pieces and Aoki brought B_i pieces. Sweets of the same type are indistinguishable regardless of who brought them, so they are treated as a combined total of A_i + B_i pieces.
All of these sweets must be packed into boxes and carried to the sales booth.
As many boxes as needed are available. Each box can hold between 1 and K sweets (inclusive), but sweets of different types cannot be placed in the same box.
If the total number of sweets of a certain type is 0, no boxes need to be used for that type.
Find the minimum number of boxes required to pack all the sweets with none left over.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9
- 0 \leq B_i \leq 10^9
- All input values are integers
- Under these constraints, the answer fits in a 64-bit signed integer
Input
The input is given in the following format.
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
The first line contains the number of types of sweets N and the maximum number of sweets per box K, separated by a space.
Each of the following N lines contains, for the i-th type, the number of pieces A_i prepared by Takahashi and the number of pieces B_i prepared by Aoki, separated by a space.
Output
Print the minimum number of boxes required to carry all the sweets, on a single line.
Sample Input 1
3 5 1 2 4 0 3 5
Sample Output 1
4
Sample Input 2
4 3 0 0 1 2 3 0 2 5
Sample Output 2
5
Sample Input 3
8 7 2 3 7 0 6 6 0 5 14 1 8 13 0 0 20 4
Sample Output 3
15
Sample Input 4
15 10 100 0 0 1 9 9 10 10 123 456 999999999 1 500000000 500000000 17 23 0 0 42 58 1000000000 1000000000 314159265 271828182 5 4 19 0 0 999999999
Sample Output 4
558598835
Sample Input 5
1 1000000000 0 0
Sample Output 5
0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君はプログラミングの勉強を始めました。彼が使っている学習サイトには N 個の練習問題があり、それぞれの問題には難易度が設定されています。i 番目の問題の難易度は D_i です。
高橋君の現在のスキルレベルは S です。高橋君が問題を解くと、その問題の難易度の分だけスキルレベルが上昇します。ただし、高橋君は現在のスキルレベル以下の難易度の問題しか解くことができません。
高橋君は、目標スキルレベル T に到達することを目指しています。
高橋君は各問題を最大 1 回ずつ解くことができます。高橋君が適切に問題を選んで解いたとき、最終的なスキルレベルを目標スキルレベル T 以上にすることができるかどうかを判定してください。
できる場合は Yes を、できない場合は No を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq S \leq T \leq 10^{18}
- 1 \leq D_i \leq 10^{9}
- 入力はすべて整数
入力
N S T D_1 D_2 \ldots D_N
- 1 行目には、問題の個数を表す N 、高橋君の初期スキルレベルを表す S 、目標スキルレベルを表す T が、スペース区切りで与えられる。
- 2 行目には、各問題の難易度を表す D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
出力
高橋君の最終的なスキルレベルを T 以上にできる場合は Yes を、できない場合は No を 1 行で出力せよ。
入力例 1
5 3 20 2 3 5 8 1
出力例 1
Yes
入力例 2
3 1 100 5 10 20
出力例 2
No
入力例 3
10 5 50 3 7 2 8 4 15 6 1 12 9
出力例 3
Yes
入力例 4
15 10 1000000000000000000 999999999 1000000000 500000000 800000000 200000000 100000000 50000000 10 5 3 2 1 7 8 4
出力例 4
No
入力例 5
1 1 1 1
出力例 5
Yes
Score : 333 pts
Problem Statement
Takahashi has started studying programming. The learning site he uses has N practice problems, each with an assigned difficulty level. The difficulty of the i-th problem is D_i.
Takahashi's current skill level is S. When Takahashi solves a problem, his skill level increases by the difficulty of that problem. However, Takahashi can only solve problems whose difficulty is less than or equal to his current skill level.
Takahashi aims to reach a target skill level of T.
Takahashi can solve each problem at most once. Determine whether Takahashi can reach a final skill level of at least T by choosing and solving problems appropriately.
If he can, output Yes; otherwise, output No.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq S \leq T \leq 10^{18}
- 1 \leq D_i \leq 10^{9}
- All inputs are integers.
Input
N S T D_1 D_2 \ldots D_N
- The first line contains N, the number of problems, S, Takahashi's initial skill level, and T, the target skill level, separated by spaces.
- The second line contains the difficulties of each problem, D_1, D_2, \ldots, D_N, separated by spaces.
Output
If Takahashi's final skill level can be made at least T, output Yes; otherwise, output No on a single line.
Sample Input 1
5 3 20 2 3 5 8 1
Sample Output 1
Yes
Sample Input 2
3 1 100 5 10 20
Sample Output 2
No
Sample Input 3
10 5 50 3 7 2 8 4 15 6 1 12 9
Sample Output 3
Yes
Sample Input 4
15 10 1000000000000000000 999999999 1000000000 500000000 800000000 200000000 100000000 50000000 10 5 3 2 1 7 8 4
Sample Output 4
No
Sample Input 5
1 1 1 1
Sample Output 5
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君が社長を務める会社では、N 人の社員がおり、それぞれ番号 1 から N が割り振られています。この会社では D ヶ月にわたってボーナスを支給します。
各社員 i（1 \leq i \leq N）には「貢献度」を表す正整数 P_i が定められており、貢献度の合計を S = P_1 + P_2 + \cdots + P_N とします。
各月 j（1 \leq j \leq D）において、会社全体のボーナス原資は W_j です。この原資は、各社員の貢献度の比率に従って分配されます。すなわち、月 j に社員 i が受け取るボーナスの額は
\frac{P_i \times W_j}{S}
です。
D ヶ月が終了した後、社員 i が受け取ったボーナスの総額は
T_i = \frac{P_i}{S} \times \sum_{j=1}^{D} W_j
となります。
青木君は経理担当として、全社員のボーナス総額の 積
R = \prod_{i=1}^{N} T_i
を計算したいと考えています。
R は 0 以上の有理数です。R を既約分数 \frac{A}{B}（A \geq 0, B > 0, \gcd(A, B) = 1）で表してください。特に R = 0 のときは A = 0, B = 1 とします。
このとき、A \times B^{-1} \bmod 998244353 を求めてください。ここで B^{-1} は 998244353 を法とする B のモジュラ逆元を表します。
なお、この問題の制約のもとで B は 998244353 と互いに素であること、すなわちモジュラ逆元が常に存在することが保証されます。
制約
- 1 \leq N \leq 10^6
- 1 \leq D \leq 10^6
- 1 \leq P_i \leq 10^9（1 \leq i \leq N）
- 0 \leq W_j \leq 10^9（1 \leq j \leq D）
- S = P_1 + P_2 + \cdots + P_N は 998244353 の倍数ではない。
- 入力はすべて整数である。
入力
N D P_1 P_2 \cdots P_N W_1 W_2 \cdots W_D
- 1 行目には、社員の人数 N と月数 D が、スペース区切りで与えられる。
- 2 行目には、各社員の貢献度 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
- 3 行目には、各月のボーナス原資 W_1, W_2, \ldots, W_D が、スペース区切りで与えられる。
出力
R を既約分数 \frac{A}{B} で表したときの A \times B^{-1} \bmod 998244353 の値を、0 以上 998244353 未満の整数として 1 行で出力せよ。
入力例 1
2 2 1 1 2 2
出力例 1
4
入力例 2
3 3 1 2 3 0 0 0
出力例 2
0
入力例 3
5 4 1 2 3 4 5 10 20 30 40
出力例 3
211088321
入力例 4
10 10 3 7 2 5 11 4 8 6 9 1 100 200 150 300 50 175 225 125 275 80
出力例 4
953616835
入力例 5
1 1 1 5
出力例 5
5
Score : 366 pts
Problem Statement
At the company where Takahashi serves as president, there are N employees, each assigned a number from 1 to N. This company pays bonuses over a period of D months.
Each employee i (1 \leq i \leq N) has a positive integer P_i representing their "contribution level," and the total contribution is S = P_1 + P_2 + \cdots + P_N.
In each month j (1 \leq j \leq D), the company's total bonus fund is W_j. This fund is distributed according to the ratio of each employee's contribution level. That is, the bonus amount that employee i receives in month j is
\frac{P_i \times W_j}{S}
After D months have concluded, the total bonus received by employee i is
T_i = \frac{P_i}{S} \times \sum_{j=1}^{D} W_j
Aoki, as the accounting manager, wants to compute the product of all employees' total bonuses:
R = \prod_{i=1}^{N} T_i
R is a non-negative rational number. Express R as an irreducible fraction \frac{A}{B} (A \geq 0, B > 0, \gcd(A, B) = 1). In particular, when R = 0, let A = 0 and B = 1.
Compute A \times B^{-1} \bmod 998244353, where B^{-1} denotes the modular inverse of B modulo 998244353.
It is guaranteed that under the constraints of this problem, B is coprime with 998244353, meaning the modular inverse always exists.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq D \leq 10^6
- 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq W_j \leq 10^9 (1 \leq j \leq D)
- S = P_1 + P_2 + \cdots + P_N is not a multiple of 998244353.
- All input values are integers.
Input
N D P_1 P_2 \cdots P_N W_1 W_2 \cdots W_D
- The first line contains the number of employees N and the number of months D, separated by a space.
- The second line contains the contribution levels P_1, P_2, \ldots, P_N of each employee, separated by spaces.
- The third line contains the bonus funds W_1, W_2, \ldots, W_D for each month, separated by spaces.
Output
Output the value of A \times B^{-1} \bmod 998244353, where R is expressed as the irreducible fraction \frac{A}{B}, as a single integer between 0 (inclusive) and 998244353 (exclusive) on one line.
Sample Input 1
2 2 1 1 2 2
Sample Output 1
4
Sample Input 2
3 3 1 2 3 0 0 0
Sample Output 2
0
Sample Input 3
5 4 1 2 3 4 5 10 20 30 40
Sample Output 3
211088321
Sample Input 4
10 10 3 7 2 5 11 4 8 6 9 1 100 200 150 300 50 175 225 125 275 80
Sample Output 4
953616835
Sample Input 5
1 1 1 5
Sample Output 5
5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、 N 個のお菓子が一列に並んでいる箱を持っています。左から i 番目のお菓子の重さは A_i グラムです。
高橋君は、この箱から連続して並んでいる 1 個以上のお菓子を選んで袋に詰め、 K 人の友達にプレゼントしようと考えています。友達全員に同じ重さずつ配りたいので、選んだお菓子の重さの合計が K グラムの倍数である必要があります。
連続して並んだ 1 個以上のお菓子の選び方であって、選んだお菓子の重さの合計が K の倍数となるものが何通りあるか求めてください。ただし、選んだお菓子の範囲（開始位置または終了位置）が異なれば、重さの合計が同じであっても異なる選び方として数えます。
制約
- 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 行目には、各お菓子の重さ A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
選んだお菓子の重さの合計が K の倍数となるような、連続する 1 個以上のお菓子の選び方の個数を 1 行で出力してください。
入力例 1
5 3 1 2 3 1 2
出力例 1
7
入力例 2
8 5 2 3 5 1 4 2 3 5
出力例 2
16
入力例 3
10 1000000000 500000000 500000000 300000000 700000000 100000000 900000000 400000000 600000000 200000000 800000000
出力例 3
15
Score : 400 pts
Problem Statement
Takahashi has a box containing N sweets lined up in a row. The weight of the i-th sweet from the left is A_i grams.
Takahashi wants to select one or more consecutive sweets from this box, pack them into a bag, and give them as a present to his K friends. Since he wants to distribute the sweets equally by weight to all his friends, the total weight of the selected sweets must be a multiple of K grams.
Find the number of ways to select one or more consecutive sweets such that the total weight of the selected sweets is a multiple of K. Note that if the ranges of selected sweets differ (i.e., the starting position or ending position differs), they are counted as different selections even if the total weights are the same.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \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 the number of sweets N and the number of friends K, separated by a space.
- The second line contains the weights of each sweet A_1, A_2, \ldots, A_N, separated by spaces.
Output
Print in one line the number of ways to select one or more consecutive sweets such that the total weight of the selected sweets is a multiple of K.
Sample Input 1
5 3 1 2 3 1 2
Sample Output 1
7
Sample Input 2
8 5 2 3 5 1 4 2 3 5
Sample Output 2
16
Sample Input 3
10 1000000000 500000000 500000000 300000000 700000000 100000000 900000000 400000000 600000000 200000000 800000000
Sample Output 3
15
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は、大学生活の傍らでアルバイトをしています。彼の働くお店は繁盛しており、毎日シフトに入ってほしいと頼まれています。
高橋君はこれから N 日間のシフトを組もうとしています。i 日目 (1 \leq i \leq N) について、高橋君はその日に働くか休むかを選びます。i 日目に働いた場合、A_i 円の給料を得られます。休んだ場合、給料は得られません。
しかし、アルバイトばかりしていると学業に支障が出るため、連続して働く日数は K - 1 日以下でなければなりません。すなわち、連続して K 日以上働くようなシフトは組めません。
また、高橋君はお金を稼ぎたいので、連続して休む日数は M - 1 日以下でなければなりません。すなわち、連続して M 日以上休むようなシフトも組めません。
ここで、連続する日数は N 日間の範囲内のみで数えます。1 日目より前や N 日目より後の状態は存在しないものとし、考慮しません。
上記の 2 つの条件をともに満たすシフトの組み方が存在する場合、高橋君が N 日間で得られる給料の合計の最大値を求めてください。条件を満たすシフトの組み方が存在しない場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq K \leq N + 1
- 2 \leq M \leq N + 1
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N K M A_1 A_2 \ldots A_N
- 1 行目には、シフトを組む日数 N、連続勤務日数に関する制約 K、連続休暇日数に関する制約 M が、スペース区切りで与えられる。連続して K 日以上働くことはできず、連続して M 日以上休むこともできない。
- 2 行目には、各日の給料 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- A_i は i 日目に働いた場合に得られる給料である。
出力
条件を満たすシフトの組み方が存在する場合は、高橋君が得られる給料の合計の最大値を 1 行で出力してください。条件を満たすシフトの組み方が存在しない場合は -1 を 1 行で出力してください。
入力例 1
5 3 2 3 5 2 7 4
出力例 1
19
入力例 2
7 3 3 10 2 8 6 1 9 3
出力例 2
36
入力例 3
15 4 3 12 5 8 20 3 15 7 11 9 18 6 14 2 10 16
出力例 3
137
Score : 466 pts
Problem Statement
Takahashi is working a part-time job alongside his university life. The store where he works is thriving, and he is asked to work every day.
Takahashi is trying to schedule his shifts for the next N days. For day i (1 \leq i \leq N), Takahashi chooses whether to work or take the day off. If he works on day i, he earns a salary of A_i yen. If he takes the day off, he earns no salary.
However, working too much would interfere with his studies, so the number of consecutive days he works must be at most K - 1 days. In other words, he cannot schedule shifts where he works K or more consecutive days.
Additionally, since Takahashi wants to earn money, the number of consecutive days he takes off must be at most M - 1 days. In other words, he cannot schedule shifts where he takes M or more consecutive days off.
Here, consecutive days are counted only within the range of the N days. The state before day 1 or after day N does not exist and is not considered.
If there exists a valid shift schedule that satisfies both of the above conditions, find the maximum total salary Takahashi can earn over the N days. If no valid shift schedule exists, output -1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq K \leq N + 1
- 2 \leq M \leq N + 1
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K M A_1 A_2 \ldots A_N
- The first line contains the number of days to schedule N, the constraint on consecutive working days K, and the constraint on consecutive days off M, separated by spaces. He cannot work K or more consecutive days, and cannot take M or more consecutive days off.
- The second line contains the salary for each day A_1, A_2, \ldots, A_N, separated by spaces.
- A_i is the salary earned if he works on day i.
Output
If a valid shift schedule satisfying the conditions exists, output the maximum total salary Takahashi can earn in one line. If no valid shift schedule exists, output -1 in one line.
Sample Input 1
5 3 2 3 5 2 7 4
Sample Output 1
19
Sample Input 2
7 3 3 10 2 8 6 1 9 3
Sample Output 2
36
Sample Input 3
15 4 3 12 5 8 20 3 15 7 11 9 18 6 14 2 10 16
Sample Output 3
137