概要

スタック（積み重ね）構造の試験管に元素を順番に投入し、特定の組み合わせが隣り合った際に発生する消滅反応をシミュレーションする問題です。

考察

この問題のポイントは、「新たに投入する元素」と「現在試験管の一番上にある元素」の 2 つだけを比較すればよいという点です。

問題文に「消滅が起きた後、新たに露出した末尾に対して再度反応チェックを行うことはない」という重要な制約があります。これにより、一度の投入で起こる変化は「末尾が 1 つ消える」か「新しい元素が 1 つ増える」かのどちらか一方のみとなります。

もし連鎖的に反応が起こる仕様であれば複雑になりますが、この制約のおかげで、各ステップでスタックの末尾（最新の要素）だけを確認する単純なシミュレーションで解くことができます。

\(N\) が最大 \(10^6\) と非常に大きいため、各操作を高速に行う必要があります。具体的には以下の工夫が有効です。 1. 反応パターンの高速判定: 反応する組 \((X, Y)\) を二次元配列（テーブル）やハッシュセットで保持することで、判定を \(O(1)\) で行えるようにします。 2. 効率的なデータ構造: 要素の追加と末尾の削除が高速な「スタック」を利用します。Python のリスト（append と pop）はこれらの操作を \(O(1)\) で行えます。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 準備: 反応パターンを 26×26 の二次元配列 react[26][26] に記録します。react[X][Y] が True ならば元素 \(X\) の次に \(Y\) を入れると反応することを意味します。
2. シミュレーション:
   • 空のスタックを用意します。
   • 文字列 \(S\) の各文字 \(c\) について、順番に以下の処理を行います。
     • スタックが空でない、かつ「スタックの末尾の文字」と「今から入れる文字 \(c\)」の組み合わせが反応パターンに含まれる場合：
       • スタックの末尾を削除（pop）します。\(c\) はスタックに追加しません。
     • それ以外の場合：
       • 文字 \(c\) をスタックの末尾に追加（append）します。
3. 出力:
   • スタックが空なら EMPTY を出力します。
   • そうでなければ、スタック内の文字を結合して出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 反応パターンの受け取りに \(O(M)\)、文字列 \(S\) の各文字に対する処理に \(O(N)\) かかります。スタックの操作と反応判定は各文字に対して \(O(1)\) なので、全体で線形時間で処理可能です。
• 空間計算量: \(O(N + \Sigma^2)\)
  • スタックに最大 \(N\) 文字格納されるため \(O(N)\) です。また、反応パターンの記録に英大文字の種類数 \(\Sigma=26\) の二乗の空間が必要ですが、これは定数として扱えます。

実装のポイント

• 高速な入出力: \(N=10^6\) のため、Python では input() ではなく sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 文字の数値化: ord(char) - ord('A') とすることで、’A’-‘Z’ を 0-25 の整数に変換でき、二次元配列のインデックスとして扱いやすくなります。

• 空の状態の判定: スタックが空のときに stack[-1] を参照するとエラーになるため、必ず if stack: などで空でないことを確認してから末尾を参照するようにします。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのトークンを一度に読み込みます。
    # 大規模な入力（N=10^6）に対して効率的に処理を行うためです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # トークンを順番に取り出すためのイテレータを作成します。
    it = iter(input_data)
    try:
        # 最初のトークンは文字列の長さ N（今回はループで s を直接回すため使いません）
        _ = next(it)
        # 次のトークンは反応パターンの数 M
        m = int(next(it))
        # その次のトークンは投入する元素の列 S
        s = next(it)
    except StopIteration:
        return
    
    # 反応パターンを 26x26 の二次元配列（テーブル）として保持します。
    # 英大文字 'A'-'Z' を 0-25 の整数にマップして管理します。
    react = [[False] * 26 for _ in range(26)]
    for _ in range(m):
        try:
            # 各反応パターン (X, Y) を取得し、テーブルを更新します。
            u_char = next(it)
            v_char = next(it)
            u = ord(u_char) - 65
            v = ord(v_char) - 65
            react[u][v] = True
        except StopIteration:
            break
            
    # 試験管の状態をスタックとして管理します。
    # 処理の高速化のため、文字ではなく 0-25 の整数として保持します。
    stack = []
    
    # 文字列 S の各元素を順番に処理（投入）します。
    for char in s:
        # 新たに投入する元素を整数に変換
        v = ord(char) - 65
        
        # 試験管が空でなく、かつ「試験管の一番上（末尾）」と「投入する元素」が反応する場合
        if stack and react[stack[-1]][v]:
            # 両方の元素が消滅するため、スタックの末尾を削除し、新しい元素も追加しません。
            # 問題文の指示通り、ここで新たに露出した末尾に対しての再反応チェックは行いません。
            stack.pop()
        else:
            # 反応が起きない場合は、新しい元素をスタックの末尾に追加します。
            stack.append(v)
            
    # すべての処理が終わった後のスタックの状態を出力します。
    if not stack:
        # スタックが空の場合は "EMPTY" を出力
        sys.stdout.write("EMPTY\n")
    else:
        # スタック内の整数を文字に戻して連結し、出力します。
        sys.stdout.write("".join(chr(v + 65) for v in stack) + "\n")

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。