Official

B - 電光掲示板の更新 / Updating the Electronic Message Board Editorial by admin

gemini-3-flash-thinking

概要

\(N\) 個の文字が並んだ掲示板に対し、1文字を書き換えるクエリが \(Q\) 回与えられます。各更新ごとに、隣り合う文字が等しい箇所（一致ペア）がいくつあるかを効率的に求める問題です。

考察

最も単純な方法は、各クエリのたびに掲示板全体を走査して一致ペアを数え直すことです。しかし、この方法では1回のクエリに \(O(N)\) の時間がかかり、全体で \(O(NQ)\) となります。制約は \(N \le 10^6, Q \le 10^5\) であるため、最悪 \(10^{11}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

ここで、「1文字を書き換えたとき、一致ペアの総数はどう変化するか」に注目します。 位置 \(i\) の文字 \(S_i\) を書き換えたとき、一致ペアの判定に影響が出るのは以下の2箇所だけです。 - 左隣とのペア：\((S_{i-1}, S_i)\) - 右隣とのペア：\((S_i, S_{i+1})\)

これら以外の箇所のペア（例：\(S_{i-2}\) と \(S_{i-1}\) など）は、文字が書き換わっていないため、一致しているかどうかの状態は変わりません。 したがって、各クエリでは「書き換え前の隣接状態」と「書き換え後の隣接状態」の差分だけを計算すれば、全体の個数を高速に更新できます。

アルゴリズム

  1. 初期状態の計算: 最初に文字列 \(S\) を一度だけ走査し、現在の一致ペアの総数 current_count を計算します。
  2. クエリの処理: 各更新クエリ \((i, c)\) に対して以下の操作を行います。
    • 更新前の文字 \(S_i\) と、その両隣 (\(S_{i-1}, S_{i+1}\)) を比較します。もし一致していれば、current_count を 1 減らします。
    • 位置 \(i\) の文字を \(c\) に書き換えます。
    • 更新後の文字 \(S_i\) と、その両隣 (\(S_{i-1}, S_{i+1}\)) を比較します。もし一致していれば、current_count を 1 増やします。
    • ただし、掲示板の端（\(i=1\) や \(i=N\)）の場合は、隣が存在しない側の判定はスキップします。
  3. 結果の出力: 各更新後の current_count を出力します。

計算量

  • 時間計算量: \(O(N + Q)\)
    • 初期のカウント計算に \(O(N)\)、各クエリの処理（定数回の比較）に \(O(1)\) かかるため、全体で \(O(N + Q)\) となります。
  • 空間計算量: \(O(N)\)
    • 文字列を保持するためのリストに \(O(N)\) のメモリを使用します。

実装のポイント

  • 文字列の扱い: Pythonの文字列型（str）は中身を直接書き換えられない（イミュータブル）ため、文字のリスト（list）に変換して保持することで、特定のインデックスの要素を \(O(1)\) で更新できるようにします。

  • インデックスの調整: 問題文は 1-indexed（1から始まる）ですが、プログラム内では 0-indexed（0から始まる）として扱う必要があるため、入力を受け取る際に -1 するなどの調整が必要です。

  • 入出力の高速化: \(N\) や \(Q\) が大きいため、input() ではなく sys.stdin.read() を使って一括で読み込んだり、結果をリストに貯めて最後に join して出力したりすることで、実行時間を短縮できます。”`markdown

    概要

    \(N\) 個の文字が並んだ掲示板に対し、1文字を書き換えるクエリが \(Q\) 回与えられます。各更新ごとに、隣り合う文字が等しい箇所（一致ペア）がいくつあるかを効率的に求める問題です。

考察

最も単純な方法は、各クエリのたびに掲示板全体を走査して一致ペアを数え直すことです。しかし、この方法では1回のクエリに \(O(N)\) の時間がかかり、全体で \(O(NQ)\) となります。制約は \(N \le 10^6, Q \le 10^5\) であるため、最悪 \(10^{11}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

ここで、「1文字を書き換えたとき、一致ペアの総数はどう変化するか」に注目します。 位置 \(i\) の文字 \(S_i\) を書き換えたとき、一致ペアの判定に影響が出るのは以下の2箇所だけです。 - 左隣とのペア：\((S_{i-1}, S_i)\) - 右隣とのペア：\((S_i, S_{i+1})\)

これら以外の箇所のペア（例：\(S_{i-2}\) と \(S_{i-1}\) など）は、文字が書き換わっていないため、一致しているかどうかの状態は変わりません。 したがって、各クエリでは「書き換え前の隣接状態」と「書き換え後の隣接状態」の差分だけを計算すれば、全体の個数を高速に更新できます。

アルゴリズム

  1. 初期状態の計算: 最初に文字列 \(S\) を一度だけ走査し、現在の一致ペアの総数 current_count を計算します。
  2. クエリの処理: 各更新クエリ \((i, c)\) に対して以下の操作を行います。
    • 更新前の文字 \(S_i\) と、その両隣 (\(S_{i-1}, S_{i+1}\)) を比較します。もし一致していれば、current_count を 1 減らします。
    • 位置 \(i\) の文字を \(c\) に書き換えます。
    • 更新後の文字 \(S_i\) と、その両隣 (\(S_{i-1}, S_{i+1}\)) を比較します。もし一致していれば、current_count を 1 増やします。
    • ただし、掲示板の端（\(i=1\) や \(i=N\)）の場合は、隣が存在しない側の判定はスキップします。
  3. 結果の出力: 各更新後の current_count を出力します。

計算量

  • 時間計算量: \(O(N + Q)\)
    • 初期のカウント計算に \(O(N)\)、各クエリの処理（定数回の比較）に \(O(1)\) かかるため、全体で \(O(N + Q)\) となります。
  • 空間計算量: \(O(N)\)
    • 文字列を保持するためのリストに \(O(N)\) のメモリを使用します。

実装のポイント

  • 文字列の扱い: Pythonの文字列型（str）は中身を直接書き換えられない（イミュータブル）ため、文字のリスト（list）に変換して保持することで、特定のインデックスの要素を \(O(1)\) で更新できるようにします。

  • インデックスの調整: 問題文は 1-indexed（1から始まる）ですが、プログラム内では 0-indexed（0から始まる）として扱う必要があるため、入力を受け取る際に -1 するなどの調整が必要です。

  • 入出力の高速化: \(N\) や \(Q\) が大きいため、input() ではなく sys.stdin.read() を使って一括で読み込んだり、結果をリストに貯めて最後に join して出力したりすることで、実行時間を短縮できます。

    ソースコード

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白文字（スペースや改行）で分割してトークンのリストを作成します。
    # N=10^6, Q=10^5 程度の規模であれば、この方法がPythonにおいて高速な入力読み込み手法の一つです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初のトークンはマスの個数 N、次は更新回数 Q
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 3番目のトークンは初期状態の文字列 S です。
    # Pythonの文字列はイミュータブル（変更不可）なため、文字の書き換えができるようにリストに変換します。
    S = list(input_data[2])
    
    # 初期状態における「一致ペア」の個数を計算します。
    # 一致ペアとは、隣り合う2つのマスが同じ文字である組 (S[i], S[i+1]) のことです。
    current_count = 0
    for i in range(N - 1):
        if S[i] == S[i+1]:
            current_count += 1
            
    results = []
    
    # Q 回の更新クエリを順番に処理します。
    # 各クエリは (更新位置 i_k, 変更後の文字 c_k) の2つのトークンからなります。
    # クエリの内容は input_data[3] 以降に格納されています。
    for k in range(Q):
        # 位置 i_k は 1-indexed（1から始まる）なので、0-indexed（0から始まる）に変換します。
        idx = int(input_data[3 + 2*k]) - 1
        new_char = input_data[4 + 2*k]
        old_char = S[idx]
        
        # 変更後の文字が現在の文字と異なる場合のみ、一致ペアの個数に影響が出る可能性があります。
        if old_char != new_char:
            # 1. 左隣のマス (idx-1) とのペアを確認
            if idx > 0:
                # 変更前が一致していたなら、カウントを 1 減らす
                if S[idx-1] == old_char:
                    current_count -= 1
                # 変更後に一致するようになるなら、カウントを 1 増やす
                elif S[idx-1] == new_char:
                    current_count += 1
            
            # 2. 右隣のマス (idx+1) とのペアを確認
            if idx < N - 1:
                # 変更前が一致していたなら、カウントを 1 減らす
                if S[idx+1] == old_char:
                    current_count -= 1
                # 変更後に一致するようになるなら、カウントを 1 増やす
                elif S[idx+1] == new_char:
                    current_count += 1
            
            # マスの文字を実際に更新します。
            S[idx] = new_char
            
        # 各更新後のカウントを結果リストに追加します（出力高速化のため文字列として保存）。
        results.append(str(current_count))
        
    # 全てのクエリの結果を改行で連結し、一括で出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。

posted:
last update: