A - Right String

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

配点 : 300

問題文

英小文字からなる文字列 T に対して次の問題を考え、その答えを f(T) とします。

T の先頭の文字を削除し末尾に追加する操作を任意の回数行うことによって作ることのできる文字列の種類数を求めてください。

英小文字からなる長さ N の文字列 S が与えられます。あなたは以下の操作を K 回以下行うことが出来ます。(1 回も行わなくてもよいです。)

  • S の文字を 1 個選び、任意の英小文字に変更する。

操作終了後の f(S) の値としてあり得る最小値を求めてください。

制約

  • 1 \le N \le 2000
  • 0 \le K \le N
  • S は英小文字からなる長さ N の文字列である。
  • N,K は整数である。

入力

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

N K
S

出力

答えを出力せよ。


入力例 1

4 1
abac

出力例 1

2

1 回目の操作で 4 文字目を c から b に変更すると S= abab となり、f(S)=2 となります。

f(S)1 回以下の操作で 1 以下にすることはできないため、答えは 2 です。


入力例 2

10 0
aaaaaaaaaa

出力例 2

1

入力例 3

6 1
abcaba

出力例 3

3

Score : 300 points

Problem Statement

For a string T consisting of lowercase English letters, consider the question below, and let f(T) be the answer.

Find the number of different strings obtained by performing the following operation any number of times: delete the first character from T and append it to the end.

You are given a string S of length N consisting of lowercase English letters. You can perform the operation below at most K times (possibly zero).

  • Choose a character of S and change it to any lowercase English letter.

Find the minimum possible value of f(S) after your operations.

Constraints

  • 1 \le N \le 2000
  • 0 \le K \le N
  • S is a string of length N consisting of lowercase English letters.
  • N and K are integers.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the answer.


Sample Input 1

4 1
abac

Sample Output 1

2

If you change the fourth character c to b in the first operation, you get S= abab, with f(S)=2.

f(S) cannot be made 1 or less in one or fewer operations, so the answer is 2.


Sample Input 2

10 0
aaaaaaaaaa

Sample Output 2

1

Sample Input 3

6 1
abcaba

Sample Output 3

3
B - Shorten ARC

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

配点 : 400

問題文

A,R,C からなる長さ N の文字列 S が与えられます。

あなたは、S の中に隣接する 3 文字であって ARCとなっているものが存在する限り以下の操作を行うことができます。

  • 奇数 回目の操作では、S の中で隣接する 3 文字であって ARC となっているものを一つ選び、R で置き換える。

  • 偶数 回目の操作では、S の中で隣接する 3 文字であって ARC となっているものを一つ選び、AC で置き換える。

操作を行える回数の最大値を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • SA,R,C からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

6
AARCCC

出力例 1

2

以下のように操作すると、 2 回操作できます。

AARCCCARCCACC


入力例 2

5
AAAAA

出力例 2

0

S の中に隣接する 3 文字であって ARC となっているものが存在しないため、操作を一度も行えません。


入力例 3

9
ARCARCARC

出力例 3

3

Score : 400 points

Problem Statement

You are given a string S of length N consisting of A,R,C.

As long as S contains three consecutive characters that are ARC, you can perform the operation below.

  • In an odd-numbered (1-st, 3-rd, 5-th, ...) operation, choose in S three consecutive characters that are ARC, and replace them with R.
  • In an even-numbered (2-nd, 4-th, 6-th, ...) operation, choose in S three consecutive characters that are ARC, and replace them with AC.

Find the maximum number of operations that can be performed.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • S is a string of length N consisting of A,R,C.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.


Sample Input 1

6
AARCCC

Sample Output 1

2

You can perform two operations as follows.

AARCCCARCCACC


Sample Input 2

5
AAAAA

Sample Output 2

0

S does not contain three consecutive characters that are ARC, so you cannot perform the operation at all.


Sample Input 3

9
ARCARCARC

Sample Output 3

3
C - ABS Permutation (LIS ver.)

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

配点 : 500

問題文

(1,\dots,N) の順列 P=(P_1,P_2,\ldots,P_N)嬉しさを以下で定義します。

  • 長さ N-1 の数列 A=(A_1,A_2,\ldots,A_{N-1}) を、A_i = |P_i-P_{i+1}|(1\leq i \leq N-1) で定める。 A の最長狭義単調増加部分列の長さを P の嬉しさとする。

P_1 = X を満たす順列 P のうち、嬉しさが最大になるものを一つ出力してください。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq X \leq N
  • 入力は全て整数

入力

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

N X

出力

P_1 = X を満たす順列 P のうち、嬉しさが最大になるものを 1 つ以下の形式で出力せよ。

P_1 P_2 \ldots P_N

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。


入力例 1

3 2

出力例 1

2 1 3

A=(1,2) となるので、P の嬉しさは 2 です。これが達成可能な嬉しさの最大であるため、出力は条件を満たします。


入力例 2

3 1

出力例 2

1 2 3

A=(1,1) となるので、P の嬉しさは 1 です。これが達成可能な嬉しさの最大であるため、出力は条件を満たします。

Score : 500 points

Problem Statement

The happiness of a permutation P=(P_1,P_2,\ldots,P_N) of (1,\dots,N) is defined as follows.

  • Let A=(A_1,A_2,\ldots,A_{N-1}) be a sequence of length N-1 with A_i = |P_i-P_{i+1}|(1\leq i \leq N-1). The happiness of P is the length of a longest strictly increasing subsequence of A.

Print a permutation P such that P_1 = X with the greatest happiness.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq X \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print a permutation P such that P_1 = X with the greatest happiness, in the following format:

P_1 P_2 \ldots P_N

If there are multiple solutions, printing any of them will be accepted.


Sample Input 1

3 2

Sample Output 1

2 1 3

Since A=(1,2), the happiness of P is 2, which is the greatest happiness achievable, so the output meets the requirement.


Sample Input 2

3 1

Sample Output 2

1 2 3

Since A=(1,1), the happiness of P is 1, which is the greatest happiness achievable, so the output meets the requirement.

D - One to One

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

配点 : 700

問題文

全ての要素が 1 以上 N 以下である長さ N の整数列 X=(X_1,X_2,\dots,X_N) に対して次の問題を考え、その答えを f(X) とします。

N 頂点の無向グラフ G があります。(G は多重辺や自己ループを含むことがあります。) G の辺は N 本あり、そのうち i 番目の辺は頂点 i と頂点 X_i を繋ぐ辺です。G の連結成分の個数を求めてください。

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。各 A_i1 以上 N 以下の整数あるいは -1 です。

全ての要素が 1 以上 N 以下である長さ N の整数列 X=(X_1,X_2,\dots,X_N) であって、A_i \neq -1 \Rightarrow A_i = X_i を満たすものを考えます。そのような全ての X に対する f(X) の総和を 998244353 で割ったあまりを求めてください。

制約

  • 1 \le N \le 2000
  • A_i1 以上 N 以下あるいは -1 である。
  • 入力は全て整数である。

入力

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

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

3
-1 1 3

出力例 1

5

X として条件を満たすものは以下の 3 通りがあります。

  • X=(1,1,3) の時、問題の答えは 2 です。
  • X=(2,1,3) の時、問題の答えは 2 です。
  • X=(3,1,3) の時、問題の答えは 1 です。

よって答えは 2+2+1=5 です。


入力例 2

1
1

出力例 2

1

入力例 3

8
-1 3 -1 -1 8 -1 -1 -1

出力例 3

433760

Score : 700 points

Problem Statement

For an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N (inclusive), consider the question below, and let f(X) be the answer.

There is an undirected graph G with N vertices (and possibly multi-edges and self-loops). G has N edges, the i-th of which connects Vertex i and Vertex X_i. Find the number of connected components in G.

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N, where each A_i is an integer between 1 and N (inclusive) or -1.

Consider an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N such that A_i \neq -1 \Rightarrow A_i = X_i. Find the sum of f(X) over all such X, modulo 998244353.

Constraints

  • 1 \le N \le 2000
  • A_i is between 1 and N (inclusive) or -1.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Prin the answer.


Sample Input 1

3
-1 1 3

Sample Output 1

5

There are three sequences X satisfying the requirement, as follows.

  • X=(1,1,3), for which the answer to the question is 2.
  • X=(2,1,3), for which the answer to the question is 2.
  • X=(3,1,3), for which the answer to the question is 1.

Thus, the answer is 2+2+1=5.


Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

8
-1 3 -1 -1 8 -1 -1 -1

Sample Output 3

433760
E - Not Equal Rectangle

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

配点 : 800

問題文

N \times M のマス目があり、あなたはこれから全てのマスに 1 以上 25 以下の整数を 1 つずつ書き込みます。上から i 行目、左から j 列目のマスに書き込む整数を a_{i,j} とします。

以下の条件を満たす整数の書き込み方を一つ求めてください。本問題の制約下で、条件を満たす整数の書き込み方が必ず存在することが証明できます。

  • 任意の整数 1\leq x_1 < x_2\leq N,1\leq y_1 < y_2 \leq M について、a_{x_1,y_1},a_{x_1,y_2},a_{x_2,y_1},a_{x_2,y_2} が全て一致してはならない。

制約

  • 2 \leq N , M \leq 500
  • 入力は全て整数

入力

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

N M 

出力

条件を満たす書き込み方の 1 つを、以下の形式で出力せよ。

a_{1,1} a_{1,2} \ldots a_{1,M}
a_{2,1} a_{2,2} \ldots a_{2,M}
\vdots
a_{N,1} a_{N,2} \ldots a_{N,M}

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。


入力例 1

2 3

出力例 1

1 1 1
1 2 3

(x_1,x_2,y_1,y_2) の組として考えられるのは (1,2,1,2),(1,2,2,3),(1,2,1,3)3 つです。

どの組についても 4 マスに書かれた数字が全て一致してはいないので、この出力は条件を満たします。

Score : 800 points

Problem Statement

We have a grid with N \times M squares. You will fill every square with an integer between 1 and 25 (inclusive). Let a_{i,j} be the integer to be written in the square at the i-th row from the top and j-th column from the left.

Find a way to fill the squares to satisfy the condition below. It can be proved that, under the Constraints of this problem, such a way always exists.

  • For any integers 1\leq x_1 < x_2\leq N,1\leq y_1 < y_2 \leq M, it must not be the case that a_{x_1,y_1},a_{x_1,y_2},a_{x_2,y_1},a_{x_2,y_2} are all equal.

Constraints

  • 2 \leq N , M \leq 500
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M 

Output

Print one way to fill the squares to satisfy the condition, in the format below:

a_{1,1} a_{1,2} \ldots a_{1,M}
a_{2,1} a_{2,2} \ldots a_{2,M}
\vdots
a_{N,1} a_{N,2} \ldots a_{N,M}

If there are multiple solutions, printing any of them will be accepted.


Sample Input 1

2 3

Sample Output 1

1 1 1
1 2 3

(x_1,x_2,y_1,y_2) can be one of (1,2,1,2),(1,2,2,3),(1,2,1,3).

For any of them, the numbers written in the squares are not all equal, so this output satisfies the condition.

F - ABS Permutation (Count ver.)

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

配点 : 900

問題文

(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) のうち、以下を満たすものの個数を 998244353 で割ったあまりを各 K=0,1,2,\dots,N-1 に対して求めてください。

  • 1 \le i \le N-1 を満たす整数 i のうち、|P_i - P_{i+1}|=M を満たすものがちょうど K 個ある。

制約

  • 2 \le N \le 250000
  • 1 \le M \le N-1
  • 入力は全て整数である。

入力

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

N M

出力

K=0,1,2,\dots,N-1 に対して、条件を満たす順列の個数を 998244353 で割ったあまりを出力せよ。


入力例 1

3 1

出力例 1

0 4 2 
  • K=0 の時は条件を満たす順列 P は存在しません。
  • K=1 の時は条件を満たす順列 P(1,3,2),(2,1,3),(2,3,1),(3,1,2)4 個あります。
  • K=2 の時は条件を満たす順列 P(1,2,3),(3,2,1)2 個あります。

入力例 2

4 3

出力例 2

12 12 0 0 

入力例 3

10 5

出力例 3

1263360 1401600 710400 211200 38400 3840 0 0 0 0 

Score : 900 points

Problem Statement

Find the number of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) that satisfy the following, modulo 998244353, for each K=0,1,2,\dots,N-1.

  • There are exactly K integers i such that 1 \le i \le N-1 and |P_i - P_{i+1}|=M.

Constraints

  • 2 \le N \le 250000
  • 1 \le M \le N-1
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of permutations that satisfy the condition, modulo 998244353, for each K=0,1,2,\dots,N-1.


Sample Input 1

3 1

Sample Output 1

0 4 2 
  • For K=0, the condition is satisfied by no permutations P.
  • For K=1, the condition is satisfied by four permutations P: (1,3,2),(2,1,3),(2,3,1),(3,1,2).
  • For K=2, the condition is satisfied by two permutations P: (1,2,3),(3,2,1).

Sample Input 2

4 3

Sample Output 2

12 12 0 0 

Sample Input 3

10 5

Sample Output 3

1263360 1401600 710400 211200 38400 3840 0 0 0 0