Time Limit: 2 sec / Memory Limit: 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
b
s の substring は a
, b
, ab
, ba
, aba
の 5 つです。
このうち 4 番目に小さい b
を出力してください。
a
を 2 回カウントしないことに注意してください。
入力例 2
atcoderandatcodeer 5
出力例 2
andat
入力例 3
z 1
出力例 3
z
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
b
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
z
Time Limit: 2 sec / Memory Limit: 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
5 2 5 3 1 4 2 1 3 5 4
出力例 1
2
j=1 を選んで操作すると、 p は 1 3 5 4 2
となり、これがベストなので答えは 2 です。
入力例 2
3 2 3 2 1 1 2 2 3
出力例 2
3
例えば 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
8
入力例 4
5 1 1 2 3 4 5 1 5
出力例 4
5
操作をする必要はありません。
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
5 2 5 3 1 4 2 1 3 5 4
Sample Output 1
2
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
3 2 3 2 1 1 2 2 3
Sample Output 2
3
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
8
Sample Input 4
5 1 1 2 3 4 5 1 5
Sample Output 4
5
We do not have to perform the operation.
Time Limit: 2 sec / Memory Limit: 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
例えば次のようにすると 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
18
入力例 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
41
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
4
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
18
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
41
Time Limit: 2 sec / Memory Limit: 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
例えば、次のように行動すると 5 秒で達成できます。
- 頂点 1 からはじめる。 頂点 1 の色を黒に変更する。
- 頂点 2 に移動し、頂点 2 の色を白に変更する。
- 頂点 2 の色を黒に変更する。
- 頂点 4 に移動し、頂点 4 の色を黒に変更する。
- 頂点 5 に移動し、頂点 5 の色を黒に変更する。
入力例 2
6 3 1 4 5 2 6 6 1 3 4 WWBWBB
出力例 2
7
入力例 3
1 B
出力例 3
0
入力例 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
21
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
5
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
7
Sample Input 3
1 B
Sample Output 3
0
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
Sample Output 4
21