AtCoder Weekday Contest 0163 Beta

A - 応援要請

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

配点 : 233 点

問題文

高橋君はイベント会場の設営リーダーです。今日は N 個のエリアにそれぞれ椅子を並べる作業があります。i 番目のエリアには A_i 脚の椅子を並べる必要があります。

椅子を並べる作業は 1 回の作業につき最大 K 脚 の椅子をまとめて運んで並べるというものです。ただし、1 回の作業では同一のエリアにしか椅子を運べません。したがって、i 番目のエリアの椅子をすべて並べるには \lceil A_i / K \rceil 回（A_i を K で割って切り上げた値）の作業が必要です。すべてのエリアの椅子を並べ終えるために必要な作業回数の合計は \displaystyle\sum_{i=1}^{N} \lceil A_i / K \rceil 回です。

高橋君のチームが今日中にこなせる作業回数の上限は、チーム全体の合計で M 回です。各作業をどのエリアに割り当てるかは自由です。

必要な作業回数の合計が M 回以下であれば、高橋君のチームだけで作業を完了できます。そうでない場合、高橋君は青木君に応援を要請します。応援要請 1 回につき、青木君が追加で 1 回の作業を行ってくれます。青木君の作業も上記と同じルールに従います（1 回の作業で最大 K 脚の椅子を同一のエリアに運んで並べる）。青木君が行った作業は高橋君のチームの上限 M 回には含まれず、青木君の作業をどのエリアに割り当てるかも自由です。応援の要請回数に上限はありませんが、高橋君は応援の要請回数をできるだけ少なく抑えたいと考えています。

すべてのエリアの椅子を並べ終えるために、高橋君が青木君に応援を要請する最小回数を求めてください。高橋君のチームだけですべての作業を完了できる場合は 0 を出力してください。

制約

1 \leq N \leq 10^6
0 \leq M \leq 10^{18}
1 \leq K \leq 10^9
1 \leq A_i \leq 10^9
入力はすべて整数

入力

N M K
A_1 A_2 \ldots A_N

1 行目には、エリアの数 N、高橋君のチーム全体が今日中にこなせる作業回数の上限 M、1 回の作業で運べる椅子の最大脚数 K が、スペース区切りで与えられる。
2 行目には、各エリアに並べる椅子の脚数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

すべてのエリアの椅子を並べ終えるために必要な応援要請の最小回数を 1 行で出力せよ。高橋君のチームだけですべての作業を完了できる場合は 0 を出力せよ。

入力例 1

3 3 4
7 3 6

出力例 1

入力例 2

3 10 3
3 6 9

出力例 2

入力例 3

5 7 5
12 8 15 3 20

出力例 3

入力例 4

10 5 3
100 200 300 400 500 600 700 800 900 1000

出力例 4

入力例 5

1 0 1
1

出力例 5

Score : 233 pts

Problem Statement

Takahashi is the setup leader for an event venue. Today, there is work to arrange chairs in each of N areas. The i-th area requires A_i chairs to be arranged.

The chair arrangement work involves carrying and arranging at most K chairs per single task. However, in a single task, chairs can only be carried to the same area. Therefore, arranging all the chairs in the i-th area requires \lceil A_i / K \rceil tasks (the value of A_i divided by K, rounded up). The total number of tasks needed to arrange all chairs in all areas is \displaystyle\sum_{i=1}^{N} \lceil A_i / K \rceil.

The maximum number of tasks that Takahashi's team can complete today is M in total for the entire team. They are free to assign each task to any area.

If the total number of required tasks is at most M, Takahashi's team can complete the work on their own. Otherwise, Takahashi requests backup from Aoki. For each backup request, Aoki performs one additional task. Aoki's tasks follow the same rules as above (carrying and arranging at most K chairs to the same area in one task). Tasks performed by Aoki are not counted toward Takahashi's team's limit of M tasks, and Aoki's tasks can be freely assigned to any area. There is no upper limit on the number of backup requests, but Takahashi wants to minimize the number of backup requests as much as possible.

Determine the minimum number of times Takahashi must request backup from Aoki in order to arrange all chairs in all areas. If Takahashi's team can complete all the work on their own, output 0.

Constraints

1 \leq N \leq 10^6
0 \leq M \leq 10^{18}
1 \leq K \leq 10^9
1 \leq A_i \leq 10^9
All inputs are integers

Input

N M K
A_1 A_2 \ldots A_N

The first line contains the number of areas N, the maximum number of tasks Takahashi's entire team can complete today M, and the maximum number of chairs that can be carried in one task K, separated by spaces.
The second line contains the number of chairs to be arranged in each area A_1, A_2, \ldots, A_N, separated by spaces.

Output

Output in a single line the minimum number of backup requests needed to arrange all chairs in all areas. If Takahashi's team can complete all the work on their own, output 0.

Sample Input 1

3 3 4
7 3 6

Sample Output 1

Sample Input 2

3 10 3
3 6 9

Sample Output 2

Sample Input 3

5 7 5
12 8 15 3 20

Sample Output 3

Sample Input 4

10 5 3
100 200 300 400 500 600 700 800 900 1000

Sample Output 4

Sample Input 5

1 0 1
1

Sample Output 5

B - ロープの収納

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

配点 : 300 点

問題文

高橋君は登山サークルに所属しており、活動で使用する長いロープの管理を担当しています。

サークルの倉庫には、長さ L センチメートルのロープが 1 本あります。このロープを収納ケースにしまうためには、ロープの長さを W センチメートル以下にする必要があります。

高橋君はロープを繰り返し二つ折りにすることで、収納ケースに収まる長さにしようと考えています。二つ折りとは、ロープ全体を半分の位置で折り返す操作です。現在の長さが x センチメートルのロープを 1 回二つ折りにすると、長さは \lceil x / 2 \rceil センチメートルになります。ここで \lceil y \rceil は y 以上の最小の整数（天井関数）を表します。これは、長さが奇数のときは折り目の位置がちょうど半分にならず、折り重なった 2 本のうち長い方の長さが全体の長さとなることに対応します。たとえば、長さが 7 のロープを二つ折りにすると長さは \lceil 7 / 2 \rceil = 4 に、長さが 8 のロープを二つ折りにすると長さは \lceil 8 / 2 \rceil = 4 になります。なお、折りたたんだことによる厚みは考慮しません。

ロープの長さを W センチメートル以下にするために必要な最小の折りたたみ回数を求めてください。最初から L \leq W であれば折りたたむ必要がないため、答えは 0 です。

制約

1 \leq L \leq 10^{18}
1 \leq W \leq 10^{18}
L, W は整数

入力

L W

ロープの長さを表す整数 L と、収納ケースに収まる長さの上限を表す整数 W が、スペース区切りで 1 行に与えられる。

出力

ロープの長さを W センチメートル以下にするために必要な最小の折りたたみ回数を 1 行で出力してください。

入力例 1

10 3

出力例 1

入力例 2

100 100

出力例 2

入力例 3

1000000000000000000 1

出力例 3

Score : 300 pts

Problem Statement

Takahashi belongs to a mountaineering club and is in charge of managing the long rope used for activities.

In the club's storage room, there is one rope of length L centimeters. To put this rope into a storage case, the rope's length must be reduced to W centimeters or less.

Takahashi plans to repeatedly fold the rope in half to make it short enough to fit in the storage case. Folding in half means folding the entire rope at its midpoint. When a rope of current length x centimeters is folded in half once, its length becomes \lceil x / 2 \rceil centimeters. Here, \lceil y \rceil denotes the smallest integer greater than or equal to y (the ceiling function). This corresponds to the fact that when the length is odd, the fold position is not exactly at the halfway point, and the length of the longer of the two overlapping parts becomes the overall length. For example, folding a rope of length 7 in half gives a length of \lceil 7 / 2 \rceil = 4, and folding a rope of length 8 in half gives a length of \lceil 8 / 2 \rceil = 4. Note that the thickness resulting from folding is not considered.

Find the minimum number of folds required to reduce the rope's length to W centimeters or less. If L \leq W from the beginning, no folding is necessary, so the answer is 0.

Constraints

1 \leq L \leq 10^{18}
1 \leq W \leq 10^{18}
L, W are integers

Input

L W

An integer L representing the length of the rope and an integer W representing the maximum length that fits in the storage case are given on a single line, separated by a space.

Output

Print the minimum number of folds required to reduce the rope's length to W centimeters or less, on a single line.

Sample Input 1

10 3

Sample Output 1

Sample Input 2

100 100

Sample Output 2

Sample Input 3

1000000000000000000 1

Sample Output 3

C - 最強の結束

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

配点 : 366 点

問題文

高橋君は N 個の宝石を持っています。宝石には 1 から N までの番号が付いており、宝石 i の品質値は A_i です。

高橋君はこの中から 2 個以上の宝石を選んでネックレスを作ろうとしています。ネックレスの「美しさ」は、選んだ宝石すべての品質値の最大公約数（GCD）で定義されます。美しさは選んだ宝石の集合のみで決まり、宝石の並べ方には依存しません。

高橋君は、まず美しさを最大化したいと考えています。さらに、美しさが最大となる選び方が複数存在する場合は、その中で選ぶ宝石の個数が最小のものを選びたいと考えています（余った宝石は他の用途に回せるためです）。

より正確に述べます。宝石の番号の集合 \{1, 2, \ldots, N\} の部分集合のうち、要素数が 2 以上であるものを考え、以下のように値 G と K を定めます。

そのような部分集合 S すべてについて、S に含まれる各宝石の品質値の GCD、すなわち \gcd(A_i \mid i \in S) を考える。この GCD の最大値を G とする。
GCD が G に等しい部分集合 S の中で、S の要素数の最小値を K とする。

ネックレスに使わなかった宝石の個数、すなわち N - K を求めてください。

制約

2 \leq N \leq 10^6
1 \leq A_i \leq 10^6（1 \leq i \leq N）
入力は全て整数である。

入力

N
A_1 A_2 \ldots A_N

1 行目には、宝石の個数を表す整数 N が与えられる。
2 行目には、各宝石の品質値を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

ネックレスに使わなかった宝石の個数 N - K を 1 行で出力せよ。

入力例 1

4
6 10 15 21

出力例 1

入力例 2

5
7 11 13 17 19

出力例 2

入力例 3

12
18 24 30 42 70 105 140 210 35 49 63 77

出力例 3

入力例 4

30
360 720 1080 1440 1800 210 330 462 770 1001 1430 2210 2730 3570 4290 6006 8190 9009 12345 23456 34567 45678 56789 67890 78901 89012 99991 999983 500000 1000000

出力例 4

入力例 5

2
1 1000000

出力例 5

Score : 366 pts

Problem Statement

Takahashi has N gems. The gems are numbered from 1 to N, and gem i has a quality value of A_i.

Takahashi wants to select 2 or more gems from these to make a necklace. The "beauty" of the necklace is defined as the greatest common divisor (GCD) of the quality values of all selected gems. The beauty depends only on the set of selected gems and does not depend on how they are arranged.

Takahashi first wants to maximize the beauty. Furthermore, if there are multiple ways to select gems that achieve the maximum beauty, he wants to choose the one with the minimum number of gems selected (since the remaining gems can be used for other purposes).

More precisely, consider subsets of the set of gem numbers \{1, 2, \ldots, N\} that have at least 2 elements, and define values G and K as follows:

For all such subsets S, consider the GCD of the quality values of the gems in S, i.e., \gcd(A_i \mid i \in S). Let G be the maximum value of this GCD.
Among the subsets S whose GCD equals G, let K be the minimum number of elements in S.

Find the number of gems not used in the necklace, i.e., N - K.

Constraints

2 \leq N \leq 10^6
1 \leq A_i \leq 10^6 (1 \leq i \leq 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 gems.
The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the quality values of each gem.

Output

Print the number of gems not used in the necklace, N - K, in one line.

Sample Input 1

4
6 10 15 21

Sample Output 1

Sample Input 2

5
7 11 13 17 19

Sample Output 2

Sample Input 3

12
18 24 30 42 70 105 140 210 35 49 63 77

Sample Output 3

Sample Input 4

30
360 720 1080 1440 1800 210 330 462 770 1001 1430 2210 2730 3570 4290 6006 8190 9009 12345 23456 34567 45678 56789 67890 78901 89012 99991 999983 500000 1000000

Sample Output 4

Sample Input 5

2
1 1000000

Sample Output 5

D - 均等な買い物

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

配点 : 400 点

問題文

高橋君と青木君がお土産を買いに行きます。お店は N 軒あり、1 から N までの番号が付けられています。i 番目のお店では、L_i 以上 R_i 以下の任意の整数金額で買い物ができます。

買い物計画とは、各お店に対して次のいずれか 1 つの状態を定めたものです。

誰も買い物をしない。
高橋君のみが買い物をし、そのお店で選べる範囲内の整数金額を 1 つ決める。
青木君のみが買い物をし、そのお店で選べる範囲内の整数金額を 1 つ決める。

すなわち、同じお店で 2 人が同時に買い物をすることはできません。

買い物計画が以下の条件をすべて満たすとき、これを均等な買い物計画と呼びます。

高橋君が買い物をするお店がちょうど P 軒である。
青木君が買い物をするお店がちょうど Q 軒である。
高橋君の合計購入金額と青木君の合計購入金額が等しい。

2 つの買い物計画が異なるとは、少なくとも 1 つのお店について以下のいずれかが成り立つことをいいます。

そのお店の状態（誰も買い物をしない・高橋君が買い物をする・青木君が買い物をする）が異なる。
そのお店で同じ人が買い物をしているが、選んだ購入金額が異なる。

これから M 回、お店の購入金額範囲の変更が順に行われます。j 回目の変更では、X_j 番目のお店で選べる購入金額の範囲が A_j 以上 B_j 以下に置き換わります。変更は累積的に適用されます（過去の変更の結果は保持されたまま、新たな変更が適用されます）。

各変更の直後における、均等な買い物計画の個数を 998244353 で割った余りを求めてください。

制約

1 \leq N \leq 2000
1 \leq P \leq 3
1 \leq Q \leq 3
P + Q \leq N
1 \leq M \leq 1000
N \times M \leq 2000
1 \leq L_i \leq R_i \leq 20
1 \leq X_j \leq N
1 \leq A_j \leq B_j \leq 20
入力はすべて整数である。

入力

N P Q M
L_1 R_1
L_2 R_2
\vdots
L_N R_N
X_1 A_1 B_1
X_2 A_2 B_2
\vdots
X_M A_M B_M

1 行目には、お店の数 N、高橋君が買い物をするお店の数 P、青木君が買い物をするお店の数 Q、変更の回数 M が、スペース区切りで与えられる。
続く N 行のうち i 行目には、i 番目のお店で初期状態において選べる最小金額 L_i と最大金額 R_i が、スペース区切りで与えられる。
続く M 行のうち j 行目には、j 回目の変更対象のお店の番号 X_j、新しい範囲の下限 A_j、上限 B_j が、スペース区切りで与えられる。この変更により、X_j 番目のお店で選べる購入金額の範囲は A_j 以上 B_j 以下に置き換わる。

出力

M 行出力せよ。j 行目には、j 回目の変更の直後における均等な買い物計画の個数を 998244353 で割った余りを出力せよ。

入力例 1

出力例 1

8
2
4

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

出力例 5

Score : 400 pts

Problem Statement

Takahashi and Aoki are going shopping for souvenirs. There are N shops, numbered from 1 to N. At the i-th shop, one can purchase items for any integer amount between L_i and R_i, inclusive.

A shopping plan assigns exactly one of the following states to each shop:

Nobody shops there.
Only Takahashi shops there, and he chooses one integer amount within the shop's allowed range.
Only Aoki shops there, and he chooses one integer amount within the shop's allowed range.

That is, two people cannot shop at the same shop simultaneously.

A shopping plan is called an equal shopping plan if it satisfies all of the following conditions:

Takahashi shops at exactly P shops.
Aoki shops at exactly Q shops.
Takahashi's total purchase amount equals Aoki's total purchase amount.

Two shopping plans are considered different if there exists at least one shop for which one of the following holds:

The state of that shop (nobody shops / Takahashi shops / Aoki shops) differs between the two plans.
The same person shops at that shop in both plans, but the chosen purchase amount differs.

From now on, M changes to the shops' price ranges will be applied in order. In the j-th change, the allowed purchase amount range at shop X_j is replaced with A_j to B_j, inclusive. Changes are applied cumulatively (the results of past changes are retained, and new changes are applied on top of them).

After each change, find the number of equal shopping plans modulo 998244353.

Constraints

1 \leq N \leq 2000
1 \leq P \leq 3
1 \leq Q \leq 3
P + Q \leq N
1 \leq M \leq 1000
N \times M \leq 2000
1 \leq L_i \leq R_i \leq 20
1 \leq X_j \leq N
1 \leq A_j \leq B_j \leq 20
All input values are integers.

Input

N P Q M
L_1 R_1
L_2 R_2
\vdots
L_N R_N
X_1 A_1 B_1
X_2 A_2 B_2
\vdots
X_M A_M B_M

The first line contains the number of shops N, the number of shops where Takahashi shops P, the number of shops where Aoki shops Q, and the number of changes M, separated by spaces.
The following N lines, where the i-th line contains the minimum amount L_i and maximum amount R_i available at the i-th shop in the initial state, separated by spaces.
The following M lines, where the j-th line contains the shop number X_j targeted by the j-th change, the new lower bound A_j, and upper bound B_j, separated by spaces. This change replaces the allowed purchase amount range at shop X_j with A_j to B_j, inclusive.

Output

Output M lines. The j-th line should contain the number of equal shopping plans immediately after the j-th change, modulo 998244353.

Sample Input 1

Sample Output 1

8
2
4

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

Sample Output 5

E - 宇宙ステーションへの移動

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

配点 : 466 点

問題文

高橋君は宇宙飛行士として、宇宙空間での船外活動を行っています。現在、高橋君は母船から距離 W メートル離れた宇宙ステーションへ移動する必要があります。

宇宙空間には N 個のデブリ（宇宙ゴミ）が浮遊しており、高橋君はこれらのデブリを足場にしてステーションまで移動することができます。

母船の位置を y = 0 、宇宙ステーションの入口を y = W とする座標系を考えると、 i 番目のデブリは座標 (x_i, y_i) に位置しています。高橋君は最初、母船の座標 (0, 0) におり、宇宙ステーションの入口である座標 (0, W) に到達したいと考えています。

高橋君の宇宙服に搭載されたジェットパックは、現在地から距離 D 以下の場所にあるデブリ、または宇宙ステーションの入口へジャンプすることができます。ただし、母船から直接宇宙ステーションにジャンプすることはできません（安全上の理由から、必ず少なくとも 1 つのデブリを経由する必要があります）。

高橋君が宇宙ステーションに到達するために必要な最小ジャンプ回数を求めてください。ただし、どのようにデブリを選んでも宇宙ステーションに到達できない場合は -1 を出力してください。

なお、 2 点 (a, b) と (c, d) の距離は \sqrt{(a-c)^2 + (b-d)^2} で計算されます。

制約

1 \leq N \leq 10^5
2 \leq W \leq 10^9
1 \leq D \leq 10^9
-10^9 \leq x_i \leq 10^9
1 \leq y_i \leq W - 1
すべての入力値は整数

入力

N W D
x_1 y_1
x_2 y_2
:
x_N y_N

1 行目には、デブリの個数 N 、母船から宇宙ステーションまでの距離 W 、ジャンプ可能な最大距離 D が、スペース区切りで与えられる。
2 行目から N + 1 行目には、各デブリの座標が与えられる。
1 + i 行目では、 i 番目のデブリの x 座標 x_i と y 座標 y_i が、スペース区切りで与えられる。

出力

高橋君が宇宙ステーションに到達するために必要な最小ジャンプ回数を 1 行で出力せよ。到達できない場合は -1 を出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

-1

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

1 1000000000 1000000000
0 500000000

出力例 5

Score : 466 pts

Problem Statement

Takahashi is an astronaut conducting extravehicular activity in outer space. Currently, he needs to travel to a space station that is W meters away from his mothership.

There are N pieces of debris (space junk) floating in space, and Takahashi can use these pieces of debris as footholds to move to the station.

Considering a coordinate system where the mothership is at y = 0 and the entrance of the space station is at y = W, the i-th piece of debris is located at coordinates (x_i, y_i). Takahashi is initially at the mothership at coordinates (0, 0) and wants to reach the entrance of the space station at coordinates (0, W).

The jetpack equipped on Takahashi's spacesuit allows him to jump to a piece of debris or the entrance of the space station that is within a distance of D from his current position. However, he cannot jump directly from the mothership to the space station (for safety reasons, he must visit at least 1 piece of debris).

Find the minimum number of jumps required for Takahashi to reach the space station. If it is impossible to reach the space station no matter which debris he chooses, output -1.

The distance between two points (a, b) and (c, d) is calculated as \sqrt{(a-c)^2 + (b-d)^2}.

Constraints

1 \leq N \leq 10^5
2 \leq W \leq 10^9
1 \leq D \leq 10^9
-10^9 \leq x_i \leq 10^9
1 \leq y_i \leq W - 1
All input values are integers.

Input

N W D
x_1 y_1
x_2 y_2
:
x_N y_N

The first line contains the number of pieces of debris N, the distance from the mothership to the space station W, and the maximum jump distance D, separated by spaces.
The 2-nd through (N + 1)-th lines provide the coordinates of each piece of debris.
The (1 + i)-th line contains the x-coordinate x_i and the y-coordinate y_i of the i-th piece of debris, separated by a space.

Output

Print the minimum number of jumps required for Takahashi to reach the space station in a single line. If it is impossible to reach, print -1.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-1

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

1 1000000000 1000000000
0 500000000