E - Rotate Colored Subsequence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。 S の各文字は色 1 、色 2 、\ldots 、色 M の M 色のうちのいずれかで塗られており、 i = 1, 2, \ldots, N について、S の i 文字目は色 C_i で塗られています。

各 i = 1, 2, \ldots, M について、この順番に下記の操作を行います。

  • S の色 i で塗られた文字からなる部分を、右に 1 つ巡回シフトする。 すなわち、S の 色 i で塗られた文字の位置が先頭のものから順に p_1, p_2, p_3, \ldots, p_k 文字目であるとき、 S の p_1, p_2, p_3, \ldots, p_k 文字目を、それぞれ、S の p_k, p_1,p_2, \ldots, p_{k-1} 文字目で同時に置き換える。

上記の操作をすべて行った後の、最終的な S を出力してください。

なお、M 色あるどの色についても、その色で塗られた S の文字が必ず 1 つ以上存在することが、制約として保証されます。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq C_i \leq M
  • N, M, C_i はすべて整数
  • S は英小文字からなる長さ N の文字列
  • 任意の整数 1 \leq i \leq M に対して、ある整数 1 \leq j \leq N が存在して C_j = i が成り立つ

入力

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

N M
S
C_1 C_2 \ldots C_N

出力

答えを出力せよ。


入力例 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

出力例 1

cszapqbr

はじめ、S = apzbqrcs です。

  • i = 1 に対する操作では、S の 1, 4, 7 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S = cpzaqrbs となります。
  • i = 2 に対する操作では、S の 2, 5, 6, 8 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S = cszapqbr となります。
  • i = 3 に対する操作では、S の 3 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S = cszapqbr となります(操作の前後で S は変わりません)。

よって、最終的な S である cszapqbr を出力します。


入力例 2

2 1
aa
1 1

出力例 2

aa

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.

For each i = 1, 2, \ldots, M in this order, let us perform the following operation.

  • Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.

Print the final S after the above operations.

The constraints guarantee that at least one character of S is painted in each of the M colors.

Constraints

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq C_i \leq M
  • N, M, and C_i are all integers.
  • S is a string of length N consisting of lowercase English letters.
  • For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.

Input

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

N M
S
C_1 C_2 \ldots C_N

Output

Print the answer.


Sample Input 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

Sample Output 1

cszapqbr

Initially, S = apzbqrcs.

  • For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S = cpzaqrbs.
  • For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S = cszapqbr.
  • For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S = cszapqbr (here, S is not changed).

Thus, you should print cszapqbr, the final S.


Sample Input 2

2 1
aa
1 1

Sample Output 2

aa
F - Min Difference

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

それぞれ N 個、M 個の正整数からなる 2 つの数列 A=(A_1,A_2, \ldots ,A_N) と B=(B_1, \ldots ,B_M) が与えられます。

それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差の最小値、すなわち、 \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert を求めてください。

制約

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

入力

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

出力

答えを出力せよ。


入力例 1

2 2
1 6
4 9

出力例 1

2

それぞれの数列から 1 つずつ要素を選んだときの 2 つの値の差としてあり得るのは、 \lvert 1-4\rvert=3 、 \lvert 1-9\rvert=8 、 \lvert 6-4\rvert=2 、 \lvert 6-9\rvert=3 の 4 つです。 この中で最小である 2 を出力します。


入力例 2

1 1
10
10

出力例 2

0

入力例 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

出力例 3

3

Score : 300 points

Problem Statement

You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

Output

Print the answer.


Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.


Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3
G - A Piece of Cake

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

xy -平面上にいくつかのイチゴが載った長方形のケーキがあります。 ケーキは、長方形領域 \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace をちょうど占めます。

ケーキには N 個のイチゴが載っており、i = 1, 2, \ldots, N について、i 番目のイチゴの座標は (p_i, q_i) です。 2 個以上のイチゴが同一の座標にあることはありません。

高橋君は、このケーキを包丁で下記の通りにいくつかのピースに切り分けます。

  • まず、ケーキを通る y 軸に並行な A 本の異なる直線、直線 x = a_1 、直線 x = a_2 、\ldots 、直線 x = a_A のそれぞれにそってケーキを切る。
  • 次に、ケーキを通る x 軸に並行な B 本の異なる直線、直線 y = b_1 、直線 y = b_2 、\ldots 、直線 y = b_B のそれぞれにそってケーキを切る。

その結果、ケーキは (A+1)(B+1) 個の長方形のピースに分割されます。 高橋君はそれらのうちのいずれか 1 個だけを選んで食べます。 高橋君が選んだピースに載っているイチゴの個数としてあり得る最小値と最大値をそれぞれ出力してください。

ここで、最終的にピースの縁となる位置にはイチゴが存在しないことが保証されます。 より形式的な説明は下記の制約を参照してください。

制約

  • 3 \leq W, H \leq 10^9
  • 1 \leq N \leq 2 \times 10^5
  • 0 \lt p_i \lt W
  • 0 \lt q_i \lt H
  • i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
  • 1 \leq A, B \leq 2 \times 10^5
  • 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
  • 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
  • p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
  • q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
  • 入力はすべて整数

入力

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

W H
N
p_1 q_1
p_2 q_2
\vdots
p_N q_N
A
a_1 a_2 \ldots a_A
B
b_1 b_2 \ldots b_B

出力

高橋君が選んだピースに載っているイチゴの個数としてあり得る最小値 m と最大値 M をそれぞれ、下記の形式の通り空白区切りで出力せよ。

m M

入力例 1

7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4

出力例 1

0 2

全 9 個のピースの内訳は、イチゴが 0 個載ったものが 6 個、イチゴが 1 個載ったものが 1 個、イチゴが 2 個載ったものが 2 個です。 よって、それらのうちのいずれか 1 個だけを選んで食べるとき、選んだピースに載っているイチゴの個数としてあり得る最小値は 0 、最大値は 2 です。


入力例 2

4 4
4
1 1
3 1
3 3
1 3
1
2
1
2

出力例 2

1 1

どのピースにもイチゴが 1 個載っています。

Score : 400 points

Problem Statement

There is a rectangular cake with some strawberries on the xy-plane. The cake occupies the rectangular area \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.

There are N strawberries on the cake, and the coordinates of the i-th strawberry are (p_i, q_i) for i = 1, 2, \ldots, N. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

  • First, cut the cake along A different lines parallel to the y-axis: lines x = a_1, x = a_2, \ldots, x = a_A.
  • Next, cut the cake along B different lines parallel to the x-axis: lines y = b_1, y = b_2, \ldots, y = b_B.

As a result, the cake will be divided into (A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

  • 3 \leq W, H \leq 10^9
  • 1 \leq N \leq 2 \times 10^5
  • 0 \lt p_i \lt W
  • 0 \lt q_i \lt H
  • i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
  • 1 \leq A, B \leq 2 \times 10^5
  • 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
  • 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
  • p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
  • q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
  • All input values are integers.

Input

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

W H
N
p_1 q_1
p_2 q_2
\vdots
p_N q_N
A
a_1 a_2 \ldots a_A
B
b_1 b_2 \ldots b_B

Output

Print the minimum possible number of strawberries m and the maximum possible number M on the chosen piece in the following format, separated by a space.

m M

Sample Input 1

7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0, and the maximum possible number is 2.


Sample Input 2

4 4
4
1 1
3 1
3 3
1 3
1
2
1
2

Sample Output 2

1 1

Each piece has one strawberry on it.

H - 3 Team Division

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 人の人がおり、3 つのチームに分かれています。

人には 1, 2, \ldots, N の番号、チームには 1, 2, 3 の番号がついており、現在人 i はチーム A_i に所属しています。

各人には強さという値が定まっており、人 i の強さは B_i です。また、チームの強さをチームに所属する人の強さの和として定めます。

0 人以上の人が所属するチームを変更することですべてのチームの強さが等しくなるようにできるか判定してください。すべてのチームの強さが等しくなるようにできる場合は所属するチームを変更する人数として考えられる最小値を求めてください。

ただし、チーム 1, 2, 3 の他に新たにチームを作ることはできません。

制約

  • 3 \leq N \leq 100
  • A_i \in \lbrace 1, 2, 3 \rbrace
  • 各 x \in \lbrace 1, 2, 3 \rbrace に対し、ある i が存在して A_i = x
  • 1 \leq B_i
  • \displaystyle\sum_{i = 1}^{N} B_i \leq 1500
  • 入力される値はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

すべてのチームの強さが等しくなるようにできる場合は所属するチームを変更する人数として考えられる最小値を出力せよ。そうでない場合は -1 を出力せよ。


入力例 1

6
1 2
2 5
1 5
3 3
1 3
3 6

出力例 1

2

人 1 がチーム 3、人 4 がチーム 2 へと所属するチームを変更することですべてのチームの強さが 8 となります。


入力例 2

4
1 1
1 2
2 3
3 4

出力例 2

-1

入力例 3

3
1 1
2 1
3 1

出力例 3

0

入力例 4

12
2 5
1 4
3 3
2 3
3 9
1 2
2 2
3 9
2 6
1 9
1 1
3 1

出力例 4

3

Score : 450 points

Problem Statement

There are N people divided into three teams.

The people are numbered 1, 2, \ldots, N, and the teams are numbered 1, 2, 3. Currently, person i belongs to team A_i.

Each person has a value called strength; person i has a strength of B_i. The strength of a team is defined as the sum of the strengths of its members.

Determine whether it is possible for zero or more people to switch teams so that all teams have equal strength. If it is possible, find the minimum number of people who need to switch teams to achieve this.

You cannot create new teams other than teams 1, 2, 3.

Constraints

  • 3 \leq N \leq 100
  • A_i \in \lbrace 1, 2, 3 \rbrace
  • For each x \in \lbrace 1, 2, 3 \rbrace, there exists some i with A_i = x.
  • 1 \leq B_i
  • \displaystyle\sum_{i = 1}^{N} B_i \leq 1500
  • 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 it is possible to make all teams have equal strength, print the minimum number of people who need to switch teams. Otherwise, print -1.


Sample Input 1

6
1 2
2 5
1 5
3 3
1 3
3 6

Sample Output 1

2

If person 1 switches to team 3 and person 4 switches to team 2, all teams will have a strength of 8.


Sample Input 2

4
1 1
1 2
2 3
3 4

Sample Output 2

-1

Sample Input 3

3
1 1
2 1
3 1

Sample Output 3

0

Sample Input 4

12
2 5
1 4
3 3
2 3
3 9
1 2
2 2
3 9
2 6
1 9
1 1
3 1

Sample Output 4

3
I - MST Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

頂点に 1 から N の番号が、辺に 1 から N-1 の番号が付いた N 頂点 N-1 辺の重み付き無向連結グラフ G が与えられます。辺 i は頂点 a_i と頂点 b_i を結んでおり、その重みは c_i です。

Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。

  • 整数 u_i,v_i,w_i が与えられる。G の頂点 u_i,v_i の間に重み w_i の辺を追加する。その後、G の最小全域木に含まれる辺の重みの和を出力する。

制約

  • 2\leq N\leq 2 \times 10^5
  • 1\leq Q\leq 2 \times 10^5
  • 1\leq a_i\lt b_i\leq N
  • 1\leq u_i\lt v_i\leq N
  • 1\leq c_i,w_i\leq 10
  • クエリを処理する前のグラフは連結
  • 入力はすべて整数

入力

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

N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q

出力

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


入力例 1

4 4
1 2 6
2 3 5
2 4 4
1 3 3
1 2 3
1 4 10
3 4 1

出力例 1

12
10
10
7

各クエリで辺を追加した後のグラフを示しています。最小全域木に含まれる辺は赤色で塗られています。


入力例 2

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

出力例 2

49
46
45
38
34
33

Score : 550 points

Problem Statement

You are given a weighted undirected connected graph G with N vertices and N-1 edges, where vertices are numbered 1 to N and edges are numbered 1 to N-1. Edge i connects vertices a_i and b_i with a weight of c_i.

You are given Q queries to process sequentially. The i-th query is described as follows:

  • You are given integers u_i, v_i, w_i. Add an edge with weight w_i between vertices u_i and v_i in G. Then, print the sum of the weights of the edges in a minimum spanning tree of G.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq a_i < b_i \leq N
  • 1 \leq u_i < v_i \leq N
  • 1 \leq c_i, w_i \leq 10
  • The graph is connected before processing the queries.
  • All input values are integers.

Input

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

N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q

Output

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


Sample Input 1

4 4
1 2 6
2 3 5
2 4 4
1 3 3
1 2 3
1 4 10
3 4 1

Sample Output 1

12
10
10
7

Here is the graph after adding the edge for each query. The edges included in the minimum spanning tree are colored red.


Sample Input 2

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

Sample Output 2

49
46
45
38
34
33