AtCoder Daily Training HARD 2025/01/01 20:00start

E - Gap Existence

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

配点 : 300 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するかどうか判定してください。

制約

2 \leq N \leq 2\times 10^5
-10^9 \leq A_i \leq 10^9
-10^9 \leq X \leq 10^9
入力は全て整数である

入力

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

N X
A_1 \ldots A_N

出力

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するとき Yes、存在しないとき No と出力せよ。

入力例 1

6 5
3 1 4 1 5 9

出力例 1

Yes

A_6-A_3=9-4=5 です。

入力例 2

6 -4
-2 -7 -1 -8 -2 -8

出力例 2

No

A_i-A_j=-4 となる組 (i,j) は存在しません。

入力例 3

2 0
141421356 17320508

出力例 3

Yes

A_1-A_1=0 です。

Score : 300 points

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

2 \leq N \leq 2\times 10^5
-10^9 \leq A_i \leq 10^9
-10^9 \leq X \leq 10^9
All values in the input are integers.

Input

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

N X
A_1 \ldots A_N

Output

Print Yes if there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X, and No otherwise.

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.

F - Tile Distance 2

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

配点 : 350 点

問題文

座標平面上に 2\times1 の大きさのタイルが敷き詰められています。タイルは、次の規則に従って敷き詰められています。

整数の組 (i,j) に対し、正方形 A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace は 1 つのタイルに含まれる。
i+j が偶数のとき、A _ {i,j} と A _ {i + 1,j} は同じタイルに含まれる。

ただし、タイルは境界を含むものとし、共通部分が正の面積をもつような 2 つの異なるタイルは存在しないとします。

原点の近くでは、タイルは以下のように敷き詰められています。

高橋君は、はじめ座標平面上の点 (S _ x+0.5,S _ y+0.5) にいます。

高橋君は、次の移動を好きなだけ繰り返します。

上下左右の方向と正の整数 n を選ぶ。その方向に n だけ進む。

高橋君が異なるタイルを通るたび、高橋君は通行料を 1 だけ支払います。

高橋君が点 (T _ x+0.5,T _ y+0.5) にたどり着くために支払わなければならない通行料の最小値を求めてください。

制約

0\leq S _ x\leq2\times10 ^ {16}
0\leq S _ y\leq2\times10 ^ {16}
0\leq T _ x\leq2\times10 ^ {16}
0\leq T _ y\leq2\times10 ^ {16}
入力はすべて整数

入力

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

S _ x S _ y
T _ x T _ y

出力

高橋君が支払わなければならない通行料の最小値を出力せよ。

入力例 1

5 0
2 5

出力例 1

例えば、以下のように移動することで支払う通行料を 5 にすることができます。

左に 1 進む。通行料を 0 支払う。
上に 1 進む。通行料を 1 支払う。
左に 1 進む。通行料を 0 支払う。
上に 3 進む。通行料を 3 支払う。
左に 1 進む。通行料を 0 支払う。
上に 1 進む。通行料を 1 支払う。

支払う通行料を 4 以下にすることはできないので、5 を出力してください。

入力例 2

3 1
4 1

出力例 2

通行料を支払わなくてよい場合もあります。

入力例 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

出力例 3

1794977862420151

出力すべき値が 32\operatorname{bit} 整数の範囲に収まらない場合があることに注意してください。

Score : 350 points

Problem Statement

The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:

For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he enters a tile, he pays a toll of 1.

Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).

Constraints

0\leq S _ x\leq2\times10 ^ {16}
0\leq S _ y\leq2\times10 ^ {16}
0\leq T _ x\leq2\times10 ^ {16}
0\leq T _ y\leq2\times10 ^ {16}
All input values are integers.

Input

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

S _ x S _ y
T _ x T _ y

Output

Print the minimum toll Takahashi must pay.

Sample Input 1

5 0
2 5

Sample Output 1

For example, Takahashi can pay a toll of 5 by moving as follows:

Move left by 1. Pay a toll of 0.
Move up by 1. Pay a toll of 1.
Move left by 1. Pay a toll of 0.
Move up by 3. Pay a toll of 3.
Move left by 1. Pay a toll of 0.
Move up by 1. Pay a toll of 1.

It is impossible to reduce the toll to 4 or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a 32-bit integer.

G - Gomamayo Sequence

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

配点 : 400 点

問題文

0, 1 からなる長さ N の文字列 S が与えられます。

0, 1 からなる長さ N の文字列 T は以下の条件を満たすとき、またそのときに限り 良い文字列 であると定義します。

1 \leq i \leq N - 1 を満たす整数 i であって、T の i 文字目と i + 1 文字目が一致するようなものがちょうど 1 つ存在する。

i = 1,2,\ldots, N について以下の操作を 1 度行うか行わないか選ぶことができます。

S の i 文字目が 0 であるとき S の i 文字目を 1 に、そうでないとき S の i 文字目を 0 に置き換える。操作を行った場合、C_i のコストがかかる。

S を良い文字列にするために必要なコストの総和の最小値を求めてください。

制約

2 \leq N \leq 2 \times 10^5
S は長さ N の 0,1 からなる文字列
1 \leq C_i \leq 10^9
N, C_i は整数

入力

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

N
S
C_1 C_2 \ldots C_N

出力

答えを出力せよ。

入力例 1

5
00011
3 9 2 6 4

出力例 1

i = 1, 5 に対して操作を行い、i = 2, 3, 4 に対して操作を行わないことで S = 10010 となり、S は良い文字列となります。このときかかるコストは 7 であり、コスト 7 未満で S を良い文字列にすることはできないため、7 を出力します。

入力例 2

4
1001
1 2 3 4

出力例 2

入力例 3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

出力例 3

2286846953

Score: 400 points

Problem Statement

You are given a string S of length N consisting of 0 and 1.

A string T of length N consisting of 0 and 1 is a good string if and only if it satisfies the following condition:

There is exactly one integer i such that 1 \leq i \leq N - 1 and the i-th and (i + 1)-th characters of T are the same.

For each i = 1,2,\ldots, N, you can choose whether or not to perform the following operation once:

If the i-th character of S is 0, replace it with 1, and vice versa. The cost of this operation, if performed, is C_i.

Find the minimum total cost required to make S a good string.

Constraints

2 \leq N \leq 2 \times 10^5
S is a string of length N consisting of 0 and 1.
1 \leq C_i \leq 10^9
N and C_i are integers.

Input

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

N
S
C_1 C_2 \ldots C_N

Output

Print the answer.

Sample Input 1

5
00011
3 9 2 6 4

Sample Output 1

Performing the operation for i = 1, 5 and not performing it for i = 2, 3, 4 makes S = 10010, which is a good string. The cost incurred in this case is 7, and it is impossible to make S a good string for less than 7, so print 7.

Sample Input 2

4
1001
1 2 3 4

Sample Output 2

Sample Input 3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

Sample Output 3

2286846953

H - 11/22 Subsequence

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

配点 : 500 点

問題文

この問題における 11/22 文字列の定義は A 問題および C 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

|T| は奇数である。ここで、|T| は T の長さを表す。
1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
\frac{|T|+1}{2} 文字目が / である。
\frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられるので、Q 個のクエリを処理してください。

各クエリでは L, R が与えられます。S の L 文字目から R 文字目までからなる (連続な) 部分文字列を T としたとき、 11/22 文字列であるような T の (連続とは限らない) 部分列の長さの最大値を求めてください。そのような部分列が存在しないときは 0 を出力してください。

制約

1 \leq N \leq 10^5
1 \leq Q \leq 10^5
S は 1, 2, / からなる長さ N の文字列
1 \leq L \leq R \leq N
N, Q, L, R は整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の形式で与えられる。

L R

出力

Q 行出力せよ。i 行目には i 番目のクエリへの答えを出力せよ。

入力例 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

出力例 1

1 番目のクエリについて、S の 1 文字目から 7 文字目からなる部分文字列は 111/212 です。この文字列は 11/22 を部分列として含み、これは 11/22 文字列であるような部分列として最大です。よって答えは 5 です。
2 番目のクエリについて、S の 9 文字目から 12 文字目からなる部分文字列は 1122 です。この文字列は 11/22 文字列であるような部分列を含まないので、答えは 0 です。

Score : 500 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and C.

A string T is called an 11/22 string when it satisfies all of the following conditions:

|T| is odd. Here, |T| denotes the length of T.
The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
The (\frac{|T|+1}{2})-th character is /.
The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string S of length N consisting of 1, 2, and /, process Q queries.

Each query provides two integers L and R. Let T be the (contiguous) substring of S from the L-th through R-th character. Find the maximum length of a subsequence (not necessarily contiguous) of T that is an 11/22 string. If no such subsequence exists, print 0.

Constraints

1 \leq N \leq 10^5
1 \leq Q \leq 10^5
S is a string of length N consisting of 1, 2, and /.
1 \leq L \leq R \leq N
N, Q, L, and R are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{query}_i denotes the i-th query.

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

L R

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

Sample Output 1

For the first query, the substring from the 1-st to 7-th character of S is 111/212. This string contains 11/22 as a subsequence, which is the longest subsequence that is an 11/22 string. Therefore, the answer is 5.
For the second query, the substring from the 9-th to 12-th character of S is 1122. This string does not contain any subsequence that is an 11/22 string, so the answer is 0.

I - Blocked Roads

実行時間制限: 2 sec / メモリ制限: 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