AtCoder Regular Contest 097

C - K-th Substring

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

配点 : 300 点

問題文

文字列 s が与えられます。 s の異なる substring のうち、辞書順で K 番目に小さいものを出力してください。

ただし、s の substring とは、 s の空でない連続した部分を取り出してできる文字列とします。例えば、 s = ababc とすると、 a, bab, ababc は s の substring ですが、 ac, z, 空文字列は s の substring ではありません。また、substring が異なるとは、文字列として異なることを指します。

なお、X = x_{1}x_{2}...x_{n}, Y = y_{1}y_{2}...y_{m} を二つの異なる文字列とするとき、Y が X の接頭辞であるか、j を x_{j} \neq y_{j} であるような最小の整数として x_{j} > y_{j} である場合、そしてその場合に限って X は Y より辞書順で大きいといいます。

制約

1 ≤ |s| ≤ 5000
s は英小文字からなる
1 ≤ K ≤ 5
s は異なる substring を K 個以上持つ

部分点

|s| ≤ 50 を満たすデータセットに正解した場合は、部分点として 200 点が与えられる。

入力

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

s
K

出力

辞書順で K 番目に小さい s の substring を出力せよ。

入力例 1

aba
4

出力例 1

s の substring は a, b, ab, ba, aba の 5 つです。このうち 4 番目に小さい b を出力してください。 a を 2 回カウントしないことに注意してください。

入力例 2

atcoderandatcodeer
5

出力例 2

andat

入力例 3

z
1

出力例 3

Score : 300 points

Problem Statement

You are given a string s. Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s. For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not. Also, we say that substrings are different when they are different as strings.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

1 ≤ |s| ≤ 5000
s consists of lowercase English letters.
1 ≤ K ≤ 5
s has at least K different substrings.

Partial Score

200 points will be awarded as a partial score for passing the test set satisfying |s| ≤ 50.

Input

Input is given from Standard Input in the following format:

s
K

Output

Print the K-th lexicographically smallest substring of K.

Sample Input 1

aba
4

Sample Output 1

s has five substrings: a, b, ab, ba and aba. Among them, we should print the fourth smallest one, b. Note that we do not count a twice.

Sample Input 2

atcoderandatcodeer
5

Sample Output 2

andat

Sample Input 3

z
1

Sample Output 3

D - Equals

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

配点 : 400 点

問題文

1 から N までの整数を並び替えた順列 p_1, p_2, .., p_N があります。また、 1 以上 N 以下の整数のペアが M 個与えられます。これらは (x_1,y_1), (x_2,y_2), .., (x_M,y_M) で表されます。シカの AtCoDeer くんは順列 p に次の操作を好きなだけ行って、 p_i = i となる i (1 ≤ i ≤ N) の数を最大にしようと考えています。

1 ≤ j ≤ M なる j を選び、 p_{x_j} と p_{y_j} をスワップする

操作後の p_i = i となる i の数として考えうる最大値を求めてください。

制約

2 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
p は 1 から N までの整数を並び替えた順列
1 ≤ x_j,y_j ≤ N
x_j ≠ y_j
i ≠ j なら、 \{x_i,y_i\} ≠ \{x_j,y_j\}
入力は全て整数

入力

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

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

出力

操作後の p_i = i となる i (1 ≤ i ≤ N) の数として考えうる最大値を出力せよ。

入力例 1

出力例 1

j=1 を選んで操作すると、 p は 1 3 5 4 2 となり、これがベストなので答えは 2 です。

入力例 2

出力例 2

例えば j=1, j=2, j=1 の順に操作すると、 p は 1 2 3 となり明らかにこれがベストです。同じ j を何回選んでもいいことに注意してください。

入力例 3

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

出力例 3

入力例 4

5 1
1 2 3 4 5
1 5

出力例 4

操作をする必要はありません。

Score : 400 points

Problem Statement

We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N. We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M). AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:

Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i = i after operations.

Constraints

2 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
p is a permutation of integers from 1 through N.
1 ≤ x_j,y_j ≤ N
x_j ≠ y_j
If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the maximum possible number of i such that p_i = i after operations.

Sample Input 1

Sample Output 1

If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

Sample Input 2

Sample Output 2

If we perform the operation by, for example, choosing j=1, j=2, j=1 in this order, p becomes 1 2 3, which is obviously optimal. Note that we may choose the same j any number of times.

Sample Input 3

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

Sample Output 3

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

We do not have to perform the operation.

E - Sorted and Sorted

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

配点 : 600 点

問題文

それぞれ 1 から N の整数が 1 つずつ書かれた白いボールと黒いボールが合わせて 2N 個一列に並んでいます。左から i (1 ≤ i ≤ 2N) 個目のボールに書いてある数は a_i で、色は c_i で表されます。 c_i = W のときボールが白いことを、c_i = B のときボールが黒いことを表します。

人間の高橋君は次のような目標を達成したいです。

1 ≤ i < j ≤ N を満たす任意の整数の組 (i,j) に対して、i が書かれた白いボールの方が j が書かれた白いボールより左にある
1 ≤ i < j ≤ N を満たす任意の整数の組 (i,j) に対して、i が書かれた黒いボールの方が j が書かれた黒いボールより左にある

目標を達成するために高橋君は次のような操作ができます。

隣り合う二つのボールをスワップする

目標を達成するために必要な操作回数の最小値を求めてください。

制約

1 ≤ N ≤ 2000
1 ≤ a_i ≤ N
c_i = W または c_i = B
i ≠ j なら、 (a_i,c_i) ≠ (a_j,c_j)

入力

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

N
c_1 a_1
c_2 a_2
:
c_{2N} a_{2N}

出力

目標を達成するために必要な操作回数の最小値を出力せよ。

入力例 1

3
B 1
W 2
B 3
W 1
W 3
B 2

出力例 1

例えば次のようにすると 4 回で可能です。

黒の 3 と白の 1 をスワップ
白の 1 と白の 2 をスワップ
黒の 3 と白の 3 をスワップ
黒の 3 と黒の 2 をスワップ

入力例 2

4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1

出力例 2

入力例 3

9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7

出力例 3

Score : 600 points

Problem Statement

There are 2N balls, N white and N black, arranged in a row. The integers from 1 through N are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball. The integer written on the i-th ball from the left (1 ≤ i ≤ 2N) is a_i, and the color of this ball is represented by a letter c_i. c_i = W represents the ball is white; c_i = B represents the ball is black.

Takahashi the human wants to achieve the following objective:

For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the white ball with i written on it is to the left of the white ball with j written on it.
For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the black ball with i written on it is to the left of the black ball with j written on it.

In order to achieve this, he can perform the following operation:

Swap two adjacent balls.

Find the minimum number of operations required to achieve the objective.

Constraints

1 ≤ N ≤ 2000
1 ≤ a_i ≤ N
c_i = W or c_i = B.
If i ≠ j, (a_i,c_i) ≠ (a_j,c_j).

Input

Input is given from Standard Input in the following format:

N
c_1 a_1
c_2 a_2
:
c_{2N} a_{2N}

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

3
B 1
W 2
B 3
W 1
W 3
B 2

Sample Output 1

The objective can be achieved in four operations, for example, as follows:

Swap the black 3 and white 1.
Swap the white 1 and white 2.
Swap the black 3 and white 3.
Swap the black 3 and black 2.

Sample Input 2

4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1

Sample Output 2

Sample Input 3

9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7

Sample Output 3

F - Monochrome Cat

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

配点 : 800 点

問題文

頂点に 1 から N の番号がついた N 頂点からなる木があります。 i 番目の辺は頂点 x_i と y_i を結んでいます。各頂点は、白か黒のいずれかの色で塗られています。初期状態では、頂点 i の色は c_i で表されます。 c_i = W のとき頂点が白いことを、c_i = B のとき頂点が黒いことを表します。

この木の頂点の上を猫が移動していきます。具体的には、1 秒間に次の動作のどちらかを行なうことを繰り返します。

現在いる頂点と隣接した頂点をひとつ選びその頂点に移動する。その後、移動先の頂点の色を反転する。
現在いる頂点の色を反転する。

猫の目標はすべての頂点を黒で塗ることです。どの頂点から動作をはじめても、どの頂点で動作を終えてもかまいません。最短何秒で目標を達成できるでしょうか?

制約

1 ≤ N ≤ 10^5
1 ≤ x_i,y_i ≤ N (1 ≤ i ≤ N-1)
与えられるグラフは木
c_i = W または c_i = B

入力

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

N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}
c_1c_2..c_N

出力

目標を達成するために必要な秒数の最小値を出力せよ。

入力例 1

5
1 2
2 3
2 4
4 5
WBBWW

出力例 1

例えば、次のように行動すると 5 秒で達成できます。

頂点 1 からはじめる。頂点 1 の色を黒に変更する。
頂点 2 に移動し、頂点 2 の色を白に変更する。
頂点 2 の色を黒に変更する。
頂点 4 に移動し、頂点 4 の色を黒に変更する。
頂点 5 に移動し、頂点 5 の色を黒に変更する。

入力例 2

6
3 1
4 5
2 6
6 1
3 4
WWBWBB

出力例 2

入力例 3

1
B

出力例 3

入力例 4

20
2 19
5 13
6 4
15 6
12 19
13 19
3 11
8 3
3 20
16 13
7 14
3 17
7 8
10 20
11 9
8 18
8 2
10 1
6 13
WBWBWBBWWWBBWWBBBBBW

出力例 4

Score : 800 points

Problem Statement

There is a tree with N vertices numbered 1 through N. The i-th edge connects Vertex x_i and y_i. Each vertex is painted white or black. The initial color of Vertex i is represented by a letter c_i. c_i = W represents the vertex is white; c_i = B represents the vertex is black.

A cat will walk along this tree. More specifically, she performs one of the following in one second repeatedly:

Choose a vertex that is adjacent to the vertex where she is currently, and move to that vertex. Then, invert the color of the destination vertex.
Invert the color of the vertex where she is currently.

The cat's objective is to paint all the vertices black. She may start and end performing actions at any vertex. At least how many seconds does it takes for the cat to achieve her objective?

Constraints

1 ≤ N ≤ 10^5
1 ≤ x_i,y_i ≤ N (1 ≤ i ≤ N-1)
The given graph is a tree.
c_i = W or c_i = B.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_{N-1} y_{N-1}
c_1c_2..c_N

Output

Print the minimum number of seconds required to achieve the objective.

Sample Input 1

5
1 2
2 3
2 4
4 5
WBBWW

Sample Output 1

The objective can be achieved in five seconds, for example, as follows:

Start at Vertex 1. Change the color of Vertex 1 to black.
Move to Vertex 2, then change the color of Vertex 2 to white.
Change the color of Vertex 2 to black.
Move to Vertex 4, then change the color of Vertex 4 to black.
Move to Vertex 5, then change the color of Vertex 5 to black.

Sample Input 2

6
3 1
4 5
2 6
6 1
3 4
WWBWBB

Sample Output 2

Sample Input 3

1
B

Sample Output 3

Sample Input 4

20
2 19
5 13
6 4
15 6
12 19
13 19
3 11
8 3
3 20
16 13
7 14
3 17
7 8
10 20
11 9
8 18
8 2
10 1
6 13
WBWBWBBWWWBBWWBBBBBW