概要

\(N\) 個の文字列に対して、特定の文字を別の文字に置き換える操作を \(Q\) 回行います。すべての操作が終わった後の最終的な文字列を出力する問題です。

考察

もっとも単純な方法は、「各操作ごとにすべての文字列をスキャンして文字を置換する」というものです。しかし、文字列の長さの合計を \(L = \sum |S_i|\) とすると、この方法の計算量は \(O(Q \times L)\) となります。本問題では \(Q = 10^5, L = 10^6\) であるため、最悪 \(10^{11}\) 回程度の計算が必要になり、制限時間内に終わりません。

ここで、「文字の種類は英小文字の 26 種類しかない」という点に注目します。文字列そのものを何度も書き換えるのではなく、「最終的にどの文字がどの文字に変わるか」という対応関係（マッピング）だけを効率よく計算することを考えます。

本解法では、操作を後ろ（最後）から逆順に処理することで、各文字の「最終的な行き先」を決定しています。 例えば、ある時点で「文字 a を b に置換する」という操作があるとき、その時点での文字 a は「その後のすべての操作を経た結果、最終的に b が行き着く先の文字」に変化すると考えることができます。

アルゴリズム

1. マッピングの初期化: 長さ 26 の配列 mapping を用意し、各文字が自分自身を指すように初期化します（a は a、b は b …）。
2. 操作を逆順に処理: \(Q\) 番目から \(1\) 番目までの操作 \((a_j, b_j)\) を順に見ていきます。
   • mapping[a_j] = mapping[b_j] と更新します。
   • これにより、「この時点での文字 \(a_j\) は、最終的に \(b_j\) が辿り着く文字と同じになる」という関係が記録されます。
3. 文字列の一括変換: すべての操作を処理し終えると、各文字（a〜z）が最終的にどの文字に変換されるかの対応表が完成します。 Python の str.translate メソッド（および str.maketrans）を使用すると、この対応表に基づいて文字列全体の置換を高速に行うことができます。

計算量

• 時間計算量: \(O(Q + \sum |S_i|)\)
  • 操作の逆順処理に \(O(Q)\)、最終的な文字列の変換に \(O(\sum |S_i|)\) かかります。文字種を \(C=26\) とすると、より正確には \(O(Q + \sum |S_i| + C)\) です。
• 空間計算量: \(O(\sum |S_i|)\)
  • 文字列を保持するためのメモリが必要です。

実装のポイント

• 逆順処理のメリット: 前から順に処理する場合、各操作ごとに 26 文字すべての状態を更新する必要がありますが、後ろから処理すると各操作につき 1 箇所の書き換えで済むため、実装がシンプルかつ効率的になります。

• 高速な入出力: \(N, Q\) や文字列の合計長が大きいため、sys.stdin.read().split() で一気に入力を読み込んだり、sys.stdout.write を使ってまとめて出力したりすることで、Python での実行時間を短縮しています。

• str.translate: Python の標準機能である str.translate は内部が C 言語で実装されているため、ループで 1 文字ずつ置換するよりも遥かに高速です。

  ソースコード

import sys

def main():
    # 標準入力からすべてのトークンを一度に読み込みます。
    # これにより、大量の入力に対しても高速に処理を行うことができます。
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not data:
        return
        
    # N: ファイル（文字列）の数, Q: 置換操作の回数
    N = int(data[0])
    Q = int(data[1])
    
    # N個の文字列 S_1, ..., S_N を取得します。
    S = data[2:2+N]
    
    # 置換操作のクエリ (a_j, b_j) を取得します。
    # queries には 2*Q 個のトークンが含まれます。
    queries = data[2+N:2+N+2*Q]
    
    # 【アプローチの解説】
    # 既存の解法は「各操作ごとに26文字すべての現在の状態を更新する」という
    # 前方からのアプローチ（計算量 O(26*Q)）をとっています。
    # 本解法では、操作を「後ろから」処理することで、各文字が最終的に
    # どの文字に変換されるかを O(Q + 26) で決定します。
    # 
    # 合成関数 G_j を「操作 j から Q までを順番に適用した結果」とすると、
    # G_j(x) = G_{j+1}(f_j(x)) と表せます。ここで f_j は j 番目の置換 (a_j -> b_j) です。
    # つまり、文字 a_j は「その後の操作によって b_j が最終的になる文字」に変換されます。
    
    # mapping[i] は、文字 chr(97 + i) が最終的にどの文字になるかを保持します。
    # 最初は自分自身にマップされるように初期化します。
    mapping = [chr(i + 97) for i in range(26)]
    
    # 操作を逆順（Q-1 から 0 まで）に走査します。
    for i in range(Q - 1, -1, -1):
        # a_char: 置換元の文字, b_char: 置換先の文字
        a_char = queries[2 * i]
        b_char = queries[2 * i + 1]
        
        if a_char == b_char:
            continue
            
        # 文字 a_char は、現時点で b_char が最終的になるとされている文字へ更新されます。
        # ord('a') は 97 です。
        a_idx = ord(a_char) - 97
        b_idx = ord(b_char) - 97
        mapping[a_idx] = mapping[b_idx]
        
    # 最終的な変換マップを元に、高速な文字列置換のための変換テーブルを作成します。
    src_chars = "abcdefghijklmnopqrstuvwxyz"
    dst_chars = "".join(mapping)
    trans_table = str.maketrans(src_chars, dst_chars)
    
    # 各文字列に対して一括変換を適用します。
    # str.translate は内部が C で実装されており、非常に高速です。
    results = [s.translate(trans_table) for s in S]
    
    # すべての文字列を改行で結合して出力します。
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    main()

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