AtCoder Beginner Contest 122 B - ATCoderの解説を書いてみた

今回はB - ATCoderの解説でも書いてみようと思います。

こちらからアクセスできます

①考え方

Sの部分文字列の中でATCG文字列（A, T, C, Gのみを含む文字列）の最長のときの長さを出力して欲しいというわけですね。
ではどのようにすればいいでしょうか？
入力例1をもとに考えていきましょう。

入力例1

ATCODER
↓
ATCODER
 TCODER
  CODER
   ODER
    DER
     ER
      R
という感じの文字列にして探索していくことで求められないかな～と考えていきます。
(cnt = 0を用意しておきます)
それぞれの文字列に対して最初から順にA, T, C, Gの文字数を
数えていき(cnt = cnt + 1)、
それ以外の場合、
次の文字列に移ります(cnt = 0と初期化しておきます)。
あらかじめans = 0というのを用意して次の文字列に移る前に、
ans = max(ans, cnt)をとり、最長時の値を求めていきます。

これをコードにおこすとこうなります。

for i in range(len(s)):
    cnt = 0
    for j in range(i, len(s)):
        if s[j] not in a:
            break
        cnt += 1
    ans = max(ans, cnt)

ちなみに全探索を使っています。

②提出したコード

import io
import sys
import statistics
import math
import queue
import heapq

s = input()
ans = 0
a = ["A", "T", "C", "G"]
for i in range(len(s)):
    cnt = 0
    for j in range(i, len(s)):
        if s[j] not in a:
            break
        cnt += 1
    ans = max(ans, cnt)
print(ans)

③まとめ

この問題は全探索を用いる問題でしたね。ただ闇雲に探索するのではなく、徐々に探索する範囲を狭めていくというのがポイントかと思います。

④参考文献