E - Reversible

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

配点 : 300 点

問題文

ボールがいくつか刺さった棒が N 本あり、各ボールには英小文字が 1 個書かれています。

i = 1, 2, \ldots, N について、i 番目の棒に刺さった各ボールの英小文字は、文字列 S_i によって表されます。 具体的には、i 番目の棒には文字列 S_i の長さ |S_i| に等しい個数のボールが刺さっており、 刺さっているボールの英小文字を、棒のある端から順に並べたものは文字列 S_i と等しいです。

2 つの棒は、一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列と、もう一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列が一致するとき、同じ棒とみなされます。 より形式的には、1 以上 N 以下の整数 i, j について、i 本目の棒と j 本目の棒は、S_i が S_j と一致するか、S_i が S_j を前後反転したものと一致するとき、かつそのときに限り、同じとみなされます。

N 本の棒の中に、何種類の異なる棒があるかを出力してください。

制約

  • N は整数
  • 2 \leq N \leq 2 \times 10^5
  • S_i は英小文字のみからなる文字列
  • |S_i| \geq 1
  • \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。


入力例 1

6
a
abc
de
cba
de
abc

出力例 1

3
  • S_2 = abc が S_4 = cba を前後反転したものと一致するため、2 番目の棒と 4 番目の棒は同じとみなされます。
  • S_2 = abc が S_6 = abc と一致するため、2 番目の棒と 6 番目の棒は同じとみなされます。
  • S_3 = de が S_5 = de と一致するため、3 番目の棒と 5 番目の棒は同じとみなされます。

よって、6 本の棒の中に、1 本目の棒、2 本目の棒( 4, 6 本目の棒と同じ)、3 本目の棒( 5 本目の棒と同じ)の 3 種類の異なる棒があります。

Score : 300 points

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

  • N is an integer.
  • 2 \leq N \leq 2 \times 10^5
  • S_i is a string consisting of lowercase English letters.
  • |S_i| \geq 1
  • \sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.


Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

3
  • S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
  • S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
  • S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

F - Rotate and Palindrome

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

配点 : 300 点

問題文

長さ N の文字列 S が与えられます。S_i\ (1\leq i \leq N) を S の左から i 番目の文字とします。

あなたは以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことができます。

  • A 円払う。 S の左端の文字を右端に移動する。すなわち、S_1S_2\ldots S_N を S_2\ldots S_NS_1 に変える。

  • B 円払う。 1 以上 N 以下の整数 i を選び、 S_i を好きな英小文字で置き換える。

S を回文にするためには最低で何円必要ですか?

回文とは ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 T は回文です。

制約

  • 1\leq N \leq 5000
  • 1\leq A,B\leq 10^9
  • S は英小文字からなる長さ N の文字列
  • S 以外の入力は全て整数

入力

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

N A B
S

出力

答えを整数として出力せよ。


入力例 1

5 1 2
rrefa

出力例 1

3

最初に 2 番目の操作を 1 回行います。2 円払い、i=5 として S_5 を e で置き換えます。 S は rrefe となります。

次に 1 番目の操作を 1 回行います。1 円払い、S は refer となります。これは回文です。

よって 3 円払うことで S を回文にすることができました。 2 円以下払うことで S を回文にすることは不可能なので、これが答えです。


入力例 2

8 1000000000 1000000000
bcdfcgaa

出力例 2

4000000000

答えは 32 bit 整数に収まらない場合があることに注意してください。

Score : 300 points

Problem Statement

You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.

You may perform the following two kinds of operations zero or more times in any order:

  • Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.

  • Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.

How many yen do you need to pay to make S a palindrome?

What is a palindrome? A string T is a palindrome if and only if the i-th character from the left and the i-th character from the right are the same for all integers i (1 \le i \le |T|), where |T| is the length of T.

Constraints

  • 1\leq N \leq 5000
  • 1\leq A,B\leq 10^9
  • S is a string of length N consisting of lowercase English letters.
  • All values in the input except for S are integers.

Input

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

N A B
S

Output

Print the answer as an integer.


Sample Input 1

5 1 2
rrefa

Sample Output 1

3

First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.

Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.

Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.


Sample Input 2

8 1000000000 1000000000
bcdfcgaa

Sample Output 2

4000000000

Note that the answer may not fit into a 32-bit integer type.

G - Index × A(Not Continuous ver.)

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

配点 : 400 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

長さ M の A の部分列(連続でなくてもよい) B=(B_1,B_2,\dots,B_M) に対する、\displaystyle \sum_{i=1}^{M} i \times B_i の最大値を求めてください。

注記

数列の部分列とは、数列から 0 個以上の要素を取り除いた後、残りの要素を元の順序で連結して得られる数列のことをいいます。

例えば、(10,30) は (10,20,30) の部分列ですが、(20,10) は (10,20,30) の部分列ではありません。

制約

  • 1 \le M \le N \le 2000
  • - 2 \times 10^5 \le A_i \le 2 \times 10^5
  • 入力は全て整数。

入力

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

N M
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

4 2
5 4 -1 8

出力例 1

21

B=(A_1,A_4) とした場合、\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21 となります。22 以上の値を達成することはできないため、解は 21 です。


入力例 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

出力例 2

54

Score : 400 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a (not necessarily contiguous) subsequence B=(B_1,B_2,\dots,B_M) of length M of A.

Notes

A subsequence of a number sequence is a sequence that is obtained by removing 0 or more elements from the original number sequence and concatenating the remaining elements without changing the order.

For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not a subsequence of (10,20,30).

Constraints

  • 1 \le M \le N \le 2000
  • - 2 \times 10^5 \le A_i \le 2 \times 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N

Output

Print the answer.


Sample Input 1

4 2
5 4 -1 8

Sample Output 1

21

When B=(A_1,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21. Since it is impossible to achieve 22 or a larger value, the solution is 21.


Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

54
H - Christmas Color Grid 1

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

配点 : 450 点

問題文

この問題は問題 G と似た設定です。問題文の相違点を赤字で示します。

H 行 W 列のグリッドがあり、グリッドの各マスは赤色あるいは緑色に塗られています。

グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表記します。

マス (i,j) の色は文字 S_{i,j} で表され、S_{i,j} = . のときマス (i,j) は赤色、S_{i,j} = # のときマス (i,j) は緑色に塗られています。

グリッドにおいて、緑色に塗られたマスを頂点集合、隣り合った 2 つの緑色のマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を 緑の連結成分数 と呼びます。ただし、2 つのマス (x,y) と (x',y') が隣り合っているとは、|x-x'| + |y-y'| = 1 であることを指します。

赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えたとき、塗り替え後のグリッドの緑の連結成分数の期待値を \text{mod } 998244353 で出力してください。

「期待値を \text{mod } 998244353 で出力」とは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、 R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ 1 つ存在することが証明できます。この R を出力してください。

制約

  • 1 \leq H,W \leq 1000
  • S_{i,j} = . または S_{i,j} = #
  • S_{i,j} = . なる (i,j) が存在する。

入力

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

出力

答えを出力せよ。


入力例 1

3 3
##.
#.#
#..

出力例 1

499122178

マス (1,3) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (2,2) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (3,2) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

マス (3,3) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

よって、赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えた後の緑の連結成分数の期待値は (1+1+2+2)/4 = 3/2 となります。


入力例 2

4 5
..#..
.###.
#####
..#..

出力例 2

598946613

入力例 3

3 4
#...
.#.#
..##

出力例 3

285212675

Score : 450 points

Problem Statement

This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.

There is a grid with H rows and W columns, where each cell is painted red or green.

Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.

The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.

Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

What does "print the expected value modulo 998244353" mean? It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. Print this R.

Constraints

  • 1 \leq H,W \leq 1000
  • S_{i,j} = . or S_{i,j} = #.
  • There is at least one (i,j) such that S_{i,j} = ..

Input

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Print the answer.


Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.

If cell (2,2) is repainted green, the number of green connected components becomes 1.

If cell (3,2) is repainted green, the number of green connected components becomes 2.

If cell (3,3) is repainted green, the number of green connected components becomes 2.

Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.


Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675
I - Earn to Advance

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 550 点

問題文

縦 N 行横 N 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。

高橋君は最初マス (1,1) におり、所持金は 0 です。

高橋君はマス (i,j) にいるとき、1 回の行動で以下のいずれかを行うことができます。

  • 同じマスにとどまり、所持金を P_{i,j} 増やす。
  • 所持金から R_{i,j} 払ってマス (i,j+1) に移動する。
  • 所持金から D_{i,j} 払ってマス (i+1,j) に移動する。

所持金が負になる移動、グリッドの外に出る移動はできません。

高橋君が最適に行動したとき、何回の行動でマス (N,N) にたどり着くことができますか。

制約

  • 2 \leq N \leq 80
  • 1 \leq P_{i,j} \leq 10^9
  • 1 \leq R_{i,j},D_{i,j} \leq 10^9
  • 入力は全て整数である

入力

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

N
P_{1,1} \ldots P_{1,N}
\vdots
P_{N,1} \ldots P_{N,N}
R_{1,1} \ldots R_{1,N-1}
\vdots
R_{N,1} \ldots R_{N,N-1}
D_{1,1} \ldots D_{1,N}
\vdots
D_{N-1,1} \ldots D_{N-1,N}

出力

答えを出力せよ。


入力例 1

3
1 2 3
3 1 2
2 1 1
1 2
4 3
4 2
1 5 7
5 3 3

出力例 1

8

図

以下のようにして 8 回の行動でマス (3,3) にたどり着くことができます。

  • マス (1,1) にとどまり、所持金を 1 増やす。所持金は 1 になる。
  • 所持金から 1 払ってマス (2,1) に移動する。所持金は 0 になる。
  • マス (2,1) にとどまり、所持金を 3 増やす。所持金は 3 になる。
  • マス (2,1) にとどまり、所持金を 3 増やす。所持金は 6 になる。
  • マス (2,1) にとどまり、所持金を 3 増やす。所持金は 9 になる。
  • 所持金から 4 払ってマス (2,2) に移動する。所持金は 5 になる。
  • 所持金から 3 払ってマス (3,2) に移動する。所持金は 2 になる。
  • 所持金から 2 払ってマス (3,3) に移動する。所持金は 0 になる。

入力例 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

出力例 2

4000000004

Score: 550 points

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

Takahashi is initially at square (1,1) with zero money.

When Takahashi is at square (i,j), he can perform one of the following in one action:

  • Stay at the same square and increase his money by P_{i,j}.
  • Pay R_{i,j} from his money and move to square (i,j+1).
  • Pay D_{i,j} from his money and move to square (i+1,j).

He cannot make a move that would make his money negative or take him outside the grid.

If Takahashi acts optimally, how many actions does he need to reach square (N,N)?

Constraints

  • 2 \leq N \leq 80
  • 1 \leq P_{i,j} \leq 10^9
  • 1 \leq R_{i,j},D_{i,j} \leq 10^9
  • All input values are integers.

Input

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

N
P_{1,1} \ldots P_{1,N}
\vdots 
P_{N,1} \ldots P_{N,N}
R_{1,1} \ldots R_{1,N-1}
\vdots
R_{N,1} \ldots R_{N,N-1}
D_{1,1} \ldots D_{1,N}
\vdots
D_{N-1,1} \ldots D_{N-1,N}

Output

Print the answer.


Sample Input 1

3
1 2 3
3 1 2
2 1 1
1 2
4 3
4 2
1 5 7
5 3 3

Sample Output 1

8

Figure

It is possible to reach square (3,3) in eight actions as follows:

  • Stay at square (1,1) and increase money by 1. His money is now 1.
  • Pay 1 money and move to square (2,1). His money is now 0.
  • Stay at square (2,1) and increase money by 3. His money is now 3.
  • Stay at square (2,1) and increase money by 3. His money is now 6.
  • Stay at square (2,1) and increase money by 3. His money is now 9.
  • Pay 4 money and move to square (2,2). His money is now 5.
  • Pay 3 money and move to square (3,2). His money is now 2.
  • Pay 2 money and move to square (3,3). His money is now 0.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Sample Output 2

4000000004