【競技プログラミング】AtCoder Beginner Contest 372_C問題

問題

既存投稿一覧ページへのリンク

一覧ページ

Before

AtCoder Beginner Contest 371_E 問題

解法手順1

ステップ1：初期状態で "ABC" の個数をカウントする

まず、文字列 $ S $ の中に "ABC" という連続部分文字列がいくつあるかを数える。
これは、長さ $ N $ の文字列 $ S $ の各位置 $ i $（ただし $ 0 \leq i \leq N-3 $）について、
$ S[i], S[i+1], S[i+2] $ がそれぞれ 'A', 'B', 'C' ならカウントを1増やす。

abc_count = 0
for i in range(N - 2):
    if S[i] == "A" and S[i+1] == "B" and S[i+2] == "C":
        abc_count += 1

---

ステップ2：クエリごとに処理を繰り返す

各クエリでは、指定された位置の文字を変更し、そのたびに "ABC" の個数を更新して出力する。

---

2-1. 変更前の "ABC" を減算

変更する位置 $ X $ の前後で "ABC" が消える可能性があるので、$ X-2 $ から $ X $ までの3か所（ただし範囲外は除く）を調べ、もし "ABC" があればカウントを1減らす。

for k in range(3):
    pos = Xi - k
    if 0 <= pos and pos + 2 < N:
        if S[pos] == "A" and S[pos+1] == "B" and S[pos+2] == "C":
            abc_count -= 1

---

2-2. 文字列を更新

指定された位置の文字を新しい文字に置き換える。

S[Xi] = Ci

---

2-3. 変更後の "ABC" を加算

再び、$ X-2 $ から $ X $ までの3か所を調べ、今度は新しく "ABC" が現れた場所があればカウントを1増やす。

for k in range(3):
    pos = Xi - k
    if 0 <= pos and pos + 2 < N:
        if S[pos] == "A" and S[pos+1] == "B" and S[pos+2] == "C":
            abc_count += 1

---

2-4. 現在の "ABC" の個数を出力

print(abc_count)

---

まとめ：全体の流れ

ACコード1

ac.py

import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

def io_func():
    # 入力の受け取り
    N, Q = map(int, input().split())
    S = list(input())
    queries = []
    for _ in range(Q):
        Xi, Ci = input().split()
        queries.append((int(Xi) - 1, Ci))
    return N, Q, S, queries

def solve(N, Q, S, queries, logger):
    # 初期状態で"ABC"が何個あるかカウント
    abc_count = 0
    for i in range(N - 2):
        if S[i] == "A" and S[i+1] == "B" and S[i+2] == "C":
            abc_count += 1
    logger.debug(f"初期状態での'ABC'の個数: {abc_count}")

    for idx, (Xi, Ci) in enumerate(queries):
        logger.debug(f"クエリ{idx+1}: 位置={Xi+1}, 変更後文字='{Ci}'")
        # 変更前、影響範囲の"ABC"を減算
        for k in range(3):
            pos = Xi - k
            if 0 <= pos and pos + 2 < N:
                if S[pos] == "A" and S[pos+1] == "B" and S[pos+2] == "C":
                    abc_count -= 1
                    logger.debug(f"変更前: S[{pos}:{pos+3}]='{S[pos]}{S[pos+1]}{S[pos+2]}' -> 'ABC'減算 (新カウント: {abc_count})")
        # 文字列更新
        old_char = S[Xi]
        S[Xi] = Ci
        logger.debug(f"S[{Xi}]を'{old_char}'から'{Ci}'に変更")
        # 変更後、影響範囲の"ABC"を加算
        for k in range(3):
            pos = Xi - k
            if 0 <= pos and pos + 2 < N:
                if S[pos] == "A" and S[pos+1] == "B" and S[pos+2] == "C":
                    abc_count += 1
                    logger.debug(f"変更後: S[{pos}:{pos+3}]='{S[pos]}{S[pos+1]}{S[pos+2]}' -> 'ABC'加算 (新カウント: {abc_count})")
        print(abc_count)

def main():
    logger = setup_logger(debug_mode=True)
    N, Q, S, queries = io_func()
    solve(N, Q, S, queries, logger)

if __name__ == "__main__":
    main()