AtCoder Daily Training HARD 2024/10/29 19:30start

E - Cross

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 H マス横 W マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスには # と . のいずれかの文字が書かれています。(i, j) に書かれている文字を C[i][j] とします。また、整数 i, j が 1 \leq i \leq H と 1 \leq j \leq W の少なくとも一方を満たさない場合、 C[i][j] を . と定義します。

正整数 a, b, n が以下の条件を全て満たす時、(a,b) および (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n) の 4n + 1 マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。

C[a][b] は # である。
1 \leq d \leq n を満たす整数 d について、 C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d] はいずれも # である。
C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1] のうち少なくとも 1 つは . である。

例えば次の図で示された例では、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印がグリッド上にあります。

グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。
また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは (3, 3) と (4, 4) が頂点を共有しているのが条件に反しています。

N = \min(H, W) とします。また、サイズ n のバツ印の個数を S_n とします。S_1, S_2, \dots, S_N を計算してください。

制約

3 \leq H, W \leq 100
C[i][j] は # または .
異なるバツ印を構成するマス同士は頂点を共有しない
H, W は整数

入力

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

出力

S_1, S_2, \dots, S_N を空白区切りで出力せよ。

入力例 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

出力例 1

1 1 0 0 0

問題文に書かれた説明の通り、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印が書かれています。

入力例 2

3 3
...
...
...

出力例 2

0 0 0

バツ印が 1 個も書かれていない場合もあります。

入力例 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

出力例 3

3 0 0

入力例 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

出力例 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

C[a][b] is #.
C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

3 \leq H, W \leq 100
C[i][j] is # or ..
No two different squares that comprise two different crosses share a corner.
H and W are integers.

Input

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

Output

Print S_1, S_2, \dots, and S_N, separated by spaces.

Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

F - One More aab aba baa

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から K 番目にくる文字列を求めてください。

「各文字を並べ替えて作ることが可能な文字列」とは？

「文字列 A が文字列 B の各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列 A と文字列 B に同数含まれるということを指します。

制約

1 \le |S| \le 8
S は英小文字のみからなる
S の各文字を並べ替えてできる文字列は K 種類以上存在する

入力

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

S K

出力

答えを出力せよ。

入力例 1

aab 2

出力例 1

aba

文字列 aab の各文字を並べ替えて作ることが可能な文字列は \{ aab, aba, baa \} の 3 つですが、このうち辞書順で前から 2 番目にくるものは aba です。

入力例 2

baba 4

出力例 2

baab

入力例 3

ydxwacbz 40320

出力例 3

zyxwdcba

Score : 300 points

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

What is a permutation of a string?

A string A is said to be a permutation of a string B when any character occurs the same number of times in A and B.

Constraints

1 \le |S| \le 8
S consists of lowercase English letters.
There are at least K distinct strings that are permutations of S.

Input

Input is given from Standard Input in the following format:

S K

Output

Print the answer.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

G - Unique Username

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はあるサービスで使うユーザー名を決めるのに困っています。彼を助けるプログラムを書いてください。

以下の条件をすべて満たす文字列 X を 1 つ求めてください。

X は次の手順で得られる文字列である。
- N 個の文字列 S_1,S_2,\ldots,S_N を好きな順番で並べたものを S_1', S_2', \ldots,S_N' とする。そして、S_1'、( 1 個以上の _ )、S_2'、( 1 個以上の _ )、\ldots、( 1 個以上の _ )、S_N' をこの順番で連結したものを X とする。
X の文字数は 3 以上 16 以下である。
X は M 個の文字列 T_1,T_2,\ldots,T_M のいずれとも一致しない。

ただし、条件をすべて満たす文字列 X が存在しない場合は代わりに -1 と出力してください。

制約

1 \leq N \leq 8
0 \leq M \leq 10^5
N,M は整数
1 \leq |S_i| \leq 16
N-1+\sum{|S_i|} \leq 16
i \neq j ならば S_i \neq S_j
S_i は英小文字のみからなる文字列
3 \leq |T_i| \leq 16
i \neq j ならば T_i \neq T_j
T_i は英小文字と _ のみからなる文字列

入力

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

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

出力

条件をすべて満たす文字列 X を 1 つ出力せよ。ただし、条件をすべて満たす文字列 X が存在しない場合は代わりに -1 を出力せよ。
答えが複数存在する場合、どれを出力しても良い。

入力例 1

1 1
chokudai
chokudai

出力例 1

-1

条件のうち 1 番目と 2 番目を満たす文字列は X= chokudai しかありませんが、これは T_1 と一致します。
このため、条件をすべて満たす文字列 X が存在せず、-1 が正しい出力となります。

入力例 2

2 2
choku
dai
chokudai
choku_dai

出力例 2

dai_choku

この他に、choku__dai (choku と dai の間の _ が 2 つ) 等も条件をすべて満たします。

入力例 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

出力例 3

-1

chokudai__atcoder や atcoder__chokudai (chokudai と atcoder の間の _ が 2 つ)は文字数が 17 なので 2 番目の条件を満たしません。

入力例 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

出力例 4

ab__ef___cd_gh

1 番目の条件で記述されている操作で得られないような文字列が T_i として与えられる場合があります。

Score : 400 points

Problem Statement

Takahashi is having trouble with deciding a username for a service. Write a code to help him.

Find a string X that satisfies all of the following conditions:

X is obtained by the following procedure:
- Let S_1', S_2', \ldots,S_N' be a permutation of S_1, S_2, \ldots,S_N. Let X be the concatenation of S_1', (1 or more copies of _), S_2', (1 or more copies of _), \ldots, (1 or more copies of _), and S_N', in this order.
The length of X is between 3 and 16, inclusive.
X does not coincide with any of M strings T_1,T_2,\ldots,T_M.

If there is no X that satisfies all of the conditions, print -1 instead.

Constraints

1 \leq N \leq 8
0 \leq M \leq 10^5
N and M are integers.
1 \leq |S_i| \leq 16
N-1+\sum{|S_i|} \leq 16
S_i \neq S_j if i \neq j.
S_i is a string consisting of lowercase English letters.
3 \leq |T_i| \leq 16
T_i \neq T_j if i \neq j.
T_i is a string consisting of lowercase English letters and _.

Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

Output

Print a string X that satisfies all of the conditions. If there is no X that satisfies all of the conditions, print -1 instead.
If there are multiple solutions, print any of them.

Sample Input 1

1 1
chokudai
chokudai

Sample Output 1

-1

The only string that satisfies the first and second conditions is X= chokudai, but it coincides with T_1.
Thus, there is no X that satisfies all of the conditions, so -1 should be printed.

Sample Input 2

2 2
choku
dai
chokudai
choku_dai

Sample Output 2

dai_choku

Strings like choku__dai (which has two _'s between choku and dai) also satisfy all of the conditions.

Sample Input 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

Sample Output 3

-1

chokudai__atcoder and atcoder__chokudai (which have two _'s between chokudai and atcoder) have a length of 17, which violates the second condition.

Sample Input 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

Sample Output 4

ab__ef___cd_gh

The given T_i may contain a string that cannot be obtained by the procedure described in the first condition.

H - Grid Filling

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

縦 H 行、横 W 列のグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) で表します。 (i,j)\ (1\leq i\leq H,1\leq j\leq W) には 1 以上 N 以下の整数 A _ {i,j} が書かれています。

整数 h,w が与えられます。0\leq k\leq H-h,0\leq l\leq W-w を満たすすべての (k,l) の組について、次の問題を解いてください。

k\lt i\leq k+h,l\lt j\leq l+w を満たす (i,j) を塗りつぶしたとき、塗りつぶされていないマスに書かれている数が何種類あるか求めよ。

ただし、問題を解く際に実際にマスを塗りつぶすことはない（各問題が独立である）ことに注意してください。

制約

1 \leq H,W,N \leq 300
1 \leq h \leq H
1 \leq w \leq W
(h,w)\neq(H,W)
1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)
入力される値はすべて整数

入力

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

H W N h w
A _ {1,1} A _ {1,2} \dots A _ {1,W}
A _ {2,1} A _ {2,2} \dots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \dots A _ {H,W}

出力

(k,l) に対する答えを \operatorname{ans}_{k,l} として、以下の形式で出力せよ。

\operatorname{ans} _ {0,0} \operatorname{ans} _ {0,1} \dots \operatorname{ans} _ {0,W-w}
\operatorname{ans} _ {1,0} \operatorname{ans} _ {1,1} \dots \operatorname{ans} _ {1,W-w}
\vdots
\operatorname{ans} _ {H-h,0} \operatorname{ans} _ {H-h,1} \dots \operatorname{ans} _ {H-h,W-w}

入力例 1

出力例 1

4 4 3
5 3 4

与えられた盤面は下の図のようになります。

例えば、(k,l)=(0,0) のときは塗りつぶされていないマスに書かれている数は 1,3,4,5 の 4 種類なので、4 が答えになります。

入力例 2

5 6 9 3 4
7 1 5 3 9 5
4 5 4 5 1 2
6 1 6 2 9 7
4 7 1 5 8 8
3 4 3 3 5 3

出力例 2

8 8 7
8 9 7
8 9 8

入力例 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

出力例 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17

Score : 500 points

Problem Statement

You have a grid with H rows from top to bottom and W columns from left to right. We denote by (i, j) the square at the i-th row from the top and j-th column from the left. (i,j)\ (1\leq i\leq H,1\leq j\leq W) has an integer A _ {i,j} between 1 and N written on it.

You are given integers h and w. For all pairs (k,l) such that 0\leq k\leq H-h and 0\leq l\leq W-w, solve the following problem:

If you black out the squares (i,j) such that k\lt i\leq k+h and l\lt j\leq l+w, how many distinct integers are written on the squares that are not blacked out?

Note, however, that you do not actually black out the squares (that is, the problems are independent).

Constraints

1 \leq H,W,N \leq 300
1 \leq h \leq H
1 \leq w \leq W
(h,w)\neq(H,W)
1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)
All values in the input are integers.

Input

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

H W N h w
A _ {1,1} A _ {1,2} \dots A _ {1,W}
A _ {2,1} A _ {2,2} \dots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \dots A _ {H,W}

Output

Print the answers in the following format, where \operatorname{ans}_{k,l} denotes the answer to (k, l):

\operatorname{ans} _ {0,0} \operatorname{ans} _ {0,1} \dots \operatorname{ans} _ {0,W-w}
\operatorname{ans} _ {1,0} \operatorname{ans} _ {1,1} \dots \operatorname{ans} _ {1,W-w}
\vdots
\operatorname{ans} _ {H-h,0} \operatorname{ans} _ {H-h,1} \dots \operatorname{ans} _ {H-h,W-w}

Sample Input 1

Sample Output 1

4 4 3
5 3 4

The given grid is as follows:

For example, when (k,l)=(0,0), four distinct integers 1,3,4, and 5 are written on the squares that are not blacked out, so 4 is the answer.

Sample Input 2

5 6 9 3 4
7 1 5 3 9 5
4 5 4 5 1 2
6 1 6 2 9 7
4 7 1 5 8 8
3 4 3 3 5 3

Sample Output 2

8 8 7
8 9 7
8 9 8

Sample Input 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

Sample Output 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17

I - Reordering

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

文字列 S が与えられます。S の空でない、連続するとは限らない部分列を並び替えて得られる文字列は何種類ありますか？

答えは非常に大きくなる場合があるので、998244353 で割ったあまりを出力してください。

制約

S は英小文字のみからなる長さ 1 以上 5000 以下の文字列

入力

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

出力

S の部分列を並び替えて得られる文字列の種類数を 998244353 で割ったあまりを出力せよ。

入力例 1

aab

出力例 1

S の部分列を並び替えて得られる文字列は、a, b, aa, ab, ba, aab, aba, baa の 8 種類です。

入力例 2

aaa

出力例 2

入力例 3

abcdefghijklmnopqrstuvwxyz

出力例 3

149621752

998244353 で割ったあまりを出力することに注意してください。

Score : 500 points

Problem Statement

Given is a string S. How many different strings can be obtained as a permutation of a non-empty, not necessarily contiguous subsequence of S?

Since the count can be enormous, print it modulo 998244353.

Constraints

S is a string of length 1 and 5000 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

Output

Print the number of different strings that can be obtained as a permutation of a subsequence of S, modulo 998244353.

Sample Input 1

aab

Sample Output 1

There are 8 different strings that can be obtained as a permutation of a subsequence of S: a, b, aa, ab, ba, aab, aba, baa.

Sample Input 2

aaa

Sample Output 2

Sample Input 3

abcdefghijklmnopqrstuvwxyz

Sample Output 3

149621752

Be sure to print the count modulo 998244353.