概要

複数の文字列に対して文字の置換操作を繰り返し行う問題です。各文字が最終的にどの文字に変換されるかを効率的に追跡することで解きます。

考察

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

最も単純な方法は、各置換操作のたびにすべての文字列を走査して文字を置き換えることです。

しかし、この方法では： - 全文字列の長さの合計が最大 \(10^6\) - 置換操作が最大 \(10^5\) 回

よって、最悪で \(10^6 \times 10^5 = 10^{11}\) 回の操作が必要となり、TLE（時間超過）になります。

重要な気づき

文字は英小文字の26種類しかありません。

各置換操作は「文字 \(a\) を文字 \(b\) に変える」というものなので、各文字が最終的にどの文字になるかだけを追跡すれば十分です。

例えば、以下の操作を考えます： 1. a → b 2. b → c

この場合、元々 a だった文字は、操作1で b になり、操作2で c になります。 元々 b だった文字も、操作2で c になります。

つまり、最終的なマッピングは「a → c, b → c」となります。

解決方法

1. 最初に「各文字はそのまま」というマッピング（a→a, b→b, …）を用意
2. 各置換操作で、現在その文字に変換される予定のすべての文字のマッピング先を更新
3. 最後に、全文字列に対してマッピングを一括適用

アルゴリズム

1. 初期化: 26文字のマッピングテーブルを作成（各文字は自分自身に対応）

   mapping = {'a': 'a', 'b': 'b', ..., 'z': 'z'}
   

2. 置換操作の処理: 各操作 \((a_j, b_j)\) について

   • マッピングテーブル全体を走査
   • 現在 \(a_j\) にマッピングされている文字を、\(b_j\) にマッピングするよう更新

3. 文字列の変換: すべての操作が終わった後

   • 最終的なマッピングテーブルを使って、各文字列を一度だけ変換

計算量

• 時間計算量: \(O(Q \times 26 + \sum|S_i|)\)

  • 各置換操作で26文字のマッピングを確認: \(O(26Q)\)
  • 全文字列の変換: \(O(\sum|S_i|)\)
  • 制約より、\(Q \leq 10^5\), \(\sum|S_i| \leq 10^6\) なので十分高速

• 空間計算量: \(O(\sum|S_i|)\)

  • 入力文字列と出力文字列の保持に必要

実装のポイント

1. マッピングの更新方法に注意

   • 操作「\(a\) → \(b\)」では、現在のマッピング先が \(a\) であるすべての元の文字について、マッピング先を \(b\) に変更します
   • 直接 mapping['a'] = 'b' とするだけでは不十分です（連鎖的な置換を追跡できない）

2. Pythonの str.maketrans() と translate() の活用

   • マッピング辞書から変換テーブルを作成し、効率的に文字列を変換できます
   • 各文字列に対して1回の走査で変換が完了します

3. 入力の高速化

   • sys.stdin.read() を使うことで、大量の入力を高速に読み込めます

     ソースコード

import sys

def main():
    input = sys.stdin.read().split('\n')
    idx = 0
    N, Q = map(int, input[idx].split())
    idx += 1
    
    strings = []
    for i in range(N):
        strings.append(input[idx])
        idx += 1
    
    # Create a mapping for each character
    # mapping[c] = the character that c will become after all operations
    mapping = {chr(ord('a') + i): chr(ord('a') + i) for i in range(26)}
    
    # Process all replacement operations
    for j in range(Q):
        a, b = input[idx].split()
        idx += 1
        # For every character that currently maps to 'a', change it to map to 'b'
        for c in mapping:
            if mapping[c] == a:
                mapping[c] = b
    
    # Build translation table
    trans_table = str.maketrans(mapping)
    
    # Apply the final mapping to all strings
    result = []
    for s in strings:
        result.append(s.translate(trans_table))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

---

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