−目次

AtCoder Beginner Contest 122 A～D問題メモ
- A - Double Helix
  - 問題
  - 解法
- B - ATCoder
  - 問題
  - 解法
- C - GeT AC
  - 問題
  - 解法
- D - We Like AGC
  - 問題
  - 解法

AtCoder Beginner Contest 122 A～D問題メモ

AtCoder Beginner Contest 122

AtCoder Beginner Contest 122 解説放送 - YouTube

謎の核酸塩基回、そして部分文字列回。

A - Double Helix

問題

塩基を表す文字 'A','C','G','T' のどれか1文字が与えられるので、対になる塩基を出力せよ
アデニンはチミンと、シトシンはグアニンと対になる

解法

こういうのがパッと出るとどう書いたらいいか迷った挙げ句、何故か記述量の多い方法を選んじゃう。

        
          辞書型
          
              print({'A': 'T', 'T': 'A', 'C': 'G', 'G': 'C'}[input()])

こちらの方がスマートか。

        
          文字列index型
          
              print('ATCG'['TAGC'.index(input())])

簡潔に書けるかと思ったら文字と文字コードの変換が発生してあまり簡潔にならなかった。str.maketrans()

        
          str.maketrans
          
              print(chr(str.maketrans('ATCG', 'TAGC')[ord(input())]))

B - ATCoder

問題

文字列 $S$ が与えられる
$S$ の部分文字列で、'A','C','G','T' のみからなるもので、最長のものの長さを求めよ
$1 \le |S| \le 10$

$S$ の部分文字列とは、 $S$ から連続する部分を切り出した文字列である
飛び飛びで拾ってきた文字列は含まない（'ATCODER' から 'AC' などは含まない）

解法

左端と右端を全探索。

        
              s = input()
ans = 0
for l in range(len(s)):
    for r in range(l, len(s)):
        t = s[l:r + 1]
        if all(c in 'ACGT' for c in t):
            ans = max(ans, len(t))
print(ans)

もしくは、先頭から1文字ずつ「今までで'A','C','G','T'が連続している個数カウント」を持ちながら見ていく。

ACGTのどれかだったらカウントを1増やし、どれでもなかったら0にリセットする。途中経過を含めたカウントの最大値が答え。

        
              s = input()
ans = 0
tmp = 0
for c in s:
    if c in 'ACGT':
        tmp += 1
        ans = max(ans, tmp)
    else:
        tmp = 0
print(ans)

C - GeT AC

問題

'A','C','G','T' のみからなる文字列 $S$ が与えられる
問いが $Q$ 個与えられるので、全てに答えよ
$i$ 番目の問い:
- $l_i,r_i$ が与えられる
- $S$ の $l_i～r_i$ 文字目（両端含む）の部分文字列に、'AC' は何回現れるか？
$1 \le |S| \le 10^5$
$1 \le Q \le 10^5$

解法

クエリが一杯あるので、毎回、文字列を切り出してカウントしては間に合わない。

以下を事前計算する。

$calc[i]$ : 先頭から $i$ 文字目までの部分文字列に、'AC' が現れる個数

S      AC_A_CA__ACACC__ ...
calc   0111111111223333 ...

'C' の時に1増やすようにする。

こうすると、 $l～r$ 文字目を見たとき、 $calc[r]-calc[l]$ で、その間の個数が求められる。

i      01234567890123456
S       AC_A_CA__ACACC__ ...
calc   00111111111223333 ...

l=2, r=14
S[l:r]   C_A_CA__ACACC
calc     1           3   → 3 - 1 = 2 個含まれる

元の文字列 $S$ では 'AC' の一部だった 'C' でも、そこを左端に切り出された場合は数えないことに注意。

        
              from itertools import accumulate
 
n, q = list(map(int, input().split()))
s = input()
 
calc = [0] * n
prev = None
for i, c in enumerate(s):
    if prev == 'A' and c == 'C':
        calc[i] = 1
    prev = c
calc = [0] + list(accumulate(calc))
 
ans = []
for _ in range(q):
    l, r = list(map(int, input().split()))
    ans.append(calc[r] - calc[l])
print('\n'.join(map(str, ans)))

D - We Like AGC

問題

整数 $N$ が与えられる
次の条件を満たす長さ $N$ の文字列の数を、 $10^9+7$ で割った余りを求めよ
$3 \le N \le 100$

条件
- 'A','C','G','T' のみからなる
- 'AGC' を部分文字列として含まない
- 隣接する2文字をどこか1箇所だけ入れ替えても、'AGC' を部分文字列として含むような文字列にすることはできない

解法

以下のDPで解く。

'A'=0, 'C'=1, 'G'=2, 'T'=3 と対応づける
$dp[h][i][j][k]=$ 末尾から3文字目が $i$ 、2文字目が $j$ 、1文字目が $k$ であるような長さ $h$ の文字列の個数

初期状態を考える。最初から3文字目までは作成した状態（ $h=3$ ）とする。

以下の組み合わせは禁止されているので0通り、他は1通りとなる。

i  j  k
A  G  C    ←そのままアウト
A  C  G    ←jとkの入れ替えでアウト
G  A  C    ←iとjの入れ替えでアウト

遷移を考える。

'AGC' を含まないなどの制約が無ければ、 $l$ を新規に末尾に付け加える文字として、各 $i,j,k,l$ （それぞれ0～3）につき、以下のように更新できる。

$dp[h+1][j][k][l]+=dp[h][i][j][k]$

さて、ここでアウトになるようなパターンを探して、それを更新から省く。

i  j  k  l
   A  G  C    ←そのままアウト
   A  C  G    ←kとlの入れ替えでアウト
   G  A  C    ←jとkの入れ替えでアウト
A     G  C    ←iとjの入れ替えでアウト
A  G     C    ←kとlの入れ替えでアウト

空白の部分は任意の文字が当てはまる。 $(i,j,k,l)$ がこれらの条件を満たす場合の遷移は行わないようにする。

$h=N$ まで埋めたら、 $dp[N]$ の数字を全て合計した値が答え。

実装の上では、 $h$ は1つ前の情報しか必要で無いので、ループ時に直前の状態を引き継ぐようにすると省略できる。

        
          
          
              
              MOD = 10 ** 9 + 7
n = int(input())
dp = [[[1] * 4 for _ in [0] * 4] for _ in [0] * 4]
dp[0][2][1] = 0
dp[0][1][2] = 0
dp[2][0][1] = 0
for _ in range(n - 3):
    ndp = [[[0] * 4 for _ in [0] * 4] for _ in [0] * 4]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (i, k, l) == (0, 2, 1) or (i, j, l) == (0, 2, 1):
                        pass
                    else:
                        ndp[j][k][l] += dp[i][j][k]
    dp = ndp
    dp[0][2][1] = 0
    dp[0][1][2] = 0
    dp[2][0][1] = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[j][k][l] %= MOD
print(sum(z for x in dp for y in x for z in y) % MOD)

            

        
      