AtCoder Grand Contest 054

A - Remove Substrings

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

英小文字からなる長さ N の文字列 S が与えられます．

あなたは，S に対して以下の操作を好きな回数行えます．

先頭の文字と最後の文字が異なる連続した（非空な）部分列を選び，これを削除する．

S を空文字列にすることが可能か判定し，可能な場合は必要な最小の操作回数を求めてください．

制約

2 \leq N \leq 10^5
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

S を空文字列にすることが可能な場合，必要な最小の操作回数を出力せよ．不可能な場合，-1 を出力せよ．

入力例 1

4
abba

出力例 1

abba →（abを選んで削除）→ ba →（baを選んで削除）→ 空文字列　と操作すればよいです．

入力例 2

3
aba

出力例 2

-1

Score : 300 points

Problem Statement

Given is a string S of length N consisting of lowercase English letters.

You can do the following operation on S any number of times.

Choose its (non-empty) contiguous substring such that the first character and the last character are different, and delete this substring.

Determine whether it is possible to make S empty. If it is possible, find the minimum number of operations needed to do so.

Constraints

2 \leq N \leq 10^5
S is a string of length N consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

If it is possible to make S empty, print the minimum number of operations needed to do so. Otherwise, print -1.

Sample Input 1

4
abba

Sample Output 1

We should do as follows: abba → (delete ab) → ba → (delete ba) → an empty string.

Sample Input 2

3
aba

Sample Output 2

-1

B - Greedy Division

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

みかんが N 個あり，1 から N までの番号がついています．みかん i の重さは W_i です．高橋くんと青木くんがこれらを以下のようにして分けます．

(1,2,\cdots,N) の順列 (p_1, p_2, \cdots, p_N) を選ぶ．
i = 1, 2, \cdots, N について，この順に以下のことを行う
- 高橋くんがすでにとったみかんの重さの合計が，青木くんがすでにとったみかんの重さの合計以下なら，みかん p_i を高橋くんがとる．そうでないならみかん p_i を青木くんが取る．

最終的に二人が取るみかんの重さの合計が等しくなるような順列 p が何通りあるかを 998244353 で割った余りを求めてください．

制約

2 \leq N \leq 100
1 \leq W_i \leq 100
入力される値はすべて整数

入力

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

N
W_1 W_2 \cdots W_N

出力

答えを出力せよ．

入力例 1

3
1 1 2

出力例 1

条件を満たす p は，(1,3,2),(2,3,1),(3,1,2),(3,2,1) の 4 通りです．例えば，p=(3,2,1) の時は，以下のように進行します．

i=1: 高橋くんがすでにとったみかんの重さの合計は 0 で，青木くんがすでにとったみかんの重さの合計は 0 である．高橋くんがみかん p_i=3 をとる．
i=2: 高橋くんがすでにとったみかんの重さの合計は 2 で，青木くんがすでにとったみかんの重さの合計は 0 である．青木くんがみかん p_i=2 をとる．
i=3: 高橋くんがすでにとったみかんの重さの合計は 2 で，青木くんがすでにとったみかんの重さの合計は 1 である．青木くんがみかん p_i=1 をとる．

よって p=(3,2,1) は条件を満たす順列です．

入力例 2

4
1 2 3 8

出力例 2

入力例 3

20
2 8 4 7 5 3 1 2 4 1 2 5 4 3 3 8 1 7 8 2

出力例 3

373835282

Score : 800 points

Problem Statement

We have N oranges, numbered 1 through N. The weight of Orange i is W_i. Takahashi and Aoki will share these oranges as follows.

Choose a permutation (p_1, p_2, \cdots, p_N) of (1,2,\cdots,N).
For each i = 1, 2, \cdots, N in this order, do the following.
- If the total weight of the oranges Takahashi has taken is not greater than that of the oranges Aoki has taken, Takahashi takes Orange p_i. Otherwise, Aoki takes Orange p_i.

Find the number of permutations p modulo 998244353 such that the total weight of the oranges Takahashi will take is equal to that of the oranges Aoki will take.

Constraints

2 \leq N \leq 100
1 \leq W_i \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
W_1 W_2 \cdots W_N

Output

Print the answer.

Sample Input 1

3
1 1 2

Sample Output 1

There are four permutations p satisfying the condition: (1,3,2),(2,3,1),(3,1,2),(3,2,1). If p=(3,2,1), for example, the following will happen.

i=1: the total weights of the oranges Takahashi and Aoki have taken are 0 and 0, respectively. Takahashi takes Orange p_i=3.
i=2: the total weights of the oranges Takahashi and Aoki have taken are 2 and 0, respectively. Aoki takes Orange p_i=2.
i=3: the total weights of the oranges Takahashi and Aoki have taken are 2 and 1, respectively. Aoki takes Orange p_i=1.

Thus, the permutation p=(3,2,1) counts.

Sample Input 2

4
1 2 3 8

Sample Output 2

Sample Input 3

20
2 8 4 7 5 3 1 2 4 1 2 5 4 3 3 8 1 7 8 2

Sample Output 3

373835282

C - Roughly Sorted

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

すぬけくんは，(1,\ 2,\ ...\ N) の順列 P=(P_1,P_2,\cdots,P_N) と整数 K をもらいました．そこですぬけくんは，P の隣接する二項をswapすることを繰り返して，以下の条件が満たされるようにしました．

それぞれの 1 \leq i \leq N について， 1 \leq j< i, P_j>P_i を満たす j が高々 K 個である．

ここで，すぬけくんは最小の操作回数でこの条件を達成しました．

すべての操作が終わったあと，すぬけくんは元の順列を忘れてしまいました．操作後の順列 P' が与えられるので，元の順列 P としてあり得るものが何通りあるかを 998244353 で割った余りを求めてください．

制約

2 \leq N \leq 5000
1 \leq K \leq N-1
1 \leq P'_i \leq N
P'_i \neq P'_j (i \neq j)
それぞれの 1 \leq i \leq N について， 1 \leq j< i, P'_j>P'_i を満たす j が高々 K 個である
入力される値はすべて整数である

入力

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

N K
P'_1 P'_2 \cdots P'_N

出力

答えを出力せよ．

入力例 1

3 1
3 1 2

出力例 1

P として考えられるのは以下の 2 通りです．

P=(3,1,2): 最小の操作回数は 0 回です．操作後の順列は P' に一致します．
P=(3,2,1): 最小の操作回数は 1 回です．P_2 と P_3 をswapすることで，P=(3,1,2) となり，これは条件を満たします．操作後の順列は P' に一致します．

入力例 2

4 3
4 3 2 1

出力例 2

入力例 3

5 2
4 2 1 5 3

出力例 3

Score : 800 points

Problem Statement

Snuke received a permutation P=(P_1,P_2,\cdots,P_N) of (1,\ 2,\ ...\ N) and an integer K. He did some number of swaps of two adjacent elements in P so that the following condition would be satisfied.

For each 1 \leq i \leq N, there are at most K indices j such that 1 \leq j< i and P_j>P_i.

Here, he did the minimum number of swaps needed to achieve this condition.

Afterward, he has forgotten the original permutation he received. Given the permutation P' after the swaps, find the number, modulo 998244353, of permutations that the original permutation P could be.

Constraints

2 \leq N \leq 5000
1 \leq K \leq N-1
1 \leq P'_i \leq N
P'_i \neq P'_j (i \neq j)
For each 1 \leq i \leq N, there is at most K indices j such that 1 \leq j< i and P'_j>P'_i.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P'_1 P'_2 \cdots P'_N

Output

Print the answer.

Sample Input 1

3 1
3 1 2

Sample Output 1

P could be one of the following two permutations.

P=(3,1,2): The minimum number of swaps needed is 0. After zero swaps, the permutation is equal to P'.
P=(3,2,1): The minimum number of swaps needed is 1: swapping P_2 and P_3 results in P=(3,1,2), which satisfies the condition and is equal to P'.

Sample Input 2

4 3
4 3 2 1

Sample Output 2

Sample Input 3

5 2
4 2 1 5 3

Sample Output 3

D - (ox)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

(, ), o, x からなる文字列 S が与えられます．あなたは，S の隣接する 2 文字をswapする操作を好きな回数行うことができます．次の条件を達成するために必要な最小の操作回数を求めてください．

S に登場するすべての o を () で，x を )( で置き換え，( と ) のみからなる文字列 S' を作る．この時，S' は括弧の対応が取れている文字列である．

括弧の対応が取れている文字列の定義

括弧の対応が取れている文字列とは，次のうちいずれかの条件を満たす文字列です．

空文字列
ある括弧の対応が取れている空でない文字列 s, t が存在し，s, t をこの順に連結した文字列
ある括弧の対応が取れている文字列 s が存在し、 (, s, ) をこの順に連結した文字列

なお，この問題の制約より，目標を達成することは必ず可能です．

制約

S は (, ), o, x からなる文字列
S は 1 つ以上の ( と ) を含み，またそれらの個数は等しい
|S| \leq 8000

入力

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

出力

答えを出力せよ．

入力例 1

)x(

出力例 1

)x( → x)( → x() → (x) と操作すればよいです．このとき，S'=()() であり，これは括弧の対応の取れている文字列です．

入力例 2

()ox

出力例 2

入力例 3

()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x

出力例 3

Score : 1000 points

Problem Statement

Given is a string S consisting of (, ), o, and x. You can swap two adjacent characters in S any number of times. Find the minimum number of swaps needed to satisfy the following condition.

Let us make a string S' consisting of ( and ) by replacing every occurrence of o with () and every occurrence of x with )( in S. Then, S' is a balanced parenthesis string.

Definition of a balanced parenthesis string

A balanced parenthesis string is a string that is one of the following:

an empty string;
a string that is a concatenation of s, t in this order, where s and t are some non-empty balanced parenthesis strings;
a string that is a concatenation of (, s, ) in this order, where s is some balanced parenthesis string.

Under the Constraints of this problem, it is always possible to achieve the objective.

Constraints

S is a string consisting of (, ), o, and x.
S contains the same non-zero number of (s and )s.
|S| \leq 8000

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

)x(

Sample Output 1

We should do as follows: )x( → x)( → x() → (x). Here, we have S'=()(), which is a balanced parenthesis string.

Sample Input 2

()ox

Sample Output 2

Sample Input 3

()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x

Sample Output 3

E - ZigZag Break

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

整数 N,A が与えられます． (1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) であって，以下の条件を満たすものの個数を 998244353 で割った余りを求めてください．

P_1=A
以下の操作を繰り返すことで，P の要素数を 2 にできる．
- 3 つの連続する要素 x,y,z を選ぶ．ただしこの時，y<\min(x,z) もしくは y>\max(x,z) が成り立っている必要がある．そして，y を P から消す．

一つの入力ファイルにつき，T 個のテストケースに答えてください．

制約

1 \leq T \leq 5 \times 10^5
3 \leq N \leq 10^6
1 \leq A \leq N
入力される値はすべて整数

入力

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

T
case_1
case_2
\vdots
case_T

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

N A

出力

各テストケースについて答えを出力せよ．

入力例 1

8
3 1
3 2
3 3
4 1
4 2
4 3
4 4
200000 10000

出力例 1

例えば，N=4,A=2 の時，P=(2,1,4,3) は条件を満たします．以下に手順の例を示します．

(x,y,z)=(2,1,4) を選び，1 を消す．P=(2,4,3) になる．
(x,y,z)=(2,4,3) を選び，4 を消す．P=(2,3) になる．

Score : 1200 points

Problem Statement

Given are integers N and A. Find the number, modulo 998244353, of permutations P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) that satisfy the following conditions.

P_1=A.
It is possible to repeat the following operation so that P has just two elements.
- Choose three consecutive elements x, y, and z. Here, y<\min(x,z) or y>\max(x,z) must hold. Then, erase y from P.

Solve T test cases in an input file.

Constraints

1 \leq T \leq 5 \times 10^5
3 \leq N \leq 10^6
1 \leq A \leq N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is in the following format:

N A

Output

Print the answer for each test case.

Sample Input 1

8
3 1
3 2
3 3
4 1
4 2
4 3
4 4
200000 10000

Sample Output 1

When N=4,A=2, one permutation that satisfies the condition is P=(2,1,4,3). One way to make it have just two elements is as follows.

Choose (x,y,z)=(2,1,4) to erase 1, resulting in P=(2,4,3).
Choose (x,y,z)=(2,4,3) to erase 4, resulting in P=(2,3).

F - Decrement

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1800 点

問題文

長さ N の正整数列 A 及び長さ N-1 の正整数列 B が与えられます．あなたは，次の操作を好きな回数行うことができます．

整数 i,j (1 \leq i < j \leq N) を選び，A_i,A_j,B_i,B_{i+1},\cdots,B_{j-1} の値をそれぞれ 1 減らす．ただし，操作後に負になる値が存在してはならない．

ここで，操作を行える回数の最大値を m とおきます． m 回の操作後の A としてありえる数列が何通りあるかを 998244353 で割った余りを求めてください．

制約

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
入力される値はすべて整数である

入力

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

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_{N-1}

出力

答えを出力せよ．

入力例 1

3
1 2 2
1 2

出力例 1

m=2 であり，最終的な A としては以下の 3 通りが考えられます．

A=(1,0,0): (i,j)=(2,3) と (i,j)=(2,3) で操作すればよい．
A=(0,1,0): (i,j)=(1,3) と (i,j)=(2,3) で操作すればよい．
A=(0,0,1): (i,j)=(1,2) と (i,j)=(2,3) で操作すればよい．

入力例 2

4
1 1 1 1
2 2 2

出力例 2

B の値が異なっていても A の値が同じなら区別しないことに注意してください．

入力例 3

4
2 2 3 4
3 1 4

出力例 3

Score : 1800 points

Problem Statement

Given is a sequence A of N positive integers and a sequence B of N-1 positive integers. You can do the following operation any number of times.

Choose integers i and j (1 \leq i < j \leq N) and decrease each of the following values by 1: A_i,A_j,B_i,B_{i+1},\cdots,B_{j-1}. Here, there should not be any negative value after this operation.

Let m be the maximum number of operations that can be done. Find the number, modulo 998244353, of sequences that A can be after m operations.

Constraints

1 \leq N \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
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_{N-1}

Output

Print the answer.

Sample Input 1

3
1 2 2
1 2

Sample Output 1

We have m=2. After two operations, A will be one of the following three sequences.

A=(1,0,0): we end up with this after operations with (i,j)=(2,3) and (i,j)=(2,3).
A=(0,1,0): we end up with this after operations with (i,j)=(1,3) and (i,j)=(2,3).
A=(0,0,1): we end up with this after operations with (i,j)=(1,2) and (i,j)=(2,3).

Sample Input 2

4
1 1 1 1
2 2 2

Sample Output 2

Note that we do not distinguish two scenarios with different contents of B if the contents of A are the same.

Sample Input 3

4
2 2 3 4
3 1 4