AtCoder Daily Training HARD 2024/05/07 19:30start

E - Just K

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字のみからなる N 個の文字列 S_1,S_2,\dots,S_N が与えられます。

S_1,S_2,\dots,S_N から文字列を好きな個数選ぶことを考えます。

このとき、「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数としてあり得る最大値を求めてください。

制約

1 \le N \le 15
1 \le K \le N
N,K は整数
S_i は英小文字からなる空でない文字列である。
1 \le i \le N を満たす整数 i に対し、S_i に同じ文字は 2 個以上含まれない。
i \neq j ならば S_i \neq S_j である。

入力

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

N K
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

4 2
abi
aef
bc
acg

出力例 1

S_1,S_3,S_4 を選んだ場合、a,b,c がちょうど 2 個の文字列に含まれます。

4 個以上の文字がちょうど 2 個の文字列に含まれるような選び方は存在しないため、答えは 3 です。

入力例 2

2 2
a
b

出力例 2

同じ文字列を複数回選ぶことはできません。

入力例 3

5 2
abpqxyz
az
pq
bc
cy

出力例 3

Score : 300 points

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

1 \le N \le 15
1 \le K \le N
N and K are integers.
S_i is a non-empty string consisting of lowercase English alphabets.
For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
If i \neq j, then S_i \neq S_j.

Input

Input is given from Standard Input in the following format:

N K
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

F - Distribution

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。

i\, (1 \leq i \leq N) 番目のすぬけ君は時刻 t に宝石をもらうと S_i 単位時間後、すなわち時刻 t+S_i にその宝石を (i+1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 T_i に i 番目のすぬけ君に宝石を渡します。

全ての i\, (1 \leq i \leq N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
入力は全て整数である。

入力

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

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

出力

N 行出力せよ。i\, (1 \leq i \leq N) 行目には、i 番目のすぬけ君が初めて宝石をもらう時刻を出力すること。

入力例 1

3
4 1 5
3 10 100

出力例 1

3
7
8

時刻 13 までのすぬけ君と高橋君の行動を時系列順に並べます。

時刻 3 : 高橋君が 1 番目のすぬけ君に宝石を渡します。

時刻 7 : 1 番目のすぬけ君が 2 番目のすぬけ君に宝石を渡します。

時刻 8 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 10 : 高橋君が 2 番目のすぬけ君に宝石を渡します。

時刻 11 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 13 : 3 番目のすぬけ君が 1 番目のすぬけ君に宝石を渡します。

時刻 14 以降も彼らは宝石の受け渡しを行いますが、答えには影響しません。

入力例 2

4
100 100 100 100
1 1 1 1

出力例 2

S_i や T_i が相異なるとは限らないことに注意してください。

入力例 3

4
1 2 3 4
1 2 4 7

出力例 3

あるすぬけくんが同時刻に複数の宝石の受け渡しをする可能性があること、特に高橋くんとすぬけくんの両方から同時に宝石を貰う可能性があることに注意してください。

入力例 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

出力例 4

Score : 300 points

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the time when Snuke i receives a gem for the first time.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

G - Shift vs. CapsLock

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

あなたのパソコンのキーボードには、a キー・Shift キー・CapsLock キーの 3 種類のキーがあります。また、CapsLock キーにはランプが付いています。初め、CapsLock キーのランプは OFF であり、パソコンの画面には空文字列が表示されています。

あなたは、以下の 3 種類の操作のうち 1 つを選んで実行するということを 0 回以上何度でも行うことができます。

X ミリ秒かけて a キーのみを押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に a が付け足され、ON ならば A が付け足される。
Y ミリ秒かけて Shift キーと a キーを同時に押す。CapsLock キーのランプが OFF ならば画面の文字列の末尾に A が付け足され、 ON ならば a が付け足される。
Z ミリ秒かけて CapsLock キーを押す。CapsLock キーのランプが OFF ならば ON に、ON ならば OFF に切り替わる。

A と a からなる文字列 S が与えられます。画面の文字列を S に一致させるのに必要な最短の時間は何ミリ秒かを求めてください。

制約

1 \leq X,Y,Z \leq 10^9
X,Y,Z は整数
1 \leq |S| \leq 3 \times 10^5
S は A と a からなる文字列

入力

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

X Y Z
S

出力

答えを出力せよ。

入力例 1

1 3 3
AAaA

出力例 1

以下のように操作を行うと 9 ミリ秒で画面の文字列を AAaA に一致させられます。これが最短の時間です。

Z(=3) ミリ秒かけて CapsLock キーを押す。CapsLock キーのランプが ON になる。
X(=1) ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。
X(=1) ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。
Y(=3) ミリ秒かけて Shift キーと a キーを同時に押す。a が画面の文字列の末尾に付け足される。
X(=1) ミリ秒かけて a キーを押す。A が画面の文字列の末尾に付け足される。

入力例 2

1 1 100
aAaAaA

出力例 2

入力例 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

出力例 3

Score : 400 points

Problem Statement

Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.

You can do the following three actions any number of times in any order:

Spend X milliseconds to press only the 'a' key. If the light on the Caps Lock key is off, a is appended to the string on the screen; if it is on, A is.
Spend Y milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off, A is appended to the string on the screen; if it is on, a is.
Spend Z milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.

Given a string S consisting of A and a, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to S.

Constraints

1 \leq X,Y,Z \leq 10^9
X, Y, and Z are integers.
1 \leq |S| \leq 3 \times 10^5
S is a string consisting of A and a.

Input

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

X Y Z
S

Output

Print the answer.

Sample Input 1

1 3 3
AAaA

Sample Output 1

The following sequence of actions makes the string on the screen equal to AAaA in 9 milliseconds, which is the shortest possible.

Spend Z(=3) milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
Spend Y(=3) milliseconds to press the Shift key and 'a' key simultaneously. a is appended to the string on the screen.
Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.

Sample Input 2

1 1 100
aAaAaA

Sample Output 2

Sample Input 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

Sample Output 3

H - Chords

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

円周上に 2N 個の点が等間隔に並んでおり、ある点から始めて時計回りに 1 から 2N までの番号が付けられています。

円周上にはさらに N 個の弦があり、i 個目の弦は点 A_i と点 B_i を結んでいます。ここで、A_1,\dots,A_N,B_1,\dots,B_N は全て相異なることが保証されます。

弦どうしの交点が存在するかどうか判定してください。

制約

2\leq N \leq 2\times 10^5
1\leq A_i,B_i \leq 2N
A_1,\dots,A_N,B_1,\dots,B_N は全て相異なる
入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

弦どうしの交点が存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

出力例 1

Yes

図のように、弦 1（点 1 と点 3 を結ぶ線分）と弦 2（点 4 と点 2 を結ぶ線分）が交点を持つので、Yes を出力します。

入力例 2

出力例 2

No

図のように、弦どうしの交点は存在しないので、No を出力します。

入力例 3

出力例 3

Yes

Score: 500 points

Problem Statement

There are 2N points placed at equal intervals on a circle, numbered 1 to 2N in a clockwise direction starting from a certain point.

There are also N chords on the circle, with the i-th chord connecting points A_i and B_i. It is guaranteed that all the values A_1,\dots,A_N,B_1,\dots,B_N are distinct.

Determine whether there is an intersection between the chords.

Constraints

2\leq N \leq 2\times 10^5
1\leq A_i,B_i \leq 2N
A_1,\dots,A_N,B_1,\dots,B_N are all distinct
All input values are integers

Input

The 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

If there is an intersection between the chords, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

As shown in the figure, chord 1 (the line segment connecting points 1 and 3) and chord 2 (the line segment connecting points 4 and 2) intersect, so print Yes.

Sample Input 2

Sample Output 2

No

As shown in the figure, there is no intersection between the chords, so print No.

Sample Input 3

Sample Output 3

Yes

I - Blocked Roads

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の有向グラフが与えられます。頂点には 1 から N の番号、辺には 1 から M の番号がついています。辺 i\,(1 \leq i \leq M) は頂点 s_i から頂点 t_i に向かう長さ 1 の辺です。

各 i\,(1 \leq i \leq M) について、辺 i のみ通れないときの頂点 1 から頂点 N までの最短距離を求めてください。ただし、頂点 1 から頂点 N にたどり着けない場合は -1 を出力してください。

制約

2 \leq N \leq 400
1 \leq M \leq N(N-1)
1 \leq s_i,t_i \leq N
s_i \neq t_i
(s_i,t_i) \neq (s_j,t_j) (i \neq j)
入力は全て整数である。

入力

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

N M
s_1 t_1
s_2 t_2
\vdots
s_M t_M

出力

M 行出力せよ。

i 行目には、辺 i のみ通れないときの頂点 1 から頂点 N までの最短距離を出力せよ。ただし、頂点 1 から頂点 N にたどり着けない場合は -1 を出力せよ。

入力例 1

出力例 1

1
2
1

入力例 2

出力例 2

辺 1 のみ通れないとき、頂点 1 から頂点 N にたどり着けないので -1 を出力します。

入力例 3

出力例 3

入力例 4

4 1
1 2

出力例 4

-1

Score : 500 points

Problem Statement

You are given a directed graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i (1 \leq i \leq M) goes from Vertex s_i to Vertex t_i and has a length of 1.

For each i (1 \leq i \leq M), find the shortest distance from Vertex 1 to Vertex N when all edges except Edge i are passable, or print -1 if Vertex N is unreachable from Vertex 1.

Constraints

2 \leq N \leq 400
1 \leq M \leq N(N-1)
1 \leq s_i,t_i \leq N
s_i \neq t_i
(s_i,t_i) \neq (s_j,t_j) (i \neq j)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
s_1 t_1
s_2 t_2
\vdots
s_M t_M

Output

Print M lines.

The i-th line should contain the shortest distance from Vertex 1 to Vertex N when all edges except Edge i are passable, or -1 if Vertex N is unreachable from Vertex 1.

Sample Input 1

Sample Output 1

1
2
1

Sample Input 2

Sample Output 2

Vertex N is unreachable from Vertex 1 when all edges except Edge 1 are passable, so the corresponding line contains -1.

Sample Input 3

Sample Output 3

Sample Input 4

4 1
1 2

Sample Output 4

-1