ABC372 C問題の解説（Python）

はじめに

この記事では、ABC372のC問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC372　C – Count ABC Again

問題

問題

長さNの文字列SとQ個のクエリが与えられるので、Q個のクエリを順番に処理する問題です。

\(i\) 番目のクエリは以下の通りです。

• Sの \(X_i\)​ 番目の文字を \(C_i\)​ に置き換える。その後、Sに文字列”ABC”が部分文字列として何箇所含まれるかを出力する。

制約

• \(3 \leqq N \leqq 2×10^5 \)
• \(1 \leqq Q \leqq 2×10^5 \)
• \(1 \leqq X_i \leqq N \)

思考の筋道

NやQは最大で 2×10^5のため、各クエリごとに”ABC”の個数を数えるのでは、TLE（時間制限超過）となります。

各クエリで文字列には1箇所しか変更が入りません。そのため毎回、文字列全体を調べるのではなく、変更された箇所の周辺のみを調べることで、時間削減ができます。

“ABC”は3文字のため、変更があった箇所の前後2文字まで調べておけば十分です。

なお、置き換える文字がすみっこの方にある際、前後2文字を取る際に文字列の範囲をはみ出さないようにしましょう。下記のコードではmaxやminを使い、はみ出さないようにしています。

毎回全体を調べるのではなく、変更で影響があった箇所のみ調べる問題はよくありますので、テクニックとして知っておくとよいでしょう。

コード

N, Q = map(int, input().split())
S = list(input())
count = 0

for i in range(N - 2):
    if S[i:i + 3] == ["A", "B", "C"]:
        count += 1

for _ in range(Q):
    X, C = input().split()
    index = int(X) - 1

    for i in range(max(0, index - 2), min(N - 2, index + 1)):
        if S[i:i + 3] == ["A", "B", "C"]:
            count -= 1

    S[index] = C

    for i in range(max(0, index - 2), min(N - 2, index + 1)):
        if S[i:i + 3] == ["A", "B", "C"]:
            count += 1

    print(count)

以上、ABC372のC問題の解説でした！

では、またね。

リンク