AtCoder Grand Contest 078

A - Rearrange ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1500 点

問題文

長さ 3N で、A, B, C をそれぞれ N 個ずつ含む文字列 S,T が与えられます。

あなたは次の操作を 0 回以上行うことができます。

S の部分文字列であって、含まれる文字がすべて相異なるものを 1 つ選ぶ。
選んだ部分文字列の文字を昇順に並べ替える。

S を T に一致させることができるか判定し、できる場合は必要な操作回数の最小値を求めてください。

制約

1 \le N \le 100
S,T は A, B, C からなる長さ 3N の文字列
S,T はそれぞれ、A, B, C をちょうど N 個ずつ含む
入力される数値はすべて整数

入力

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

N
S
T

出力

答えを出力せよ。ただし、S を T に一致させることができない場合は -1 を出力せよ。

入力例 1

2
CACBAB
ACABCB

出力例 1

例えば、次のように 2 回の操作を行うことで S を T に一致させられます。

CACBAB の先頭 2 文字を選び、ACCBAB にする。
ACCBAB の 3 文字目から 5 文字目までを選び、ACABCB にする。

1 回の操作で一致させることはできないため、答えは 2 です。

入力例 2

1
ABC
CBA

出力例 2

-1

どのように操作しても、ABC を CBA に一致させることはできません。

入力例 3

8
CCBCCCABCCAABBBACABAAABB
BCAAACCABCCBACBBBACAABCB

出力例 3

Score : 1500 points

Problem Statement

You are given strings S and T of length 3N, each containing exactly N occurrences of each of A, B, and C.

You can perform the following operation zero or more times.

Choose one substring of S whose characters are all distinct.
Sort the characters of the chosen substring in ascending order.

Determine whether it is possible to make S equal to T, and if it is possible, find the minimum number of operations required.

Constraints

1 \le N \le 100
S and T are strings of length 3N consisting of A, B, and C.
Each of S and T contains exactly N occurrences of each of A, B, and C.
All input values are integers.

Input

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

N
S
T

Output

Output the answer. If it is impossible to make S equal to T, output -1.

Sample Input 1

2
CACBAB
ACABCB

Sample Output 1

For example, you can make S equal to T by performing two operations as follows.

Choose the first two characters of CACBAB, making it ACCBAB.
Choose the 3-rd through 5-th characters of ACCBAB, making it ACABCB.

It is impossible to make them equal with one operation, so the answer is 2.

Sample Input 2

1
ABC
CBA

Sample Output 2

-1

No matter how you perform the operations, you cannot make ABC equal to CBA.

Sample Input 3

8
CCBCCCABCCAABBBACABAAABB
BCAAACCABCCBACBBBACAABCB

Sample Output 3

B - L Robust IS

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1500 点

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) と、非負整数 X,Y が与えられます。

以下の条件をともに満たす A の部分列 B=(B_1,B_2,\ldots,B_M) の長さ M の最大値を求めてください。

2\le i\le M を満たすすべての整数 i に対して、B_i\ge B_{i-1}-X が成り立つ。
3\le i\le M を満たすすべての整数 i に対して、B_i\ge B_{i-2}-(X+Y) が成り立つ。

制約

1\le N\le 5\times 10^5
1\le A_i\le 10^9
0\le X,Y\le 10^9
入力される数値はすべて整数

入力

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

N X Y
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

7 3 1
8 6 3 7 5 2 6

出力例 1

部分列 (8,6,7,5,6) は条件を満たします。条件を満たす長さ 6 以上の部分列は存在しないので、5 を出力します。

入力例 2

5 0 0
5 4 3 2 1

出力例 2

入力例 3

15 441943320 890669835
693547414 783888993 702664735 345257171 73365711 320257375 683236857 951712144 151653382 210806164 439829968 987667432 978973992 565844495 621822141

出力例 3

Score : 1500 points

Problem Statement

You are given a length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N) and non-negative integers X,Y.

Find the maximum length M of a subsequence B=(B_1,B_2,\ldots,B_M) of A that satisfies both of the following conditions.

B_i\ge B_{i-1}-X holds for every integer i satisfying 2\le i\le M.
B_i\ge B_{i-2}-(X+Y) holds for every integer i satisfying 3\le i\le M.

Constraints

1\le N\le 5\times 10^5
1\le A_i\le 10^9
0\le X,Y\le 10^9
All input values are integers.

Input

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

N X Y
A_1 A_2 \ldots A_N

Output

Output the answer.

Sample Input 1

7 3 1
8 6 3 7 5 2 6

Sample Output 1

The subsequence (8,6,7,5,6) satisfies the conditions. There is no subsequence of length 6 or greater that satisfies the conditions, so output 5.

Sample Input 2

5 0 0
5 4 3 2 1

Sample Output 2

Sample Input 3

15 441943320 890669835
693547414 783888993 702664735 345257171 73365711 320257375 683236857 951712144 151653382 210806164 439829968 987667432 978973992 565844495 621822141

Sample Output 3

C - AB vs. BA

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1500 点

問題文

A と B からなる長さ N の文字列 S が与えられます。 Abel と Bart は、S を用いてゲームをします。 Abel を先手として交互に、次の操作を行います。

Abel は、S の部分文字列 AB を 1 つ選び、削除する。
Bart は、S の部分文字列 BA を 1 つ選び、削除する。

自分の手番で操作を行えない人が負けとなり、もう一方の人が勝ちとなります。両者が最適に行動したとき、勝者を求めてください。

1 つの入力につき、T ケースを解いてください。

制約

1 \le T \le 2 \times 10^5
1 \le N \le 2 \times 10^5
S は A と B からなる長さ N の文字列
T ケースにわたる N の総和は 2 \times 10^5 以下
入力される数値はすべて整数

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N
S

出力

T 行出力せよ。i 行目には、i 番目のテストケースについて、 Abel が勝つならば Abel を、そうでなければ Bart を出力せよ。

入力例 1

2
5
ABAAB
5
AABBA

出力例 1

Abel
Bart

1 番目のテストケースでは、Abel が左側の AB を削除すると S= AAB となり、 Bart は操作を行えないため、Abel が勝ちます。

2 番目のテストケースでは、Abel が AB を削除すると S= ABA となります。続いて Bart が BA を削除すると S= A となり、Abel は操作を行えないため、Bart が勝ちます。

入力例 2

3
7
BAABAAA
13
AABBAAAABABBA
20
ABAABABABBAAABBABABA

出力例 2

Bart
Abel
Abel

Score : 1500 points

Problem Statement

You are given a string S of length N consisting of A and B. Abel and Bart play a game using S. Starting with Abel, they take turns performing the following operation.

Abel chooses one substring AB of S and deletes it.
Bart chooses one substring BA of S and deletes it.

The person who cannot perform the operation on their turn loses, and the other person wins. Find the winner when both players act optimally.

Solve T test cases for each input.

Constraints

1 \le T \le 2 \times 10^5
1 \le N \le 2 \times 10^5
S is a string of length N consisting of A and B.
The sum of N over the T test cases is at most 2 \times 10^5.
All input values are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
S

Output

Output T lines. The i-th line should contain Abel if Abel wins the i-th test case, and Bart otherwise.

Sample Input 1

2
5
ABAAB
5
AABBA

Sample Output 1

Abel
Bart

In the first test case, if Abel deletes the left AB, then S= AAB, and Bart cannot perform the operation, so Abel wins.

In the second test case, if Abel deletes AB, then S= ABA. Next, if Bart deletes BA, then S= A, and Abel cannot perform the operation, so Bart wins.

Sample Input 2

3
7
BAABAAA
13
AABBAAAABABBA
20
ABAABABABBAAABBABABA

Sample Output 2

Bart
Abel
Abel