AtCoder Beginner Contest 381

A - 11/22 String

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

配点 : 150 点

問題文

この問題における 11/22 文字列の定義は C 問題および E 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

|T| は奇数である。ここで、|T| は T の長さを表す。
1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
\frac{|T|+1}{2} 文字目が / である。
\frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられます。S が 11/22 文字列であるか判定してください。

制約

1 \leq N \leq 100
S は 1, 2, / からなる長さ N の文字列

入力

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

N
S

出力

S が 11/22 文字列であれば Yes を、そうでなければ No を出力せよ。

入力例 1

5
11/22

出力例 1

Yes

11/22 は問題文の 11/22 文字列の条件を満たします。

入力例 2

1
/

出力例 2

Yes

/ は問題文の 11/22 文字列の条件を満たします。

入力例 3

4
1/22

出力例 3

No

1/22 は問題文の 11/22 文字列の条件を満たしません。

入力例 4

5
22/11

出力例 4

No

Score : 150 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems C and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

|T| is odd. Here, |T| denotes the length of T.
The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
The (\frac{|T|+1}{2})-th character is /.
The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string S of length N consisting of 1, 2, and /, determine whether S is an 11/22 string.

Constraints

1 \leq N \leq 100
S is a string of length N consisting of 1, 2, and /.

Input

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

N
S

Output

If S is an 11/22 string, print Yes; otherwise, print No.

Sample Input 1

5
11/22

Sample Output 1

Yes

11/22 satisfies the conditions for an 11/22 string in the problem statement.

Sample Input 2

1
/

Sample Output 2

Yes

/ satisfies the conditions for an 11/22 string.

Sample Input 3

4
1/22

Sample Output 3

No

1/22 does not satisfy the conditions for an 11/22 string.

Sample Input 4

5
22/11

Sample Output 4

No

B - 1122 String

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

配点 : 150 点

問題文

文字列 T が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、T を 1122 文字列 と呼びます。

\lvert T \rvert は偶数である。ここで、\lvert T \rvert は T の長さを表す。
1\leq i\leq \frac{\lvert T \rvert}{2} をみたす整数 i について、T の (2i-1) 文字目と 2i 文字目は等しい。
各文字は T にちょうど 0 個または 2 個現れる。すなわち、T に含まれる文字は T にちょうど 2 回ずつ登場する。

英小文字のみからなる文字列 S が与えられるので、S が 1122 文字列であるならば Yes を、そうでないならば No を出力してください。

制約

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

入力

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

出力

S が 1122 文字列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

aabbcc

出力例 1

Yes

S=aabbcc は 1122 文字列の条件をすべてみたしているため、Yes を出力します。

入力例 2

aab

出力例 2

No

S=aab は長さが奇数であり、 1 つめの条件をみたしていないため、No を出力します。

入力例 3

zzzzzz

出力例 3

No

S=zzzzzz は z が 6 個含まれており、 3 つめの条件をみたしていないため、No を出力します。

Score : 150 points

Problem Statement

A string T is called a 1122 string if and only if it satisfies all of the following three conditions:

\lvert T \rvert is even. Here, \lvert T \rvert denotes the length of T.
For each integer i satisfying 1\leq i\leq \frac{|T|}{2}, the (2i-1)-th and 2i-th characters of T are equal.
Each character appears in T exactly zero or two times. That is, every character contained in T appears exactly twice in T.

Given a string S consisting of lowercase English letters, print Yes if S is a 1122 string, and No otherwise.

Constraints

S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

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

Output

If S is a 1122 string, print Yes; otherwise, print No.

Sample Input 1

aabbcc

Sample Output 1

Yes

S=aabbcc satisfies all the conditions for a 1122 string, so print Yes.

Sample Input 2

aab

Sample Output 2

No

S=aab has an odd length and does not satisfy the first condition, so print No.

Sample Input 3

zzzzzz

Sample Output 3

No

S=zzzzzz contains six zs and does not satisfy the third condition, so print No.

C - 11/22 Substring

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

配点 : 300 点

問題文

この問題における 11/22 文字列の定義は A 問題および E 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

|T| は奇数である。ここで、|T| は T の長さを表す。
1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
\frac{|T|+1}{2} 文字目が / である。
\frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられます。S は / を 1 個以上含みます。
11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
S は 1, 2, / からなる長さ N の文字列
S は / を 1 個以上含む

入力

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

N
S

出力

11/22 文字列であるような S の(連続な)部分文字列の長さの最大値を出力せよ。

入力例 1

8
211/2212

出力例 1

S の 2 文字目から 6 文字目からなる部分文字列は 11/22 で、これは 11/22 文字列です。S の部分文字列のうち 11/22 文字列であるものはこれが最長です。よって 5 が答えです。

入力例 2

5
22/11

出力例 2

入力例 3

22
/1211/2///2111/2222/11

出力例 3

Score : 300 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

|T| is odd. Here, |T| denotes the length of T.
The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
The (\frac{|T|+1}{2})-th character is /.
The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

You are given a string S of length N consisting of 1, 2, and /, where S contains at least one /.
Find the maximum length of a (contiguous) substring of S that is an 11/22 string.

Constraints

1 \leq N \leq 2 \times 10^5
S is a string of length N consisting of 1, 2, and /.
S contains at least one /.

Input

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

N
S

Output

Print the maximum length of a (contiguous) substring of S that is an 11/22 string.

Sample Input 1

8
211/2212

Sample Output 1

The substring from the 2-nd to 6-th character of S is 11/22, which is an 11/22 string. Among all substrings of S that are 11/22 strings, this is the longest. Therefore, the answer is 5.

Sample Input 2

5
22/11

Sample Output 2

Sample Input 3

22
/1211/2///2111/2222/11

Sample Output 3

D - 1122 Substring

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

配点 : 425 点

問題文

正整数からなる（空でも良い）数列 X=(X_1,X_2,\ldots) が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、X を 1122 数列 と呼びます。
（1122 数列の定義はF問題と共通です。）

\lvert X \rvert は偶数である。ここで、\lvert X \rvert は X の長さを表す。
1\leq i\leq \frac{\lvert X \rvert}{2} をみたす整数 i について、X_{2i-1} と X_{2i} は等しい。
各正整数は X に現れないか、ちょうど 2 回現れるかのどちらかである。すなわち、X に含まれる正整数は X にちょうど 2 回ずつ登場する。

正整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられるので、A の 連続する部分列 であって、1122 数列であるようなもののうち最長のものの長さを出力してください。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

A の連続する部分列であって、1122 数列であるようなもののうち最長のものの長さを出力せよ。

入力例 1

8
2 3 1 1 2 2 1 1

出力例 1

例えば A の 3 項目から 6 項目までの連続部分列をとると (1,1,2,2) となりますが、これは長さが 4 の 1122 数列となっています。
これより長い部分列であって、1122 数列の条件をみたすようなものは存在しないため、4 を出力します。

入力例 2

3
1 2 2

出力例 2

入力例 3

1
1

出力例 3

項数が 0 の列も 1122 数列の条件をみたしていることに注意してください。

Score : 425 points

Problem Statement

A sequence X = (X_1, X_2, \ldots) of positive integers (possibly empty) is called a 1122 sequence if and only if it satisfies all of the following three conditions: (The definition of a 1122 sequence is the same as in Problem F.)

\lvert X \rvert is even. Here, \lvert X \rvert denotes the length of X.
For each integer i satisfying 1\leq i\leq \frac{|X|}{2}, X_{2i-1} and X_{2i} are equal.
Each positive integer appears in X either not at all or exactly twice. That is, every positive integer contained in X appears exactly twice in X.

Given a sequence A = (A_1, A_2, \ldots, A_N) of length N consisting of positive integers, print the maximum length of a (contiguous) subarray of A that is a 1122 sequence.

Constraints

1\leq N \leq 2 \times 10^5
1\leq A_i \leq N
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 maximum length of a (contiguous) subarray of A that is a 1122 sequence.

Sample Input 1

8
2 3 1 1 2 2 1 1

Sample Output 1

For example, taking the subarray from the 3-rd to 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer (contiguous) subarray that satisfies the conditions for a 1122 sequence, so the answer is 4.

Sample Input 2

3
1 2 2

Sample Output 2

Sample Input 3

1
1

Sample Output 3

Note that a sequence of length 0 also satisfies the conditions for a 1122 sequence.

E - 11/22 Subsequence

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

配点 : 500 点

問題文

この問題における 11/22 文字列の定義は A 問題および C 問題と同じです。

文字列 T が以下の条件を全て満たすとき、T を 11/22 文字列 と呼びます。

|T| は奇数である。ここで、|T| は T の長さを表す。
1 文字目から \frac{|T|+1}{2} - 1 文字目までが 1 である。
\frac{|T|+1}{2} 文字目が / である。
\frac{|T|+1}{2} + 1 文字目から |T| 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられるので、Q 個のクエリを処理してください。

各クエリでは L, R が与えられます。S の L 文字目から R 文字目までからなる (連続な) 部分文字列を T としたとき、 11/22 文字列であるような T の (連続とは限らない) 部分列の長さの最大値を求めてください。そのような部分列が存在しないときは 0 を出力してください。

制約

1 \leq N \leq 10^5
1 \leq Q \leq 10^5
S は 1, 2, / からなる長さ N の文字列
1 \leq L \leq R \leq N
N, Q, L, R は整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の形式で与えられる。

L R

出力

Q 行出力せよ。i 行目には i 番目のクエリへの答えを出力せよ。

入力例 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

出力例 1

1 番目のクエリについて、S の 1 文字目から 7 文字目からなる部分文字列は 111/212 です。この文字列は 11/22 を部分列として含み、これは 11/22 文字列であるような部分列として最大です。よって答えは 5 です。
2 番目のクエリについて、S の 9 文字目から 12 文字目からなる部分文字列は 1122 です。この文字列は 11/22 文字列であるような部分列を含まないので、答えは 0 です。

Score : 500 points

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and C.

A string T is called an 11/22 string when it satisfies all of the following conditions:

|T| is odd. Here, |T| denotes the length of T.
The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
The (\frac{|T|+1}{2})-th character is /.
The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string S of length N consisting of 1, 2, and /, process Q queries.

Each query provides two integers L and R. Let T be the (contiguous) substring of S from the L-th through R-th character. Find the maximum length of a subsequence (not necessarily contiguous) of T that is an 11/22 string. If no such subsequence exists, print 0.

Constraints

1 \leq N \leq 10^5
1 \leq Q \leq 10^5
S is a string of length N consisting of 1, 2, and /.
1 \leq L \leq R \leq N
N, Q, L, and R are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{query}_i denotes the i-th query.

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

L R

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

Sample Output 1

For the first query, the substring from the 1-st to 7-th character of S is 111/212. This string contains 11/22 as a subsequence, which is the longest subsequence that is an 11/22 string. Therefore, the answer is 5.
For the second query, the substring from the 9-th to 12-th character of S is 1122. This string does not contain any subsequence that is an 11/22 string, so the answer is 0.

F - 1122 Subsequence

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

配点 : 525 点

問題文

正整数からなる（空でも良い）数列 X=(X_1,X_2,\ldots) が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、X を 1122 数列 と呼びます。
（1122 数列の定義はD問題と共通です。）

\lvert X \rvert は偶数である。ここで、\lvert X \rvert は X の長さを表す。
1\leq i\leq \frac{\lvert X \rvert}{2} をみたす整数 i について、X_{2i-1} と X_{2i} は等しい。
各正整数は X に現れないか、ちょうど 2 回現れるかのどちらかである。すなわち、X に含まれる正整数は X にちょうど 2 回ずつ登場する。

正整数からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられるので、A の （連続でなくても良い）部分列 であって、1122 数列であるようなもののうち最長のものの長さを出力してください。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

A の（連続でなくても良い）部分列であって、1122 数列であるようなもののうち最長のものの長さを出力せよ。

入力例 1

7
1 3 3 1 2 2 1

出力例 1

例えば A の部分列として、1,4,5,6 項目をとると (1,1,2,2) となりますが、これは長さが 4 の 1122 数列となっています。
これより長い部分列であって、1122 数列の条件をみたすようなものは存在しないため、4 を出力します。

入力例 2

1
20

出力例 2

Score : 525 points

Problem Statement

\lvert X \rvert is even. Here, \lvert X \rvert denotes the length of X.
For each integer i satisfying 1\leq i\leq \frac{|X|}{2}, X_{2i-1} and X_{2i} are equal.
Each positive integer appears in X either not at all or exactly twice. That is, every positive integer contained in X appears exactly twice in X.

Given a sequence A = (A_1, A_2, \ldots, A_N) of length N consisting of positive integers, print the maximum length of a subsequence (not necessarily contiguous) of A that is a 1122 sequence.

Constraints

1\leq N \leq 2 \times 10^5
1\leq A_i \leq 20
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 maximum length of a (not necessarily contiguous) subsequence of A that is a 1122 sequence.

Sample Input 1

7
1 3 3 1 2 2 1

Sample Output 1

For example, choosing the 1-st, 4-th, 5-th, and 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer subsequence that satisfies the conditions for a 1122 sequence, so the answer is 4.

Sample Input 2

1
20

Sample Output 2

G - Fibonacci Product

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

配点 : 675 点

問題文

数列 a_1, a_2, a_3, \dots の一般項 a_n を次のように定義します。

a_n = \begin{cases} x & (n=1) \\ y & (n=2) \\ a_{n-1} + a_{n-2} & (n \geq 3) \\ \end{cases}

\left(\displaystyle \prod_{i=1}^N a_i\right) \bmod{998244353} を計算してください。

T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。

制約

1 \leq T \leq 5
1 \leq N \leq 10^{18}
0 \leq x \leq 998244352
0 \leq y \leq 998244352
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N x y

出力

T 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。

入力例 1

3
5 1 1
2024 11 22
1000000000000000000 12345 6789

出力例 1

30
577322229
726998219

1 番目のテストケースについて、数列の各項は 1, 1, 2, 3, 5, 8, \dots です。よって (1 \times 1 \times 2 \times 3 \times 5) \bmod{998244353} = 30 が答えとなります。

Score : 675 points

Problem Statement

Define a sequence a_1, a_2, a_3, \dots as follows:

a_n = \begin{cases} x & (n=1) \\ y & (n=2) \\ a_{n-1} + a_{n-2} & (n \geq 3) \\ \end{cases}

Find \left( \displaystyle \prod_{i=1}^N a_i \right) \bmod{998244353}.

You are given T test cases to solve.

Constraints

1 \leq T \leq 5
1 \leq N \leq 10^{18}
0 \leq x \leq 998244352
0 \leq y \leq 998244352
All input values are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{case}_i denotes the i-th test case.

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N x y

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

3
5 1 1
2024 11 22
1000000000000000000 12345 6789

Sample Output 1

30
577322229
726998219

For the first test case, the elements of the sequence are 1, 1, 2, 3, 5, 8, \dots. Thus, the answer is (1 \times 1 \times 2 \times 3 \times 5) \bmod{998244353} = 30.