概要

与えられた文字列 \(S\) を左から順に試験管へ入れていき、試験管の一番上の文字と新しく入れる文字の組が反応表にあるときだけ両方消す、という操作を高速にシミュレーションする問題です。
試験管は「末尾が上」のスタックとして扱うと、そのまま実装できます。

考察

重要なポイントは次の2つです。

• 反応判定に必要なのは、毎回「現在の一番上」と「今入れる文字」の2文字だけ。
• 1回の投入で起きる反応は高々1回（連鎖反応しない）。

このため、試験管全体を毎回見直す必要はありません。
単純に文字列連結や削除を繰り返す実装だと、言語によっては1操作が \(O(N)\) になり、全体で \(O(N^2)\) になってしまう可能性があります（\(N=10^6\) なので危険）。

そこで、試験管を スタック（Pythonではリストの append/pop）で管理します。

• 文字 \(ch\) を入れるとき
  • スタックが空でなく、かつ (stack[-1], ch) が反応するなら pop（両方消滅）
  • そうでなければ append(ch)

これを \(S\) の全ての文字に対して行えば、問題文の手順と一致します。

さらに反応パターンの検索を高速化するために、
英大文字26種類を使って react[26][26] の真偽表を作っておくと、判定は \(O(1)\) です。

例えば (A, B) が反応なら react[0][1] = True としておき、
判定時に react[ord(top)-65][ord(ch)-65] を見るだけです。

アルゴリズム

1. \(N, M\) と文字列 \(S\) を読む。
2. react[26][26] を False で初期化。
3. 各反応パターン \((X, Y)\) について react[X][Y] = True にする（文字を 0〜25 に変換）。
4. 空スタック stack を用意。
5. \(S\) を左から順に見て、各文字 ch について:
   • stack が空でなく、react[top][ch] == True なら stack.pop()
   • そうでなければ stack.append(ch)
6. 最後に stack が空なら EMPTY、そうでなければ "".join(stack) を出力。

計算量

• 時間計算量: \(O(N + M)\)
  （各文字は高々1回 push / 1回 pop、反応判定は定数時間）
• 空間計算量: \(O(N + 26^2)\)
  （スタック最大 \(N\)、反応表は定数サイズ）

実装のポイント

• 反応には向きがあるので、react[x][y] と react[y][x] は別物です。

• 問題文どおり、1回の投入で連鎖反応はしません。今回の if ... pop else append はそれを正確に再現しています。

• 速度のため、入力は sys.stdin.readline を使うと安心です。

• 最後に空なら必ず EMPTY を出力します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = input().strip()

    react = [[False] * 26 for _ in range(26)]
    for _ in range(M):
        x, y = input().split()
        react[ord(x) - 65][ord(y) - 65] = True

    stack = []
    for ch in S:
        if stack and react[ord(stack[-1]) - 65][ord(ch) - 65]:
            stack.pop()
        else:
            stack.append(ch)

    if stack:
        print("".join(stack))
    else:
        print("EMPTY")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。