概要

元素を1つずつ試験管（スタック）に投入し、スタックの一番上の元素と新しい元素が反応パターンに一致すれば両方消滅する、という操作をシミュレーションして最終的な試験管の中身を求める問題です。

考察

重要な気づき：スタックで素直にシミュレーションできる

問題文をよく読むと、以下の2点がポイントです。

1. 試験管はスタック構造：新しい元素は常に一番上（末尾）に積まれる。
2. 連鎖反応は起きない：1回の投入で起きる消滅は高々1回。消滅後に新たに露出した末尾との再チェックは行わない。

この2点のおかげで、問題は「スタックに対して push するか、条件を満たせば pop するか」という単純なシミュレーションに帰着します。

具体例で確認

例えば、\(S = \) ABBA、反応パターンが \((A, B)\) と \((B, A)\) の場合：

投入文字	スタック状態（操作前）	判定	スタック状態（操作後）
A	[]	空なので push	[A]
B	[A]	\((A, B)\) が反応パターン → pop	[]
B	[]	空なので push	[B]
A	[B]	\((B, A)\) が反応パターン → pop	[]

最終結果は空なので EMPTY を出力します。

素朴なアプローチで十分か？

各文字について「スタック末尾との反応チェック」を行いますが、反応パターンの検索をどう実装するかが鍵です。反応パターンは最大 \(676\) 個（\(26 \times 26\)）しかないので、集合（ハッシュセット）に格納すれば \(O(1)\) で判定できます。よって全体で \(O(N)\) となり、\(N \leq 10^6\) でも十分高速です。

アルゴリズム

1. 前処理：\(M\) 個の反応パターン \((X_k, Y_k)\) をハッシュセット（Pythonの set）に格納する。
2. シミュレーション：文字列 \(S\) を先頭から1文字ずつ処理する。
   • スタックが空でなく、(スタック末尾, 現在の文字) が反応パターンに含まれる場合 → スタックから末尾を削除（pop）。
   • そうでなければ → 現在の文字をスタックに追加（push）。
3. 出力：スタックが空なら EMPTY、そうでなければスタックの中身を連結して出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • 反応パターンの読み込みに \(O(M)\)、文字列の各文字に対するスタック操作と反応判定がそれぞれ \(O(1)\) で合計 \(O(N)\)。
• 空間計算量: \(O(N + M)\)
  • スタックに最大 \(O(N)\) 文字、反応パターンのセットに \(O(M)\) エントリを格納。

実装のポイント

• 高速な入力：\(N\) が最大 \(10^6\) と大きいため、Pythonでは sys.stdin.buffer.read() でまとめて読み込むことで入出力のオーバーヘッドを抑えています。

• 反応パターンの格納方法：set にタプル (X, Y) を入れることで、\(O(1)\) のルックアップが可能です。反応パターンには向きがある（\((X, Y)\) と \((Y, X)\) は別物）点に注意が必要です。

• 連鎖反応がないことの確認：問題文に「消滅が起きた後、新たに露出した末尾に対して再度反応チェックを行うことはない」と明記されているため、1回の投入につき判定は1回で済みます。もしこの条件がなければ、pop 後にさらにループで再チェックする必要がありますが、本問ではそれは不要です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    M = int(tokens[idx]); idx += 1
    S = tokens[idx]; idx += 1
    
    react = set()
    for _ in range(M):
        X = tokens[idx]; idx += 1
        Y = tokens[idx]; idx += 1
        react.add((X, Y))
    
    stack = []
    for ch in S:
        if stack and (stack[-1], ch) in react:
            stack.pop()
        else:
            stack.append(ch)
    
    if stack:
        print(''.join(stack))
    else:
        print('EMPTY')

main()

---

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