AtCoder Daily Training HARD 2025/06/04 20:00start

E - AtCoder Magics

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

高橋くんは、カードゲーム「AtCoder Magics」のカードを N 枚持っています。i 番目のカードをカード i と呼ぶことにします。各カードには強さとコストのパラメーターがあり、カード i の強さは A_i で、コストは C_i です。

高橋くんは、弱いカードは要らないので捨てることにしました。具体的には、以下の操作をできなくなるまで繰り返します。

2 つのカード x, y であって、 A_x > A_y かつ C_x < C_y であるようなものを選ぶ。カード y を捨てる。

操作ができなくなったとき、捨てられなかったカードの集合は一意に定まることが証明できます。これを求めてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq A_i, C_i \leq 10^9
A_1, A_2, \dots ,A_N は全て異なる
C_1, C_2, \dots ,C_N は全て異なる
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 C_1
A_2 C_2
\vdots
A_N C_N

出力

捨てられなかったカードは m 枚あり、それらの番号が昇順に i_1, i_2, \dots ,i_m であったとする。このとき、以下の形式で出力せよ。

m
i_1 i_2 \cdots i_m

入力例 1

出力例 1

2
2 3

カード 1, 3 に注目すると、 A_1 < A_3 かつ C_1 > C_3 なのでカード 1 を捨てることができます。

それ以上操作をすることはできません。このときカード 2, 3 が残っているので、これらを出力します。

入力例 2

出力例 2

5
1 2 3 4 5

この場合、どのカードも捨てることができません。

入力例 3

出力例 3

4
2 3 5 6

Score : 350 points

Problem Statement

Takahashi has N cards from the card game "AtCoder Magics." The i-th card will be called card i. Each card has two parameters: strength and cost. Card i has a strength of A_i and a cost of C_i.

He does not like weak cards, so he will discard them. Specifically, he will repeat the following operation until it can no longer be performed:

Choose two cards x and y such that A_x > A_y and C_x < C_y. Discard card y.

It can be proved that the set of remaining cards when the operations can no longer be performed is uniquely determined. Find this set of cards.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i, C_i \leq 10^9
A_1, A_2, \dots ,A_N are all distinct.
C_1, C_2, \dots ,C_N are all distinct.
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 C_1
A_2 C_2
\vdots
A_N C_N

Output

Let there be m remaining cards, cards i_1, i_2, \dots, i_m, in ascending order. Print these in the following format:

m
i_1 i_2 \cdots i_m

Sample Input 1

Sample Output 1

2
2 3

Focusing on cards 1 and 3, we have A_1 < A_3 and C_1 > C_3, so card 1 can be discarded.

No further operations can be performed. At this point, cards 2 and 3 remain, so print them.

Sample Input 2

Sample Output 2

5
1 2 3 4 5

In this case, no cards can be discarded.

Sample Input 3

Sample Output 3

4
2 3 5 6

F - Blue Spring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は N 日間の鉄道旅行を計画しています。
高橋君はそれぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。

ここで、1\leq i\leq N について、i 日目の旅行にかかる運賃の通常料金は F_i 円です。
一方、1 日周遊パスは D 枚セットで P 円で発売されており、何セットでも購入することが可能ですが、D 枚単位でしか購入することができません。
また、購入したパスは 1 枚ずつ好きな日に使うことができ、旅行が終了した時点で余っていても構いません。

N 日間の旅行でかかる金額、すなわち 1 日周遊パスの購入にかかった代金と、1 日周遊パスを利用しなかった日における運賃の通常料金の合計金額の和としてあり得る最小値を求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq D\leq 2\times 10^5
1\leq P\leq 10^9
1\leq F_i\leq 10^9
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N D P
F_1 F_2 \ldots F_N

出力

N 日間の旅行でかかる金額としてあり得る最小値を出力せよ。

入力例 1

5 2 10
7 1 6 3 6

出力例 1

1 日周遊パスを 1 セットだけ購入し、1 日目と 3 日目に使用すると、合計金額は (10\times 1)+(0+1+0+3+6)=20 となり、このときかかる金額が最小となります。
よって、20 を出力します。

入力例 2

3 1 10
1 2 3

出力例 2

3 日間すべてにおいて運賃の通常料金を支払ったときに最小となります。

入力例 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

3000000000

1 日周遊パスを 3 セット購入し、8 日間すべてにおいて 1 日周遊パスを利用したときに最小となります。
答えが 32 bit 整数型に収まらないことがあることに注意してください。

Score : 300 points

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

1\leq N\leq 2\times 10^5
1\leq D\leq 2\times 10^5
1\leq P\leq 10^9
1\leq F_i\leq 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format:

N D P
F_1 F_2 \ldots F_N

Output

Print the minimum possible total cost for the N-day trip.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

G - Cubes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

正整数 N が与えられます。x^{3}-y^{3}=N を満たす正整数の組 (x,y) が存在するか判定し、存在する場合はそのような (x,y) を一つ出力してください。

制約

1 \leq N \leq 10^{18}
入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

出力

x^{3}-y^{3}=N を満たす正整数の組 (x,y) が存在しない場合は -1 を出力せよ。存在する場合は、x,y を順番に空白区切りで出力せよ。答えが複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

出力例 1

12 11

12^3-11^3=397 であるため、(x,y)=(12,11) が答えの一つです。

入力例 2

出力例 2

-1

x^3-y^3=1 となるような正整数の組 (x,y) は存在しません。よって、-1 を出力します。

入力例 3

39977273855577088

出力例 3

342756 66212

Score : 425 points

Problem Statement

You are given a positive integer N. Determine whether there exists a pair of positive integers (x,y) such that x^3 - y^3 = N. If such a pair exists, print one such pair (x,y).

Constraints

1 \leq N \leq 10^{18}
All input values are integers.

Input

The input is given from Standard Input in the following format:

Output

If there is no pair of positive integers (x,y) satisfying x^3 - y^3 = N, print -1. If there is such a pair, print x and y in this order separated by a space. If there are multiple solutions, printing any one of them is accepted as correct.

Sample Input 1

Sample Output 1

12 11

We have 12^3 - 11^3 = 397, so (x,y) = (12,11) is a solution.

Sample Input 2

Sample Output 2

-1

No pair of positive integers (x,y) satisfies x^3 - y^3 = 1. Thus, print -1.

Sample Input 3

39977273855577088

Sample Output 3

342756 66212

H - Σ[k=0..10^100]floor(X／10^k)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

\displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor を求めてください。

注釈

\lfloor A \rfloor は、 A の小数点以下を切り捨てた値を指します。

制約

X は整数
1 \le X < 10^{500000}

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを整数として出力せよ。
但し、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.33e+21 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。

入力例 1

出力例 1

求める値は、 1225+122+12+1+0+0+\dots+0=1360 となります。

入力例 2

出力例 2

繰り上がりに注意してください。

入力例 3

314159265358979323846264338327950288419716939937510

出力例 3

349065850398865915384738153697722542688574377708317

入力される値も出力すべき値も非常に大きくなる場合があります。

Score : 500 points

Problem Statement

Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor.

Notes

\lfloor A \rfloor denotes the value of A truncated to an integer.

Constraints

X is an integer.
1 \le X < 10^{500000}

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.
Here, the answer must be precisely printed as an integer, even if it is large. It is not allowed to use exponential notation, such as 2.33e+21, or print unnecessary leading zeros, as in 0523.

Sample Input 1

Sample Output 1

The value we seek is 1225+122+12+1+0+0+\dots+0=1360.

Sample Input 2

Sample Output 2

Beware of carries.

Sample Input 3

314159265358979323846264338327950288419716939937510

Sample Output 3

349065850398865915384738153697722542688574377708317

The values in input and output can both be enormous.

I - Fuel Round Trip

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

数直線上の座標 0 から座標 X_N まで行き、折り返して座標 0 まで帰ってくる計画を立てています。ただし、往路では正の方向、復路では負の方向にしか進めません。
移動は車で行います。車は距離 1 進むごとに 1 リットルの燃料を消費します。燃料は H リットルまで所持することができ、燃料を所持していない状態で進むことはできません。
各 i = 1, 2, \ldots, N-1 について、座標 X_i にはガソリンスタンドがあり、P_i 円払うと F_i リットルの燃料が得られます。ただし、H リットルを超えて燃料を所持することはできません。より厳密には、x リットルの燃料を持っているときに座標 X_i にあるガソリンスタンドを使うと P_i 円を払う必要があり、持っている燃料は \min(x + F_i, H) リットルとなります。各ガソリンスタンドは、往路と復路で合わせて 1 回までしか使うことができません。
はじめに燃料を H リットル所持しているとき、この計画を達成することができるか判定し、可能ならば必要な金額の最小値を求めてください。

制約

1 \leq N, H \leq 300
0 < X_1 < X_2 < \ldots < X_N \leq 10^5
1 \leq P_i \leq 10^5
1 \leq F_i \leq H
入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N H
X_1 X_2 \ldots X_N
P_1 F_1
P_2 F_2
\vdots
P_{N-1} F_{N-1}

出力

計画を達成できる場合は必要な金額の最小値を、できない場合は -1 を出力せよ。

入力例 1

出力例 1

往路で座標 5 の、復路で座標 9 のガソリンスタンドを用いることにより合計 9 円払うことで計画を達成することができます。
計画を達成するためにかかる金額を 8 円以下にすることはできません。往路と復路で同じガソリンスタンドを使うことができないことに注意してください。

入力例 2

1 1
100000

出力例 2

-1

入力例 3

5 20
4 13 16 18 23
1 16
2 8
4 11
8 13

出力例 3

Score : 550 points

Problem Statement

You are planning to travel from coordinate 0 to coordinate X_N on a number line, then turn around and return to coordinate 0. Here, you can only move in the positive direction on the outbound trip and in the negative direction on the return trip.
You will travel by car. The car consumes one liter of fuel for every unit distance it travels. You can carry up to H liters of fuel and cannot move without fuel.
For each i = 1, 2, \ldots, N-1, there is a gas station at coordinate X_i, where you can get F_i liters of fuel for P_i yen. However, you cannot carry more than H liters of fuel. More precisely, if you have x liters of fuel and use the gas station at coordinate X_i, you must pay P_i yen, and your amount of fuel becomes \min(x + F_i, H) liters. Each gas station can be used at most once in total during the round trip.
Determine if you can achieve this plan when you initially have H liters of fuel, and if it is possible, find the minimum amount of money required.

Constraints

1 \leq N, H \leq 300
0 < X_1 < X_2 < \ldots < X_N \leq 10^5
1 \leq P_i \leq 10^5
1 \leq F_i \leq H
All input values are integers.

Input

The input is given from Standard Input in the following format:

N H
X_1 X_2 \ldots X_N
P_1 F_1
P_2 F_2
\vdots
P_{N-1} F_{N-1}

Output

If the plan can be achieved, print the minimum amount of money required; otherwise, print -1.

Sample Input 1

Sample Output 1

You can achieve the plan by using the gas station at coordinate 5 on the outbound trip and the one at coordinate 9 on the return trip, paying a total of 9 yen.
It is impossible to achieve the plan by paying 8 yen or less. Note that you cannot use the same gas station on both the outbound and return trips.

Sample Input 2

1 1
100000

Sample Output 2

-1

Sample Input 3

5 20
4 13 16 18 23
1 16
2 8
4 11
8 13