C - chess960

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

配点 : 200 点

問題文

高橋君は chess960 と呼ばれるゲームで遊んでいます。 高橋君はランダムに決めた初期配置が chess960 の条件を満たすか確認するプログラムを書くことにしました。

長さ 8 の文字列 S が与えられます。S には K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれます。 S が以下の条件を全て満たしているか判定してください。

  • S において左から x,y\ (x < y) 文字目が B であるとする。このとき x と y の偶奇が異なる。

  • K は 2 つの R の間にある。より形式的には、S において左から x,y\ (x < y) 文字目が R であり、 z 文字目が K であるとする。このとき、 x< z < y が成り立つ。

制約

  • S は 長さ 8 の文字列であり、K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれる。

入力

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

S

出力

S が条件を満たす場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

RNBQKBNR

出力例 1

Yes

B は左から 3 番目、6 番目にあり、3 と 6 は偶奇が異なります。 また、K は 2 つの R の間にあります。よって条件を満たします。

入力例 2

KRRBBNNQ

出力例 2

No

K は 2 つの R の間にありません。

入力例 3

BRKRBQNN

出力例 3

No

Score : 200 points

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

  • Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

  • K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

  • S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Input

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

S

Output

Print Yes if S satisfies the conditions; print No otherwise.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No
D - Cat

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

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

  • N は 1 以上 1000 以下の整数
  • S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。

入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。

入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

  • N is an integer between 1 and 1000, inclusive.
  • 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 the answer.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal
E - Merge the balls

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

配点 : 250 点

問題文

空の列と、N 個のボールがあります。i 個目 (1\leq i\leq N) のボールの大きさは 2^{A_i} です。

これから N 回の操作を行います。
i 回目の操作では、i 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。

  1. 列にあるボールが 1 つ以下ならば操作を終了する。
  2. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 異なる ならば操作を終了する。
  3. 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 等しい ならば、2 つのボールを取り除き、「取り除かれた 2 つのボールの大きさの和」の大きさのボール 1 つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。

N 回の操作の後で、列にあるボールの数を求めてください。

制約

  • 1\leq N \leq 2\times 10^5
  • 0\leq A_i\leq 10^9
  • 入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

N 回の操作の後で、列にあるボールの数を出力せよ。

入力例 1

7
2 1 1 3 5 3 3

出力例 1

3

操作は次のように行われます。

  • 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^2 です。
  • 2 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^2, 2^1 です。
  • 3 回目の操作の後、列にあるボールは 1 つで、大きさは 2^3 です。これは次のようにして得ることができます。
    • 3 回目の操作において 3 個目のボールを付け加えたとき、列にあるボールの大きさは順に 2^2,2^1,2^1 となります。
    • 右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^1+2^1=2^2 のボールが追加されます。このとき、列にあるボールの大きさは 2^2, 2^2 となります。
    • さらに、再び右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^2+2^2=2^3 のボールが追加され、列にあるボールの大きさは 2^3 となります。
  • 4 回目の操作の後、列にあるボールは 1 つで、大きさは 2^4 です。
  • 5 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^4, 2^5 です。
  • 6 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^3 です。
  • 7 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^4 です。

よって、最後に列にあるボールの数である 3 を出力します。

入力例 2

5
0 0 0 1 2

出力例 2

4

操作は次のように行われます。

  • 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^0 です。
  • 2 回目の操作の後、列にあるボールは 1 つで、大きさは 2^1 です。
  • 3 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^1, 2^0 です。
  • 4 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^1, 2^0, 2^1 です。
  • 5 回目の操作の後、列にあるボールは 4 つで、大きさは順に 2^1, 2^0, 2^1, 2^2 です。

よって、最後に列にあるボールの数である 4 を出力します。

Score: 250 points

Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

  1. If the sequence has one or fewer balls, end the operation.
  2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
  3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the number of balls in the sequence after the N operations.

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

  • After the first operation, the sequence has one ball, of size 2^2.
  • After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
  • After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
    • When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
    • The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
    • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
  • After the fourth operation, the sequence has one ball, of size 2^4.
  • After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
  • After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
  • After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

  • After the first operation, the sequence has one ball, of size 2^0.
  • After the second operation, the sequence has one ball, of size 2^1.
  • After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
  • After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
  • After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.
F - Count xxx

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

配点 : 300 点

問題文

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

S の空でない部分文字列であって、1 種類の文字のみからなるものの数を求めてください。 ただし、文字列として等しい部分文字列同士は、取り出し方が異なっても区別しません。

なお、S の空でない部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のうち、長さが 1 以上であるもののことをいいます。 例えば、ab や abc は abc の空でない部分文字列ですが、ac や空文字列は abc の空でない部分文字列ではありません。

制約

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

入力

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

N
S

出力

S の空でない部分文字列であって、1 種類の文字のみからなるものの数を出力せよ。

入力例 1

6
aaabaa

出力例 1

4

S の空でない部分文字列であって、1 種類の文字のみからなるものは a, aa, aaa, b の 4 つです。 S から a や aa を取り出す方法は 1 通りではありませんが、それぞれ 1 回ずつしか数えないことに注意してください。

入力例 2

1
x

出力例 2

1

入力例 3

12
ssskkyskkkky

出力例 3

8

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the number of non-empty substrings of S that are repetitions of one character. Here, two substrings that are equal as strings are not distinguished even if they are obtained differently.

A non-empty substring of S is a string of length at least one obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, ab and abc are non-empty substrings of abc, while ac and the empty string are not.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 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 the number of non-empty substrings of S that are repetitions of one character.

Sample Input 1

6
aaabaa

Sample Output 1

4

The non-empty substrings of S that are repetitions of one character are a, aa, aaa, and b; there are four of them. Note that there are multiple ways to obtain a or aa from S, but each should only be counted once.

Sample Input 2

1
x

Sample Output 2

1

Sample Input 3

12
ssskkyskkkky

Sample Output 3

8
G - Three Days Ago

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

配点 : 400 点

問題文

20230322 は並べ替えると 02320232 となり、これは 0232 を 2 度繰り返しています。
このように、数字のみからなる文字列であって、適切に文字を並び替える (そのままでもよい) ことによって同じ列を 2 度繰り返すようにできるものを 嬉しい列 と呼びます。
数字のみからなる文字列 S が与えられるので、以下の条件を全て満たす整数の組 (l,r) はいくつあるか求めてください。

  • 1 \le l \le r \le |S| ( |S| は S の長さ)
  • S の l 文字目から r 文字目までの (連続する) 部分文字列は嬉しい列である。

制約

  • S は数字のみからなる長さ 1 以上 5 \times 10^5 以下の文字列

入力

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

S

出力

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

入力例 1

20230322

出力例 1

4

S= 20230322 です。
条件を満たす整数組 (l,r) は (1,6),(1,8),(2,7),(7,8) の 4 つです。

入力例 2

0112223333444445555556666666777777778888888889999999999

出力例 2

185

S の先頭が 0 である場合もあります。

入力例 3

3141592653589793238462643383279502884197169399375105820974944

出力例 3

9

Score : 400 points

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.

  • 1 \le l \le r \le |S|. (|S| is the length of S.)
  • The (contiguous) substring formed of the l-th through r-th characters of S is happy.

Constraints

  • S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.

Input

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

S

Output

Print an integer representing the answer.

Sample Input 1

20230322

Sample Output 1

4

We have S= 20230322.

Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185

S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9