AtCoder Weekday Contest 0151 Beta

A - 荷物の配送

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は配送センターの責任者で、M 件の届け先にすべての荷物を届けなければなりません。

配送センターには N 人のドライバーがいます。i 番目の届け先には A_i 個の荷物を届ける必要があります。

各ドライバーは複数の届け先の荷物を運ぶことができますが、1 人のドライバーが運ぶ荷物の個数の合計は K 個以下でなければなりません。同じ届け先の荷物を複数のドライバーで分担して届けることもできます。ただし、1 個の荷物をさらに分割することはできず、荷物は整数個単位で各ドライバーに割り当てます。荷物を運ばないドライバーがいても構いません。

すべての届け先のすべての荷物を、N 人のドライバーで漏れなく配送することが可能かどうか判定してください。

制約

1 \leq N \leq 10^9
1 \leq M \leq 10^5
1 \leq K \leq 10^9
1 \leq A_i \leq 10^9
入力はすべて整数である

入力

N M K
A_1
A_2
\vdots
A_M

1 行目には、ドライバーの人数 N、届け先の数 M、1 人のドライバーが運べる荷物の最大個数 K がスペース区切りで与えられます。続く M 行のうち i 行目には、i 番目の届け先の荷物の個数 A_i が与えられます。

出力

すべての荷物を配送することが可能であれば Yes を、不可能であれば No を 1 行に出力してください。

入力例 1

出力例 1

Yes

入力例 2

出力例 2

No

入力例 3

出力例 3

Yes

入力例 4

19 20 1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
999999999

出力例 4

No

入力例 5

1 1 1
1

出力例 5

Yes

Score : 200 pts

Problem Statement

Takahashi is the manager of a delivery center and must deliver all packages to M destinations.

The delivery center has N drivers. The i-th destination requires A_i packages to be delivered.

Each driver can carry packages for multiple destinations, but the total number of packages carried by a single driver must be at most K. Packages for the same destination can be split among multiple drivers. However, a single package cannot be further divided, and packages must be assigned to each driver in whole numbers. It is acceptable for some drivers to carry no packages.

Determine whether it is possible for the N drivers to deliver all packages to all destinations without any omissions.

Constraints

1 \leq N \leq 10^9
1 \leq M \leq 10^5
1 \leq K \leq 10^9
1 \leq A_i \leq 10^9
All input values are integers

Input

N M K
A_1
A_2
\vdots
A_M

The first line contains the number of drivers N, the number of destinations M, and the maximum number of packages a single driver can carry K, separated by spaces. The i-th of the following M lines contains A_i, the number of packages for the i-th destination.

Output

If it is possible to deliver all packages, print Yes; otherwise, print No on a single line.

Sample Input 1

Sample Output 1

Yes

Sample Input 2

Sample Output 2

No

Sample Input 3

Sample Output 3

Yes

Sample Input 4

19 20 1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
999999999

Sample Output 4

No

Sample Input 5

1 1 1
1

Sample Output 5

Yes

B - 不満を感じる回数

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君のクラスには N 人の生徒がいます。生徒にはそれぞれ 1 から N までの出席番号が割り振られています。高橋君の出席番号は 2 です。

ある日、先生はご褒美のシールを M 枚用意し、生徒たちに配ることにしました。最初、どの生徒もシールを 1 枚も持っていません。先生は M 枚のシールを 1 枚ずつ順番に配ります。配る順番は長さ M の数列 P_1, P_2, \dots, P_M で表され、i 枚目のシールは出席番号 P_i の生徒に渡されます。同じ生徒に複数回シールが渡されることもあります。

高橋君は負けず嫌いです。P_i = 2 のとき、すなわち i 枚目のシールが高橋君に渡されたとき、高橋君がそのシールを受け取った直後の時点で、高橋君以外の生徒の中に高橋君よりも厳密に多い枚数のシールを持っている生徒が 1 人でもいれば、高橋君は不満を 1 回感じます。高橋君と同数のシールを持っている生徒がいるだけでは不満を感じません。P_i \neq 2 のとき、すなわち高橋君以外の生徒にシールが渡されたときには、高橋君は不満を感じません。

なお、数列 P に 2 が含まれない（高橋君にシールが一度も渡されない）場合もあり得ます。この場合、高橋君が不満を感じる機会は一度もないため、答えは 0 です。

シールを M 枚すべて配り終えるまでに、高橋君が不満を感じる回数の合計を求めてください。

制約

2 \leq N \leq 3 \times 10^5
1 \leq M \leq 3 \times 10^5
1 \leq P_i \leq N (1 \leq i \leq M)
入力はすべて整数である

入力

N M
P_1 P_2 \dots P_M

1 行目には、生徒の人数を表す整数 N と、シールの枚数を表す整数 M が、スペース区切りで与えられる。
2 行目には、シールを配る順番を表す数列 P_1, P_2, \dots, P_M が、スペース区切りで与えられる。
P_i は i 枚目のシールを渡す生徒の出席番号であり、1 以上 N 以下の整数である。

出力

高橋君が不満を感じる回数の合計を 1 行で出力せよ。

入力例 1

3 6
1 1 2 1 2 2

出力例 1

入力例 2

5 10
1 3 3 2 1 3 2 4 2 5

出力例 2

入力例 3

5 12
1 3 4 1 3 2 1 2 5 5 2 2

出力例 3

Score : 300 pts

Problem Statement

There are N students in Takahashi's class. Each student is assigned a student number from 1 to N. Takahashi's student number is 2.

One day, the teacher prepared M stickers to distribute to the students. Initially, no student has any stickers. The teacher distributes the M stickers one at a time in order. The distribution order is represented by a sequence of length M: P_1, P_2, \dots, P_M, where the i-th sticker is given to the student with student number P_i. The same student may receive stickers multiple times.

Takahashi is competitive. When P_i = 2, that is, when the i-th sticker is given to Takahashi, if immediately after Takahashi receives that sticker there exists at least one student other than Takahashi who has strictly more stickers than Takahashi, then Takahashi feels frustrated once. He does not feel frustrated merely because some student has the same number of stickers as him. When P_i \neq 2, that is, when a sticker is given to a student other than Takahashi, Takahashi does not feel frustrated.

Note that it is possible that 2 does not appear in the sequence P (Takahashi never receives a sticker). In this case, Takahashi never has an opportunity to feel frustrated, so the answer is 0.

Find the total number of times Takahashi feels frustrated by the time all M stickers have been distributed.

Constraints

2 \leq N \leq 3 \times 10^5
1 \leq M \leq 3 \times 10^5
1 \leq P_i \leq N (1 \leq i \leq M)
All inputs are integers.

Input

N M
P_1 P_2 \dots P_M

The first line contains an integer N representing the number of students and an integer M representing the number of stickers, separated by a space.
The second line contains the sequence P_1, P_2, \dots, P_M representing the order of sticker distribution, separated by spaces.
P_i is the student number of the student who receives the i-th sticker, and is an integer between 1 and N, inclusive.

Output

Print the total number of times Takahashi feels frustrated, in a single line.

Sample Input 1

3 6
1 1 2 1 2 2

Sample Output 1

Sample Input 2

5 10
1 3 3 2 1 3 2 4 2 5

Sample Output 2

Sample Input 3

5 12
1 3 4 1 3 2 1 2 5 5 2 2

Sample Output 3

C - 温泉旅行の準備

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は旅行会社で働いており、N 人の顧客の温泉旅行への参加状況を管理しています。顧客にはそれぞれ 1 から N までの番号が付けられています。

各顧客は「旅行ポイント」を持っています。顧客 i の初期の旅行ポイントは A_i であり、旅行ポイントが閾値 T_i 以上であるとき、その顧客は旅行への参加を決定します。

高橋君は Q 回のキャンペーンを順に実施します。j 回目のキャンペーンでは、顧客番号が L_j 以上 R_j 以下であるすべての顧客の旅行ポイントを X_j だけ増加させます。

すべてのキャンペーンが終わった後の最終的な旅行ポイントが閾値以上になっている顧客の人数を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq 10^9
1 \leq L_j \leq R_j \leq N
1 \leq X_j \leq 10^9
入力はすべて整数である

入力

N Q
A_1 T_1
A_2 T_2
\vdots
A_N T_N
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q

1 行目には、顧客の数 N とキャンペーンの回数 Q が、スペース区切りで与えられる。
続く N 行では、各顧客の情報が与えられる。このうち i 行目では、顧客 i の初期旅行ポイント A_i と、参加を決定するポイントの閾値 T_i が、スペース区切りで与えられる。
続く Q 行では、各キャンペーンの情報が与えられる。このうち j 行目では、j 回目のキャンペーンの対象区間の左端 L_j 、右端 R_j 、増加させるポイント X_j が、スペース区切りで与えられる。

出力

すべてのキャンペーンが終わった後に旅行ポイントが閾値以上になっている顧客の人数を 1 行で出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

10 5
100 500
200 300
0 1000
450 451
999999999 1000000000
0 10
50 100
300 350
0 1
600 700
1 5 100
3 7 500
1 10 50
6 8 20
2 4 150

出力例 3

Score : 366 pts

Problem Statement

Takahashi works at a travel agency and manages the participation status of N customers for a hot spring trip. Each customer is assigned a number from 1 to N.

Each customer has "travel points." Customer i initially has A_i travel points, and when their travel points are at least the threshold T_i, that customer decides to participate in the trip.

Takahashi conducts Q campaigns in order. In the j-th campaign, the travel points of all customers whose numbers are between L_j and R_j (inclusive) are increased by X_j.

Determine the number of customers whose final travel points after all campaigns are at least their threshold.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
0 \leq A_i \leq 10^9
1 \leq T_i \leq 10^9
1 \leq L_j \leq R_j \leq N
1 \leq X_j \leq 10^9
All input values are integers

Input

N Q
A_1 T_1
A_2 T_2
\vdots
A_N T_N
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q

The first line contains the number of customers N and the number of campaigns Q, separated by a space.
The following N lines give information about each customer. The i-th of these lines contains customer i's initial travel points A_i and the threshold T_i for deciding to participate, separated by a space.
The following Q lines give information about each campaign. The j-th of these lines contains the left endpoint L_j, right endpoint R_j of the target range, and the points to increase X_j for the j-th campaign, separated by spaces.

Output

Print in one line the number of customers whose travel points are at least their threshold after all campaigns have been completed.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

10 5
100 500
200 300
0 1000
450 451
999999999 1000000000
0 10
50 100
300 350
0 1
600 700
1 5 100
3 7 500
1 10 50
6 8 20
2 4 150

Sample Output 3

D - 仕事の選択

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君はフリーランスのプログラマーで、複数の仕事の依頼を受けています。現在 N 件の仕事の候補があり、高橋君は 1 日目から M 日目までの M 日間の期間内でこれらの仕事に取り組むことができます。この期間外（M+1 日目以降）に作業を行うことはできません。

各仕事 i（ 1 \leq i \leq N ）には以下の情報が与えられます：

完了に必要な日数 D_i
完了時に得られる報酬 V_i
納期 T_i

高橋君は同時に 1 つの仕事しかこなせず、各仕事は最大 1 回しか引き受けられません。ある仕事に取りかかったら、途中で中断することはできず、 D_i 日間連続で作業する必要があります。仕事 i を s 日目（ s \geq 1 ）に開始した場合、 s, s+1, \ldots, s + D_i - 1 日目に作業を行い、 s + D_i - 1 日目に完了となります。次の仕事は最も早くて s + D_i 日目から開始できます。

仕事 i を引き受ける場合、納期 T_i 日目までに完了しなければなりません。すなわち、開始日を s としたとき、 s + D_i - 1 \leq T_i を満たす必要があります。制約より T_i \leq M が保証されているため、納期を守れば作業は自動的に M 日間の期間内に収まります。

高橋君は N 件の候補から仕事の部分集合を選び、選んだ仕事すべてをそれぞれの納期以内に完了できるように作業順序とスケジュールを決めます。仕事を一つも引き受けないことも可能で、その場合の報酬の合計は 0 です。

また、特別なルールがあります。高橋君が完了した仕事の数が K 個以上のとき、クライアントからの信頼ボーナスとして追加で B が得られます。このボーナスは条件を満たせば一度だけ加算され、完了した仕事が K 個以上であれば何個であっても加算額は B で一定です。

高橋君が最終的に得る報酬は、完了した仕事の報酬 V_i の総和に、ボーナス条件を満たしていれば B を加えたものです。引き受ける仕事の集合とその作業順序を適切に選ぶことで、この最終的な報酬の最大値を求めてください。

制約

1 \leq N \leq 200
1 \leq M \leq 5000
1 \leq K \leq N
0 \leq B \leq 10^9
1 \leq D_i \leq M
1 \leq V_i \leq 10^9
1 \leq T_i \leq M
入力はすべて整数

入力

N M K B
D_1 V_1 T_1
D_2 V_2 T_2
\vdots
D_N V_N T_N

1 行目には、仕事の候補数を表す N 、期間の日数を表す M 、ボーナス条件の仕事数を表す K 、ボーナスの値を表す B が、スペース区切りで与えられる。
2 行目から N + 1 行目では、各仕事の情報が N 行で与えられる。
1 + i 行目では、仕事 i の完了に必要な日数 D_i 、報酬 V_i 、納期 T_i がスペース区切りで与えられる。

出力

得られる報酬の合計（ボーナスを含む）の最大値を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

10 30 5 200
3 80 5
5 120 12
2 50 6
7 200 20
4 90 15
6 150 18
1 20 3
8 300 30
3 70 10
5 110 25

出力例 3

入力例 4

25 100 12 1000
4 120 10
8 260 20
3 90 12
10 400 35
6 180 25
12 500 50
5 150 30
7 230 40
2 60 15
9 310 55
11 450 70
4 140 45
6 210 60
13 520 85
3 100 33
15 700 100
5 170 65
8 280 75
1 30 22
10 360 90
6 190 48
7 240 58
14 600 95
2 80 38
9 330 82

出力例 4

入力例 5

1 1 1 1000000000
1 1000000000 1

出力例 5

2000000000

Score : 400 pts

Problem Statement

Takahashi is a freelance programmer who has received multiple job requests. Currently there are N job candidates, and Takahashi can work on these jobs within a period of M days from day 1 to day M. He cannot perform any work outside this period (from day M+1 onwards).

For each job i (1 \leq i \leq N), the following information is given:

Number of days required to complete: D_i
Reward upon completion: V_i
Deadline: T_i

Takahashi can only work on 1 job at a time, and each job can be accepted at most once. Once he starts a job, he cannot interrupt it and must work on it for D_i consecutive days. If job i is started on day s (s \geq 1), he works on days s, s+1, \ldots, s + D_i - 1, and the job is completed on day s + D_i - 1. The next job can be started at the earliest on day s + D_i.

If job i is accepted, it must be completed by the deadline day T_i. That is, if the starting day is s, the condition s + D_i - 1 \leq T_i must be satisfied. Since the constraints guarantee T_i \leq M, meeting the deadline automatically ensures the work falls within the M-day period.

Takahashi selects a subset of jobs from the N candidates and determines the work order and schedule so that all selected jobs can be completed within their respective deadlines. It is also possible to accept no jobs at all, in which case the total reward is 0.

Additionally, there is a special rule. When the number of jobs Takahashi has completed is K or more, he receives an additional trust bonus of B from the clients. This bonus is added only once if the condition is met, and regardless of how many jobs are completed (as long as it is K or more), the bonus amount is a fixed B.

Takahashi's final reward is the sum of the rewards V_i of all completed jobs, plus B if the bonus condition is satisfied. Find the maximum value of this final reward by appropriately choosing the set of jobs to accept and their work order.

Constraints

1 \leq N \leq 200
1 \leq M \leq 5000
1 \leq K \leq N
0 \leq B \leq 10^9
1 \leq D_i \leq M
1 \leq V_i \leq 10^9
1 \leq T_i \leq M
All inputs are integers

Input

N M K B
D_1 V_1 T_1
D_2 V_2 T_2
\vdots
D_N V_N T_N

The first line contains N representing the number of job candidates, M representing the number of days in the period, K representing the number of jobs required for the bonus condition, and B representing the bonus value, separated by spaces.
From the 2nd line to the (N+1)-th line, the information for each job is given over N lines.
The (1+i)-th line contains the number of days D_i required to complete job i, the reward V_i, and the deadline T_i, separated by spaces.

Output

Output the maximum total reward (including the bonus) in a single line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

10 30 5 200
3 80 5
5 120 12
2 50 6
7 200 20
4 90 15
6 150 18
1 20 3
8 300 30
3 70 10
5 110 25

Sample Output 3

Sample Input 4

25 100 12 1000
4 120 10
8 260 20
3 90 12
10 400 35
6 180 25
12 500 50
5 150 30
7 230 40
2 60 15
9 310 55
11 450 70
4 140 45
6 210 60
13 520 85
3 100 33
15 700 100
5 170 65
8 280 75
1 30 22
10 360 90
6 190 48
7 240 58
14 600 95
2 80 38
9 330 82

Sample Output 4

Sample Input 5

1 1 1 1000000000
1 1000000000 1

Sample Output 5

2000000000

E - ネットワークの巡回点検

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、N 台のサーバーからなるネットワークの点検を担当しています。各サーバーには 1 から N までの番号が付けられています。

高橋君は、以下の手順に従ってすべてのサーバーを点検します。

未点検のサーバーのうち番号が最小のものを s とする。サーバー s を点検し、ここから新たな巡回を開始する。手順 2 に進む。
現在いるサーバー（直前に点検したサーバー）の番号を k とする。

k = 1 の場合： 1 は素因数を持たないため、特別に扱う。番号が k より大きい未点検のサーバーが存在すれば、その中で番号が最小のサーバーに移動して点検し、手順 2 を繰り返す。存在しなければ、この巡回を終了し、手順 3 に進む。
k \geq 2 の場合： 番号が k より大きい未点検のサーバーのうち、番号と k が共通の素因数を少なくとも 1 つ持つ（すなわち、番号を m として \gcd(k, m) \geq 2 である）ものを考える。そのようなサーバーが存在すれば、その中で番号が最小のサーバーに移動して点検し、手順 2 を繰り返す。存在しなければ、この巡回を終了し、手順 3 に進む。

未点検のサーバーが残っていれば手順 1 に戻り、新たな巡回を開始する。すべてのサーバーを点検していれば終了する。

高橋君が巡回を開始した回数、すなわち手順 1 が実行された回数を求めてください。

制約

1 \leq N \leq 5 \times 10^5
N は整数である。

入力

1 行目には、サーバーの台数を表す整数 N が与えられる。

出力

高橋君が巡回を開始した回数を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

出力例 5

Score : 466 pts

Problem Statement

Takahashi is in charge of inspecting a network consisting of N servers. The servers are numbered from 1 to N.

Takahashi inspects all the servers according to the following procedure:

Let s be the uninspected server with the smallest number. Inspect server s, and start a new patrol from here. Go to Step 2.
Let k be the current server (the server inspected most recently).

If k = 1: Since 1 has no prime factors, it is treated as a special case. If there exists an uninspected server with a number greater than k, move to the one with the smallest number among them, inspect it, and repeat Step 2. If no such server exists, end this patrol and go to Step 3.
If k \geq 2: Consider the uninspected servers with numbers greater than k that share at least one prime factor with k (that is, letting the server's number be m, \gcd(k, m) \geq 2). If such servers exist, move to the one with the smallest number among them, inspect it, and repeat Step 2. If no such server exists, end this patrol and go to Step 3.

If there are still uninspected servers, return to Step 1 and start a new patrol. If all servers have been inspected, terminate the process.

Find the number of times Takahashi started a patrol, which is the number of times Step 1 was executed.