概要

試験管の状態 \(T\) は「末尾が一番上」のスタックとして扱えるので、左から順に文字を見ながら「積む / 1 個だけ消す」を繰り返せばよい問題です。
反応するかどうかは「現在の一番上の文字」と「新しく入れる文字」の 2 文字だけで決まるため、スタックでシミュレーションできます。

考察

この問題で大事なのは、毎回見るべきなのは試験管の一番上だけ ということです。

新しい文字 \(S_i\) を投入するとき、

• \(T\) が空なら、そのまま積む
• \(T\) の一番上を \(c\) として、\((c, S_i)\) が反応パターンにあるなら
  • \(c\) を取り除く
  • \(S_i\) も入れない
• そうでなければ \(S_i\) を積む

という処理をすればよいです。

ここで重要なのは、問題文に

消滅が起きた後、新たに露出した \(T\) の末尾に対して再度反応チェックを行うことはない

とあることです。
つまり、1 回の投入で起こる反応は高々 1 回 です。
連鎖反応を考える必要はありません。

なぜスタックなのか

試験管の末尾が一番上に対応しているので、

• 末尾に追加する
• 末尾を削除する
• 末尾を見る

という操作が頻繁に出てきます。
これはまさにスタックそのものです。

たとえば、\(S = \texttt{ABCA}\) で、反応パターンが \((A,B), (C,A)\) だとします。

1. A を入れる → A
2. B を入れる
   一番上は A、\((A,B)\) は反応する → A と B が消える → 空
3. C を入れる → C
4. A を入れる
   一番上は C、\((C,A)\) は反応する → 空

最終的に空になります。

素朴な方法がまずい理由

1. 反応パターンを毎回線形探索する

各文字を入れるたびに、\(M\) 個の反応パターンを順番に調べると、計算量は \(O(NM)\) になります。

制約では

• \(N \le 10^6\)
• \(M \le 676\)

なので、最悪で \(10^6 \times 676\) 回程度の判定が必要になり、かなり重いです。

2. Python の文字列をそのまま更新する

Python の文字列は immutable（変更不可）なので、

• 末尾に追加
• 末尾を削除

を文字列のまま毎回行うと、都度新しい文字列を作ることになり、最悪 \(O(N^2)\) になりえます。

どう解決するか

• 試験管 \(T\) は リストを使ったスタック で管理する
• 反応パターンは \(26 \times 26\) の真偽表 にして、\(O(1)\) で判定する

英大文字は 26 種類しかないので、
react[x][y] = True なら \((x, y)\) が反応する、としておけば高速です。

これなら各文字について行う処理は定数時間で済み、全体で \(O(N + M)\) になります。

アルゴリズム

1. react[26][26] をすべて False で初期化する。
2. 与えられた反応パターン \((X_k, Y_k)\) について、react[X_k][Y_k] = True にする。
3. 空のスタック stack を用意する。
4. 文字列 \(S\) を左から順に見ていく。
   • 現在の文字を ch とする
   • stack が空でなく、かつ
     react[stack の一番上][ch] == True なら
     • stack.pop() する
     • ch は積まない
   • そうでなければ
     • stack.append(ch) する
5. 最後に stack が空なら EMPTY を出力し、そうでなければ結合して出力する。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + 26^2)\)

※ \(26^2 = 676\) は定数なので、空間計算量は実質 \(O(N)\) です。

実装のポイント

• 反応パターンは向き付きです。\((X, Y)\) があっても \((Y, X)\) があるとは限らないので、必ず順番通りに管理します。

• 英大文字は A を 0 として 0〜25 に変換すると、react に直接アクセスできて便利です。

• \(N\) が大きいので、入力は sys.stdin.buffer.read() を使って高速化しています。

• 最後にスタックが空なら、空文字列ではなく必ず EMPTY を出力します。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    m = int(data[1])
    s = data[2].decode()

    react = [[False] * 26 for _ in range(26)]
    idx = 3
    for _ in range(m):
        x = data[idx][0] - 65
        y = data[idx + 1][0] - 65
        react[x][y] = True
        idx += 2

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

    sys.stdout.write(''.join(stack) if stack else 'EMPTY')

if __name__ == "__main__":
    main()

---

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