概要

電光掲示板の文字を1つずつ変更するたびに、隣り合うマスの文字が同じである「一致ペア」の個数を効率的に求める問題です。

考察

素朴なアプローチとその問題点

更新のたびに全マスを走査して一致ペアを数え直すと、各更新に \(O(N)\) かかり、全体で \(O(NQ)\) となります。\(N\) が最大 \(10^6\)、\(Q\) が最大 \(10^5\) なので、最悪 \(10^{11}\) 回の操作となり TLE になります。

重要な気づき：局所的な変化に着目する

1文字を変更したとき、一致ペアの個数に影響を与えるのは 変更したマスとその左右の隣接マスとの関係だけ です。

具体的に、位置 \(i\) の文字を変更する場合、関係するペアは最大で2つだけです： - \((i-1, i)\) のペア（\(i > 1\) の場合） - \((i, i+1)\) のペア（\(i < N\) の場合）

例えば、文字列が AABA で位置3（0-indexed で2）を A に変えると： - 変更前：ペア \((2,3)\) は B と A で不一致、ペア \((3,4)\) は A と A で一致 - 変更後：ペア \((2,3)\) は A と A で一致（+1）、ペア \((3,4)\) は A と A で一致（変化なし）

このように、変更前の文字（old）との一致を引き、変更後の文字（new）との一致を足すだけで、カウントを \(O(1)\) で更新できます。

アルゴリズム

1. 初期化: 文字列 \(S\) を配列として持ち、隣接する文字が同じペアの数 count を \(O(N)\) で数える。
2. 各更新処理（位置 \(i\) を文字 \(c\) に変更）:
   • 現在の文字 old = S[i] と新しい文字 \(c\) が異なる場合のみ処理する。
   • 左隣 \((i-1)\) との関係を更新:
     • S[i-1] == old なら count -= 1（元々一致していたペアが崩れる可能性）
     • S[i-1] == c なら count += 1（新たに一致ペアが生まれる可能性）
   • 右隣 \((i+1)\) との関係を更新:
     • S[i+1] == old なら count -= 1
     • S[i+1] == c なら count += 1
   • S[i] = c で配列を更新する。
3. 各更新後の count を出力する。

計算量

• 時間計算量: \(O(N + Q)\)（初期カウントに \(O(N)\)、各更新に \(O(1)\)）
• 空間計算量: \(O(N)\)（文字列を配列として保持）

実装のポイント

• 0-indexed と 1-indexed の変換: 問題文では1-indexed なので、入力を受け取ったら -1 して 0-indexed に変換する。

• 変更なしの場合のスキップ: old == c の場合は一致ペア数に変化がないので、条件分岐で処理をスキップすることで無駄な計算を避ける。

• 出力の高速化: Python では print を毎回呼ぶと遅いため、結果をリストに溜めて最後に sys.stdout.write で一括出力する。同様に、入力も sys.stdin.readline を使う。

• 境界チェック: 左端（\(i = 0\)）や右端（\(i = N-1\)）では隣接マスが片方しかないため、範囲外アクセスを防ぐ条件分岐が必要。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = list(input().strip())
    
    # Count initial matching pairs
    count = 0
    for i in range(N - 1):
        if S[i] == S[i + 1]:
            count += 1
    
    out = []
    for _ in range(Q):
        line = input().split()
        idx = int(line[0]) - 1  # 0-indexed
        c = line[1]
        
        old = S[idx]
        if old != c:
            # Check left neighbor
            if idx > 0:
                if S[idx - 1] == old:
                    count -= 1
                if S[idx - 1] == c:
                    count += 1
            # Check right neighbor
            if idx < N - 1:
                if S[idx + 1] == old:
                    count -= 1
                if S[idx + 1] == c:
                    count += 1
            S[idx] = c
        
        out.append(str(count))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

この解説は claude4.6opus-thinking によって生成されました。