AtCoder Beginner Contest 122

A - Double Helix

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

AtCoder 星には四種類の塩基 A, C, G, T が存在し、A と T、C と G がそれぞれ対になります。

文字 b が入力されます。これは A, C, G, T のいずれかです。塩基 b と対になる塩基を表す文字を出力するプログラムを書いてください。

制約

b は文字 A, C, G, T のいずれかである。

入力

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

出力

塩基 b と対になる塩基を表す文字を出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

Score : 100 points

Problem Statement

On the Planet AtCoder, there are four types of bases: A, C, G and T. A bonds with T, and C bonds with G.

You are given a letter b as input, which is A, C, G or T. Write a program that prints the letter representing the base that bonds with the base b.

Constraints

b is one of the letters A, C, G and T.

Input

Input is given from Standard Input in the following format:

Output

Print the letter representing the base that bonds with the base b.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

B - ATCoder

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

英大文字からなる文字列 S が与えられます。S の部分文字列 (注記を参照) であるような最も長い ACGT 文字列 の長さを求めてください。

ここで、ACGT 文字列とは A, C, G, T 以外の文字を含まない文字列です。

注記

文字列 T の部分文字列とは、T の先頭と末尾から 0 文字以上を取り去って得られる文字列です。

例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, (空文字列) が含まれ、AC は含まれません。

制約

S は長さ 1 以上 10 以下の文字列である。
S の各文字は英大文字である。

入力

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

出力

S の部分文字列であるような最も長い ACGT 文字列の長さを出力せよ。

入力例 1

ATCODER

出力例 1

ATCODER の部分文字列であるような ACGT 文字列のうち、最も長いものは ATC です。

入力例 2

HATAGAYA

出力例 2

HATAGAYA の部分文字列であるような ACGT 文字列のうち、最も長いものは ATAGA です。

入力例 3

SHINJUKU

出力例 3

SHINJUKU の部分文字列であるような ACGT 文字列のうち、最も長いものは (空文字列) です。

Score : 200 points

Problem Statement

You are given a string S consisting of uppercase English letters. Find the length of the longest ACGT string that is a substring (see Notes) of S.

Here, a ACGT string is a string that contains no characters other than A, C, G and T.

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and (the empty string), but not AC.

Constraints

S is a string of length between 1 and 10 (inclusive).
Each character in S is an uppercase English letter.

Input

Input is given from Standard Input in the following format:

Output

Print the length of the longest ACGT string that is a substring of S.

Sample Input 1

ATCODER

Sample Output 1

Among the ACGT strings that are substrings of ATCODER, the longest one is ATC.

Sample Input 2

HATAGAYA

Sample Output 2

Among the ACGT strings that are substrings of HATAGAYA, the longest one is ATAGA.

Sample Input 3

SHINJUKU

Sample Output 3

Among the ACGT strings that are substrings of SHINJUKU, the longest one is (the empty string).

C - GeT AC

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

A, C, G, T からなる長さ N の文字列 S が与えられます。以下の Q 個の問いに答えてください。

問 i (1 \leq i \leq Q): 整数 l_i, r_i (1 \leq l_i < r_i \leq N) が与えられる。S の先頭から l_i 文字目から r_i 文字目までの (両端含む) 部分文字列を考える。この文字列に AC は部分文字列として何回現れるか。

注記

文字列 T の部分文字列とは、T の先頭と末尾から 0 文字以上を取り去って得られる文字列です。

例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, (空文字列) が含まれ、AC は含まれません。

制約

2 \leq N \leq 10^5
1 \leq Q \leq 10^5
S は長さ N の文字列である。
S の各文字は A, C, G, T のいずれかである。
1 \leq l_i < r_i \leq N

入力

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

N Q
S
l_1 r_1
:
l_Q r_Q

出力

Q 行出力せよ。i 行目に問 i への答えを出力すること。

入力例 1

8 3
ACACTACG
3 7
2 3
1 8

出力例 1

2
0
3

問 1: S の先頭から 3 文字目から 7 文字目までの部分文字列は ACTAC です。この文字列に AC は部分文字列として 2 回現れます。
問 2: S の先頭から 2 文字目から 3 文字目までの部分文字列は CA です。この文字列に AC は部分文字列として 0 回現れます。
問 3: S の先頭から 1 文字目から 8 文字目までの部分文字列は ACACTACG です。この文字列に AC は部分文字列として 3 回現れます。

Score : 300 points

Problem Statement

You are given a string S of length N consisting of A, C, G and T. Answer the following Q queries:

Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does AC occurs as a substring?

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and (the empty string), but not AC.

Constraints

2 \leq N \leq 10^5
1 \leq Q \leq 10^5
S is a string of length N.
Each character in S is A, C, G or T.
1 \leq l_i < r_i \leq N

Input

Input is given from Standard Input in the following format:

N Q
S
l_1 r_1
:
l_Q r_Q

Output

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

Sample Input 1

8 3
ACACTACG
3 7
2 3
1 8

Sample Output 1

2
0
3

Query 1: the substring of S starting at index 3 and ending at index 7 is ACTAC. In this string, AC occurs twice as a substring.
Query 2: the substring of S starting at index 2 and ending at index 3 is CA. In this string, AC occurs zero times as a substring.
Query 3: the substring of S starting at index 1 and ending at index 8 is ACACTACG. In this string, AC occurs three times as a substring.

D - We Like AGC

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 N が与えられます。次の条件を満たす長さ N の文字列の数を 10^9+7 で割った余りを求めてください。

A, C, G, T 以外の文字を含まない。
AGC を部分文字列として含まない。
隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。

注記

文字列 T の部分文字列とは、T の先頭と末尾から 0 文字以上を取り去って得られる文字列です。

例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, (空文字列) が含まれ、AC は含まれません。

制約

3 \leq N \leq 100

入力

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

出力

条件を満たす文字列の数を 10^9+7 で割った余りを出力せよ。

入力例 1

出力例 1

A, C, G, T 以外の文字を含まない長さ 3 の文字列は 4^3 = 64 通り存在し、そのうち AGC, ACG, GAC のみが条件に違反するため、答えは 64 - 3 = 61 通りです。

入力例 2

出力例 2

入力例 3

出力例 3

388130742

文字列の数を 10^9+7 で割った余りを出力することをお忘れなく。

Score : 400 points

Problem Statement

You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

The string does not contain characters other than A, C, G and T.
The string does not contain AGC as a substring.
The condition above cannot be violated by swapping two adjacent characters once.

Notes

A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.

For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and (the empty string), but not AC.

Constraints

3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:

Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Sample Input 1

Sample Output 1

There are 4^3 = 64 strings of length 3 that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is 64 - 3 = 61.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

388130742

Be sure to print the number of strings modulo 10^9+7.