AtCoder Daily Training HARD 2024/07/04 20:30start

E - Festival

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)

i=1,2,\dots,N に対して、以下の問題を解いてください。

i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。

制約

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
入力は全て整数

入力

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

N M
A_1 A_2 \dots A_M

出力

N 行出力せよ。

i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。

入力例 1

3 2
2 3

出力例 1

1
0
0

AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。

1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。

入力例 2

8 5
1 3 4 7 8

出力例 2

Score : 250 points

Problem Statement

The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)

For each i=1,2,\dots,N, solve the following problem.

How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.

Constraints

1 \le M \le N \le 2 \times 10^5
1 \le A_1 < A_2 < \dots < A_M = N
All input values are integers.

Input

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

N M
A_1 A_2 \dots A_M

Output

Print N lines.

The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.

Sample Input 1

3 2
2 3

Sample Output 1

1
0
0

The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.

From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.

Sample Input 2

8 5
1 3 4 7 8

Sample Output 2

F - Collision 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

xy 座標平面上に N 人の人がいます。人 i は (X_i, Y_i) にいます。すべての人は異なる地点にいます。

L, R からなる長さ N の文字列 S があります。
人 i は S_i = R ならば右向きに、S_i = L ならば左向きに、一斉に同じ速度で歩き始めます。ここで、右は x 軸の正の向き、左は x 軸の負の向きです。

たとえば (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL の場合は次の図のように動きます。

反対の向きに歩いている人同士が同じ地点に来ることを「衝突」と呼びます。すべての人が歩き続けたとき、衝突は発生しますか？

制約

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j) である。
X_i, Y_i はすべて整数である。
S は L および R からなる長さ N の文字列である。

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

出力

衝突が発生するならば Yes を、発生しないならば No を出力せよ。

入力例 1

出力例 1

Yes

この入力は問題文にある例と同じケースです。
すべての人が歩き続けると人 2 と人 3 が衝突します。よって Yes を出力します。

入力例 2

出力例 2

No

人 1 と人 2 は同じ向きに歩いているので衝突することはありません。

入力例 3

出力例 3

Yes

Score : 300 points

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
(X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
All X_i and Y_i are integers.
S is a string of length N consisting of L and R.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

Output

If there will be a collision, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

Sample Output 3

Yes

G - Restricted Permutation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

(1, 2, \dots, N) を並び替えて得られる数列 P であって以下の条件を満たすもののうち、辞書順で最小のものを求めてください。

i = 1, \dots, M に対し、P において A_i は B_i よりも先に現れる。

ただし、そのような P が存在しない場合は -1 と出力してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq A_i, B_i \leq N
A_i \neq B_i
入力は全て整数である。

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

出力例 1

2 1 3 4

条件を満たす P は (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1) の 5 つです。これらのうち辞書順で最小のものは (2, 1, 3, 4) です。

入力例 2

出力例 2

-1

条件を満たす P は存在しません。

Score : 400 points

Problem Statement

Among the sequences P that are permutations of (1, 2, \dots, N) and satisfy the condition below, find the lexicographically smallest sequence.

For each i = 1, \dots, M, A_i appears earlier than B_i in P.

If there is no such P, print -1.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq A_i, B_i \leq N
A_i \neq B_i
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

Sample Output 1

2 1 3 4

The following five permutations P satisfy the condition: (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1). The lexicographically smallest among them is (2, 1, 3, 4).

Sample Input 2

Sample Output 2

-1

No permutations P satisfy the condition.

H - Booster

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

2 次元平面上に N 個の街と M 個の宝箱があります。街 i は座標 (X_i,Y_i) に、宝箱 i は座標 (P_i,Q_i) にあります。

高橋君は原点を出発し、N 個の街全てを訪れたのち原点に戻る旅行をしようと考えています。
宝箱を訪れる必要はありませんが、宝箱の中にはそれぞれブースターが 1 つあり、ブースターを拾うごとに移動速度が 2 倍になります。

高橋君の最初の移動速度が単位時間あたり 1 であるとき、旅行にかかる時間の最小値を求めてください。

制約

1 \leq N \leq 12
0 \leq M \leq 5
-10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
(0,0),(X_i,Y_i),(P_i,Q_i) は相異なる
入力は全て整数

入力

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

N M
X_1 Y_1
\vdots
X_N Y_N
P_1 Q_1
\vdots
P_M Q_M

出力

答えを出力せよ。なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。

入力例 1

出力例 1

2.5000000000

以下のように移動するのが最適解の一つです。

原点から宝箱 1 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
宝箱 1 から街 1 までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる
街 1 から街 2までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる
街 2から原点までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる

入力例 2

出力例 2

3.4142135624

以下のように移動するのが最適解の一つです。

原点から街 1 までの距離 1.41\ldots を速さ 1 で移動する。時間が 1.41\ldots かかる
街 1 から街 2 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
街 2 から原点までの距離 1 を速さ 1 で移動する。時間が 1 かかる

入力例 3

出力例 3

4.3713203436

以下のように移動するのが最適解の一つです。

原点から宝箱 1 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
宝箱 1 から宝箱 2 までの距離 1.41\ldots を速さ 2 で移動する。時間が 0.707\ldots かかる
宝箱 2 から街 1 までの距離 5 を速さ 4 で移動する。時間が 1.25 かかる
街 1 から原点までの距離 5.65\ldots を速さ 4 で移動する。時間が 1.41\ldots かかる

Score : 500 points

Problem Statement

In a two-dimensional plane, there are N towns and M chests. Town i is at the coordinates (X_i,Y_i), and chest i is at the coordinates (P_i,Q_i).

Takahashi will go on a trip where he starts at the origin, visits all N towns, and then returns to the origin.
It is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by 2.

Takahashi's initial moving speed is 1. Find the shortest time needed to complete the trip.

Constraints

1 \leq N \leq 12
0 \leq M \leq 5
-10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
(0,0), (X_i,Y_i), and (P_i,Q_i) are distinct.
All values in the input are integers.

Input

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

N M
X_1 Y_1
\vdots
X_N Y_N
P_1 Q_1
\vdots
P_M Q_M

Output

Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{-6}.

Sample Input 1

Sample Output 1

2.5000000000

Here is one optimal way to complete the trip.

Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
Go the distance 1 from chest 1 to town 1 at a speed of 2, taking a time of 0.5.
Go the distance 1 from town 1 to town 2 at a speed of 2, taking a time of 0.5.
Go the distance 1 from town 2 to the origin at a speed of 2, taking a time of 0.5.

Sample Input 2

Sample Output 2

3.4142135624

Here is one optimal way to complete the trip.

Go the distance 1.41\ldots from the origin to town 1 at a speed of 1, taking a time of 1.41\ldots.
Go the distance 1 from town 1 to town 2 at a speed of 1, taking a time of 1.
Go the distance 1 from town 2 to the origin at a speed of 1, taking a time of 1.

Sample Input 3

Sample Output 3

4.3713203436

Here is one optimal way to complete the trip.

Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
Go the distance 1.41\ldots from chest 1 to chest 2 at a speed of 2, taking a time of 0.707\ldots.
Go the distance 5 from chest 2 to town 1 at a speed of 4, taking a time of 1.25.
Go the distance 5.65\ldots from town 1 to the origin at a speed of 4, taking a time of 1.41\ldots.

I - ABCBAC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の文字列 S および整数 i\ (0\leq i\leq N) に対して、f_i(S) を、

S の先頭 i 文字
S を反転した文字列
S の末尾 N-i 文字

をこの順に連結した文字列と定義します。例えば、S= abc、i=2 のとき、f_i(S)= abcbac です。

長さ 2N の文字列 T が与えられます。 f_i(S)=T を満たす長さ N の文字列 S と整数 i\ (0\leq i\leq N) の組を 1 つ見つけてください。そのような S,i の組が存在しない場合は、それを報告してください。

制約

1\leq N \leq 10^6
N は整数
T は英小文字からなる長さ 2N の文字列

入力

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

N 
T

出力

条件を満たす S,i の組が存在しないならば、-1 と出力せよ。存在するならば、S,i を改行区切りで出力せよ。条件を満たす S,i の組が複数存在する場合は、そのどれを出力しても良い。

入力例 1

3
abcbac

出力例 1

abc
2

問題文中に書いた通り、S= abc、i=2 とすると f_i(S)= abcbac となって T に一致するため、abc と 2 を出力します。

入力例 2

4
abababab

出力例 2

abab
1

S= abab、i=3 としても条件を満たします。

入力例 3

3
agccga

出力例 3

cga
0

S= agc、i=3 としても条件を満たします。

入力例 4

4
atcodeer

出力例 4

-1

条件を満たす S,i の組が存在しない場合は -1 を出力してください。

Score : 500 points

Problem Statement

For a string S of length N and an integer i\ (0\leq i\leq N), let us define the string f_i(S) as the concatenation of:

the first i characters of S,
the reversal of S, and
the last (N-i) characters of S,

in this order. For instance, if S= abc and i=2, we have f_i(S)= abcbac.

You are given a string T of length 2N. Find a pair of a string S of length N and an integer i\ (0\leq i\leq N) such that f_i(S)=T. If no such pair of S and i exists, report that fact.

Constraints

1\leq N \leq 10^6
N is an integer.
T is a string of length 2N consisting of lowercase English letters.

Input

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

N 
T

Output

If no pair of S and i satisfies the condition, print -1. Otherwise, print S and i, separated by a newline. If multiple pairs of S and i satisfy the condition, you may print any of them.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if S= abc and i=2, we have f_i(S)= abcbac, which equals T, so you should print abc and 2.

Sample Input 2

4
abababab

Sample Output 2

abab
1

S= abab and i=3 also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

S= agc and i=3 also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of S and i satisfies the condition, print -1.