AtCoder Daily Training EASY 2024/02/08 16:30start

A - wwwvvvvvv

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

v と w のみからなる文字列 S が与えられます。

S の中に、下に尖っている部分が何箇所あるかを出力してください（入出力例にある図もご参照ください）。

制約

S は v と w のみからなる文字列
S の長さは 1 以上 100 以下

入力

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

出力

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

入力例 1

vvwvw

出力例 1

vvwvw

上の画像のように、vvwvw という文字列には下に尖った部分が 7 箇所あります。

入力例 2

出力例 2

入力例 3

wwwvvvvvv

出力例 3

Score : 100 points

Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

S is a string consisting of v and w.
The length of S is between 1 and 100, inclusive.

Input

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

Output

Print the answer as an integer.

Sample Input 1

vvwvw

Sample Output 1

vvwvw

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

Sample Output 2

Sample Input 3

wwwvvvvvv

Sample Output 3

B - 484558

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

0123456789 に加えて 10,11,12,13,14,15 に対応する数字として ABCDEF を使う 16 進表記では、0 以上 255 以下の整数は 1 桁または 2 桁になります。
例えば、0 や 12 は 16 進表記では 0 や C と 1 桁になり、99 や 255 は 16 進表記では 63 や FF と 2 桁になります。

0 以上 255 以下の整数 N を、必要に応じて先頭に 0 を加えることでちょうど 2 桁の 16 進表記に変換してください。

注記

英大文字と英小文字は区別されます。特に、16 進表記の数字として ABCDEF の代わりに abcdef を使うことは出来ません。

制約

0 \leq N \leq 255
N は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

99 は 16 進表記で 63 です。

入力例 2

出力例 2

0C

12 は 16 進表記で C です。
要求されているのはちょうど 2 桁の 16 進表記に変換することなので、C の先頭に 0 を加えた 0C が答えです。

入力例 3

出力例 3

入力例 4

出力例 4

FF

Score : 100 points

Problem Statement

In the hexadecimal system, where the digits ABCDEF corresponding to 10,11,12,13,14, and 15 are used in addition to 0123456789, every integer between 0 and 255 is represented as a 1- or 2-digit numeral.
For example, 0 and 12 are represented as 1-digit hexadecimal numerals 0 and C; 99 and 255 are represented as 2-digit hexadecimals 63 and FF.

Given an integer N between 0 and 255, convert it to an exactly two-digit hexadecimal numeral, prepending leading 0s if necessary.

Notes

The judge is case-sensitive. Specifically, you cannot use abcdef as hexadecimal digits instead of ABCDEF.

Constraints

0 \leq N \leq 255
N is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

99 is represented as 63 in hexadecimal.

Sample Input 2

Sample Output 2

0C

12 is represented as C in hexadecimal.
Since we ask you to convert it to a two-digit hexadecimal numeral, the answer is 0C, where 0 is prepended to C.

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

FF

C - Longest Uncommon Prefix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。 S の x 文字目 (1 \le x \le N) は S_x です。

i=1,2,\dots,N-1 それぞれについて、以下の条件を全て満たす最大の非負整数 l を求めてください。

l+i \le N である。
全ての 1 \le k \le l を満たす整数 k について、 S_{k} \neq S_{k+i} を満たす。

なお、 l=0 は常に条件を満たすことに注意してください。

制約

N は 2 \le N \le 5000 を満たす整数
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

N-1 行にわたって出力せよ。そのうち x 行目 (1 \le x < N) には i=x とした場合の答えを整数として出力せよ。

入力例 1

6
abcbac

出力例 1

この入力では、 S= abcbac です。

i=1 のとき、 S_1 \neq S_2, S_2 \neq S_3, \dots ,S_5 \neq S_6 であるため、最大値は l=5 です。
i=2 のとき、 S_1 \neq S_3 ですが S_2 = S_4 であるため、最大値は l=1 です。
i=3 のとき、 S_1 \neq S_4, S_2 \neq S_5 ですが S_3 = S_6 であるため、最大値は l=2 です。
i=4 のとき、 S_1 = S_5 であるため、最大値は l=0 です。
i=5 のとき、 S_1 \neq S_6 であるため、最大値は l=1 です。

Score : 200 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

l+i \le N, and
for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

N is an integer such that 2 \le N \le 5000.
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print (N-1) lines. The x-th (1 \le x < N) line should contain the answer as an integer when i=x.

Sample Input 1

6
abcbac

Sample Output 1

In this input, S= abcbac.

When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
When i=4, we have S_1 = S_5, so the maximum value is l=0.
When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

D - Climbing Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 個の台が一列に並んでおり、左から i 番目の台の高さは H_i です。

高橋君は最初、左端の台の上に立っています。

高橋君は高い所が好きなので、次のルールで可能な限り移動を繰り返します。

いま立っているのが右端の台ではなく、かつ、右隣にある台の高さが自分がいま立っている台より高いとき、右隣の台に移動する

最終的に高橋君が立っている台の高さを求めてください。

制約

2 \leq N \leq 10^5
1 \leq H_i \leq 10^9
入力に含まれる値は全て整数である

入力

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

N
H_1 \ldots H_N

出力

答えを出力せよ。

入力例 1

5
1 5 10 4 2

出力例 1

最初、高橋君は左端にある高さ 1 の台に立っています。右隣の台の高さは 5 であり、いま立っている台より高いので、右隣の台に移動します。

移動後、高橋君は左から 2 番目にある高さ 5 の台に立っています。右隣の台の高さは 10 であり、いま立っている台より高いので、右隣の台に移動します。

移動後、高橋君は左から 3 番目にある高さ 10 の台に立っています。右隣の台の高さは 4 であり、いま立っている台より低いので、高橋君は移動をやめます。

よって、最終的に高橋君が立っている台の高さは 10 です。

入力例 2

3
100 1000 100000

出力例 2

入力例 3

4
27 1828 1828 9242

出力例 3

Score : 200 points

Problem Statement

There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.

Takahashi is initially standing on the leftmost platform.

Since he likes heights, he will repeat the following move as long as possible.

If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.

Find the height of the final platform he will stand on.

Constraints

2 \leq N \leq 10^5
1 \leq H_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
H_1 \ldots H_N

Output

Print the answer.

Sample Input 1

5
1 5 10 4 2

Sample Output 1

Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.

He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.

He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.

Thus, the height of the final platform Takahashi will stand on is 10.

Sample Input 2

3
100 1000 100000

Sample Output 2

Sample Input 3

4
27 1828 1828 9242

Sample Output 3

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