AtCoder Daily Training HARD 2024/12/12 18:30start

E - Doukasen

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

配点 : 300 点

問題文

N 本の導火線を一直線に接着したものがあります。左から i 本目の導火線は長さが A_i cm で、 1 秒あたり B_i cm の一定の速さで燃えます。

この導火線の左端と右端から同時に火をつけるとき、 2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か求めてください。

制約

1 \leq N \leq 10^5
1 \leq A_i,B_i \leq 1000
入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

2 つの火がぶつかる場所が着火前の導火線の左端から何 cm の地点か（単位を除いて）出力せよ。

想定解答との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。

入力例 1

出力例 1

3.000000000000000

着火前の導火線の左端から 3 cm の地点で 2 つの火がぶつかります。

入力例 2

出力例 2

3.833333333333333

入力例 3

出力例 3

8.916666666666668

Score : 300 points

Problem Statement

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

1 \leq N \leq 10^5
1 \leq A_i,B_i \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the distance between the position where the two flames will meet and the left end of the object, in centimeters (print just the number).

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-5}.

Sample Input 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

Sample Output 2

3.833333333333333

Sample Input 3

Sample Output 3

8.916666666666668

F - String Delimiter

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

配点 : 300 点

問題文

英小文字、,、" からなる長さ N の文字列 S が与えられます。S に含まれる " の個数は偶数であることが保証されています。

S に含まれる " の個数を 2K 個とすると、各 i=1,2,\ldots,K について 2i-1 番目の " から 2i 番目の " までの文字のことを 括られた文字 と呼びます。

あなたの仕事は、 S に含まれる , のうち、括られた文字 でないもの を . で置き換えて得られる文字列を答えることです。

制約

N は 1 以上 2\times 10^5 以下の整数
S は英小文字、,、" からなる長さ N の文字列
S に含まれる " の個数は偶数

入力

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

N
S

出力

答えを出力せよ。

入力例 1

8
"a,b"c,d

出力例 1

"a,b"c.d

S のうち "a,b" が括られた文字であり、c,d は括られた文字ではありません。

S に含まれる , のうち、括られた文字でないのは S の左から 7 番目の文字なので、7 番目の文字を . で置き換えたものが答えとなります。

入力例 2

5
,,,,,

出力例 2

.....

入力例 3

20
a,"t,"c,"o,"d,"e,"r,

出力例 3

a."t,"c."o,"d."e,"r.

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

N is an integer between 1 and 2\times 10^5, inclusive.
S is a string of length N consisting of lowercase English letters, ,, and ".
S contains an even number of ".

Input

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

N
S

Output

Print the answer.

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

G - Prefix K-th Max

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

配点 : 400 点

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N)、および正整数 K が与えられます。

i=K,K+1,\ldots,N について、以下を求めてください。

P の先頭 i 項のうち、K 番目に大きい値

制約

1 \leq K \leq N \leq 5 \times 10^5
(P_1,P_2,\ldots,P_N) は (1,2,\ldots,N) の並び替えによって得られる
入力はすべて整数

入力

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

N K
P_1 P_2 \ldots P_N

出力

i=K,K+1,\ldots,N についてこの順に、問題文中で問われている値を改行区切りで出力せよ。

入力例 1

3 2
1 2 3

出力例 1

1
2

P の先頭 2 項、すなわち (P_1,P_2)=(1,2) の中で K=2 番目に大きい値は 1 となります。
P の先頭 3 項、すなわち (P_1,P_2,P_3)=(1,2,3) の中で K=2 番目に大きい値は 2 となります。

入力例 2

11 5
3 7 2 5 11 6 1 9 8 10 4

出力例 2

Score : 400 points

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

The K-th greatest value among the first i terms of P.

Constraints

1 \leq K \leq N \leq 5 \times 10^5
(P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \ldots P_N

Output

For each i=K, K+1, \ldots, N, in this order, print the specified value in Problem Statement, separated by newlines.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

11 5
3 7 2 5 11 6 1 9 8 10 4

Sample Output 2

H - Takahashi Quest

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

配点 : 450 点

問題文

高橋くんは冒険に出ようとしています。

冒険では、N 個の出来事が起こります。 i 番目 (1\leq i\leq N) の出来事は整数の組 (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) で表され、次のような出来事です。

t _ i=1 のとき、タイプ x _ i のポーションを 1 つ発見する。高橋くんは、発見したポーションを拾うか捨てるかのどちらかを選択する。
t _ i=2 のとき、タイプ x _ i のモンスター 1 体と遭遇する。高橋くんがタイプ x _ i のポーションを持っている場合、それを 1 つ消費することでモンスターを撃退することができる。モンスターを撃退しなかった場合、高橋くんは敗北する。

高橋くんが敗北することなく全てのモンスターを撃退することができるか判定してください。

高橋くんが全てのモンスターを撃退することができない場合、-1 を出力してください。

高橋くんが全てのモンスターを撃退することができる場合、高橋君が冒険の途中で持っているポーションの個数の最大値を K とします。高橋くんが敗北しないような戦略全体にわたる K の最小値を K _ {\min} とします。 K _ {\min} の値と、K _ {\min} を達成する高橋くんの行動を出力してください。

制約

1\leq N\leq2\times10^5
1\leq t _ i\leq2\ (1\leq i\leq N)
1\leq x _ i\leq N\ (1\leq i\leq N)
入力はすべて整数

入力

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

N
t _ 1 x _ 1
t _ 2 x _ 2
\vdots
t _ N x _ N

出力

高橋くんが全てのモンスターを撃退することができない場合、-1 を出力せよ。高橋くんが全てのモンスターを撃退することができる場合、1 行目には K _ {\min} の値を、2 行目には t _ i=1 であるような i すべてについて昇順に、i 番目の出来事で発見したポーションを拾うなら 1 を、拾わないなら 0 を空白区切りで出力せよ。 K _ {\min} を達成し、高橋くんが敗北せず冒険を終えられるような行動が複数ある場合、どれを出力しても構わない。

入力例 1

出力例 1

3
1 1 1 0 0 1 0 1

出力例は、次のような行動に対応しています。

タイプ 2,3,1 のポーションをこの順に発見する。これらのポーションをすべて拾う。
タイプ 3,2 のポーションをこの順に発見する。これらのポーションをいずれも拾わない。
タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
タイプ 3 のポーションを発見する。このポーションを拾う。
タイプ 3 のポーションを発見する。このポーションを拾わない。
タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
タイプ 3 のポーションを発見する。このポーションを拾う。
タイプ 2 のモンスターと遭遇する。持っているタイプ 2 のポーションを 1 つ消費してモンスターを撃退する。
タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
タイプ 1 のモンスターと遭遇する。持っているタイプ 1 のポーションを 1 つ消費してモンスターを撃退する。

この行動では、K の値は 3 となります。

K\leq 2 として敗北しない方法はないので、求める K _ {\min} の値は 3 です。 K=3 を満たして高橋くんが敗北しない行動は複数ありますが、どれを出力しても構いません。

入力例 2

出力例 2

-1

高橋くんはかならず最初に遭遇するモンスターに敗北してしまいます。

入力例 3

出力例 3

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

Score : 450 points

Problem Statement

Takahashi will embark on an adventure.

During the adventure, N events will occur. The i-th event (1\leq i\leq N) is represented by a pair of integers (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) and is as follows:

If t _ i=1, he finds one potion of type x _ i. He can choose to pick it up or discard it.
If t _ i=2, he encounters one monster of type x _ i. If he has a potion of type x _ i, he can use one to defeat the monster. If he does not defeat it, he will be defeated.

Determine whether he can defeat all the monsters without being defeated.

If he cannot defeat all the monsters, print -1.

Otherwise, let K be the maximum number of potions he has at some point during the adventure. Let K _ {\min} be the minimum value of K across all strategies where he will not be defeated. Print the value of K _ {\min} and the actions of Takahashi that achieve K _ {\min}.

Constraints

1\leq N\leq2\times10^5
1\leq t _ i\leq2\ (1\leq i\leq N)
1\leq x _ i\leq N\ (1\leq i\leq N)
All input values are integers.

Input

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

N
t _ 1 x _ 1
t _ 2 x _ 2
\vdots
t _ N x _ N

Output

If Takahashi cannot defeat all the monsters, print -1. If he can, print the value of K _ {\min} in the first line, and in the second line, for each i such that t _ i=1 in ascending order, print 1 if he picks up the potion found at the i-th event, and 0 otherwise, separated by spaces. If multiple sequences of actions achieve K _ {\min} and allow him to finish the adventure without being defeated, you may print any of them.

Sample Input 1

Sample Output 1

3
1 1 1 0 0 1 0 1

The sample output corresponds to the following actions:

Find potions of types 2,3,1 in this order. Pick up all of them.
Find potions of types 3,2 in this order. Do not pick up any of them.
Encounter a type-3 monster. Use one type-3 potion to defeat it.
Find a type-3 potion. Pick it up.
Find a type-3 potion. Do not pick it up.
Encounter a type-3 monster. Use one type-3 potion to defeat it.
Find a type-3 potion. Pick it up.
Encounter a type-2 monster. Use one type-2 potion to defeat it.
Encounter a type-3 monster. Use one type-3 potion to defeat it.
Encounter a type-1 monster. Use one type-1 potion to defeat it.

In this sequence of actions, the value of K is 3.

There is no way to avoid defeat with K\leq 2, so the sought value of K _ {\min} is 3. There are multiple sequences of actions that satisfy K=3 and allow him to avoid defeat; you may print any of them.

Sample Input 2

Sample Output 2

-1

He will inevitably be defeated by the first monster he encounters.

Sample Input 3

Sample Output 3

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

I - Cake Division

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

配点 : 575 点

問題文

円形のケーキがあり、ケーキは切り目によって N 個のピースに分けられています。各切り目は円の中心と円弧上の点を結ぶ線分です。

ピースおよび切り目には時計回りに 1, 2, \ldots, N の番号が付けられており、ピース i の質量は A_i です。ピース 1 をピース N + 1 とも呼ぶこととします。

切り目 i はピース i とピース i + 1 の間にあり、ピース 1, 切り目 1, ピース 2, 切り目 2, \ldots, ピース N, 切り目 N の順に時計回りに並んでいます。

このケーキを以下の条件を満たすように K 人に分けようとしています。ただし、i 番目の人が受け取るピースの質量の合計を w_i とします。

すべての人が 1 つ以上の連続するピースを受け取る
誰も受け取らないピースは存在しない
上の 2 つの条件を満たすという条件下で \min(w_1, w_2, \ldots, w_K) が最大になるようにする

条件を満たす分け方における \min(w_1, w_2, \ldots, w_K) の値および条件を満たすすべての分け方で切られることのない切り目の個数を求めてください。ただし、切り目 i が切られるとは、ピース i とピース i + 1 が異なる人に分けられることを指します。

制約

2 \leq K \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^4
入力される値はすべて整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

条件を満たす分け方における \min(w_1, w_2, \ldots, w_K) の値を x、切られることのない切り目の個数を y として、x と y をこの順に空白区切りで出力せよ。

入力例 1

5 2
3 6 8 6 4

出力例 1

13 1

以下の分け方が条件を満たします。

一方の人にピース 2, 3 を渡し、もう一方の人にピース 4, 5, 1 を渡す。ピース 2, 3 の質量の合計は 14、ピース 4, 5, 1 の質量の合計は 13 である。
一方の人にピース 3, 4 を渡し、もう一方の人にピース 5, 1, 2 を渡す。ピース 3, 4 の質量の合計は 14、ピース 5, 1, 2 の質量の合計は 13 である。

条件を満たす分け方における \min(w_1, w_2) の値は 13 であり、どちらの分け方でも切られない切り目は切り目 5 の 1 つです。

入力例 2

6 3
4 7 11 3 9 2

出力例 2

11 1

入力例 3

10 3
2 9 8 1 7 9 1 3 5 8

出力例 3

17 4

Score : 575 points

Problem Statement

There is a circular cake divided into N pieces by cut lines. Each cut line is a line segment connecting the center of the circle to a point on the arc.

The pieces and cut lines are numbered 1, 2, \ldots, N in clockwise order, and piece i has a mass of A_i. Piece 1 is also called piece N + 1.

Cut line i is between pieces i and i + 1, and they are arranged clockwise in this order: piece 1, cut line 1, piece 2, cut line 2, \ldots, piece N, cut line N.

We want to divide this cake among K people under the following conditions. Let w_i be the sum of the masses of the pieces received by the i-th person.

Each person receives one or more consecutive pieces.
There are no pieces that no one receives.
Under the above two conditions, \min(w_1, w_2, \ldots, w_K) is maximized.

Find the value of \min(w_1, w_2, \ldots, w_K) in a division that satisfies the conditions, and the number of cut lines that are never cut in the divisions that satisfy the conditions. Here, cut line i is considered cut if pieces i and i + 1 are given to different people.

Constraints

2 \leq K \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^4
All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Let x be the value of \min(w_1, w_2, \ldots, w_K) in a division that satisfies the conditions, and y be the number of cut lines that are never cut. Print x and y in this order, separated by a space.

Sample Input 1

5 2
3 6 8 6 4

Sample Output 1

13 1

The following divisions satisfy the conditions:

Give pieces 2, 3 to one person and pieces 4, 5, 1 to the other. Pieces 2, 3 have a total mass of 14, and pieces 4, 5, 1 have a total mass of 13.
Give pieces 3, 4 to one person and pieces 5, 1, 2 to the other. Pieces 3, 4 have a total mass of 14, and pieces 5, 1, 2 have a total mass of 13.

The value of \min(w_1, w_2) in divisions satisfying the conditions is 13, and there is one cut line that is not cut in either division: cut line 5.

Sample Input 2

6 3
4 7 11 3 9 2

Sample Output 2

11 1

Sample Input 3

10 3
2 9 8 1 7 9 1 3 5 8

Sample Output 3

17 4