概要

複数の文字列に対し、指定された文字置換操作を順番に適用した結果を出力する問題です。

考察

この問題では、合計長さが最大 \(10^6\) となる複数の文字列に対して、最大 \(10^5\) 回の置換操作を行う必要があります。もし毎回すべての文字列を実際に操作していたら、非常に時間がかかりすぎてしまいます（TLE）。

重要な着眼点は、「各英小文字が最終的にどの文字に変わるか」だけを管理すれば良いということです。つまり、各操作ごとに文字列を書き換えるのではなく、操作全体を通して「元の文字 → 最終的な文字」の対応関係（マッピング）を効率よく管理することがポイントです。

さらに重要なのは、このマッピングを後ろから構築するというアイデアです。例えば、操作「a → b」があったとき、すでにその後に「b → c」という操作があるなら、「a」は最終的には「c」になります。このように、後の操作ほど影響が大きいので、後ろから処理することで一度の操作で正しい最終状態を求めることができます。

例えば以下のような操作を考えましょう： - 操作1: ‘a’ → ‘b’ - 操作2: ‘b’ → ‘c’

前から処理すると、まず ‘a’ が ‘b’ になり、次に ‘b’（含む以前の ‘a’）が ‘c’ になるように更新が必要です。しかし、後ろから処理すれば、まず ‘b’ → ‘c’ を反映しておき、次に ‘a’ → ‘b’ を処理するときに「a は最終的に c になる」とすぐに分かるようになります。

このようにして、全ての操作を後ろから処理して各文字の最終的な行き先を決定し、最後に各文字列をそのマッピングに従って一括変換すれば効率的に答えを求められます。

アルゴリズム

1. 各英小文字の最終的な変換先を管理する配列 mapping を用意する（初期状態では各文字は自分自身にマップされる）。
2. 置換操作を後ろから前へ処理し、mapping[a] = mapping[b] として更新する。
3. すべての操作を処理した後、各文字列に対して mapping を使って一括変換を行う。
4. 変換後の文字列を出力する。

計算量

• 時間計算量: \(O(\sum |S_i| + Q)\)
  （各文字列を一回だけ走査し、操作は定数時間で処理される）
• 空間計算量: \(O(26 + \sum |S_i|)\)
  （マッピングテーブルと結果の文字列分）

実装のポイント

• 操作を後ろから処理することを意識する。

• 英小文字とインデックス（0～25）の変換は ord(c) - ord('a') を使う。

• 入力を高速に読み込むために sys.stdin.read を使用している。

  ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    
    strings = data[2:2+N]
    operations = data[2+N:]
    
    # 文字の変換マッピングを後ろから構築する
    # 初期状態では各文字は自分自身にマッピングされる
    mapping = list(range(26))  # ord('a') + i の文字は最終的に ord('a') + mapping[i] になる
    
    # 操作を後ろから処理する
    for i in range(Q-1, -1, -1):
        a = ord(operations[2*i]) - ord('a')
        b = ord(operations[2*i+1]) - ord('a')
        # a から b への変換を追加する
        # すでに a が別の文字にマッピングされている場合、それを維持する
        # しかし、後ろから処理しているので、b 自体が最終的な値にマッピングされている
        # よって、a が最終的にどのような値になるかを b の最終値に設定する
        mapping[a] = mapping[b]
    
    # 各文字列を変換する
    result = []
    for s in strings:
        converted = []
        for c in s:
            converted.append(chr(ord('a') + mapping[ord(c) - ord('a')]))
        result.append(''.join(converted))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。