競プロ初中級者100問

ABC122B ATCoder

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc122/tasks/abc122_b

この問題は全探索を用いて解くことができます。

方針

Sの長さが十分に小さいので、全ての部分文字列を全探索することができます。

とはいえ、線形探索であっても実装がシンプルになるため、線形探索で解きます。

コード

リストの末尾に特殊な文字（番兵と呼びます）を追加することで、処理をシンプルにしています。番兵を用いない場合、ループ終了後に改めて

1
ans = max(ans, sm)

とする必要があります。

1
2
3
4
5
6
7
8
9
10
11
S = input()
S+='*'
sm = 0
ans = 0
for s in S:
    if s in ('A','C','G','T'):
        sm += 1
    else:
        ans = max(ans, sm)
        sm = 0
print (ans)

記事情報

  • 投稿日：2020年5月10日
  • 最終更新日：2020年5月10日