概要

2つの文字列 \(S, T\) を同じ位置どうしで見比べ、ルール通りに復元文字列を作りつつ、矛盾（!）が1つでも出たかを判定する問題です。

考察

各位置 \(i\) は他の位置と独立に決まります。つまり、位置 \(i\) の復元結果は \(S[i]\) と \(T[i]\) の2文字だけを見れば一意に決まり、全体としてはそれを \(N\) 回繰り返すだけです。

重要な観察は以下の4ケース分けがそのまま解答手順になることです：

• 同じ英小文字同士：その文字で確定（例：a と a → a）
• 片方が ?：もう片方の英小文字を採用（例：? と b → b）
• 両方 ?：不明なので ? のまま（例：? と ? → ?）
• 異なる英小文字同士：どちらが正しいか判定不能なので !（例：c と d → !）

素朴に「元の板書全体を推測して整合する文字列を探す」などを考えると、候補が指数的に増えて現実的ではありません（TLE）。しかし本問は「復元ルールが位置ごとに確定している」ため、探索は不要で、単純な1回走査で解けます。

アルゴリズム

1. 長さ \(N\) の結果配列 res を用意し、矛盾フラグ has_conflict=False を用意する。
2. \(i=1..N\) について \((S[i], T[i])\) を見て次のように res[i] を決める。
   • \(S[i] == T[i]\) なら res[i]=S[i]（? 同士もここに含まれる）
   • そうでなく \(S[i]=='?'\) なら res[i]=T[i]
   • そうでなく \(T[i]=='?'\) なら res[i]=S[i]
   • それ以外（異なる英小文字同士）なら res[i]='!'、has_conflict=True
3. res を連結して復元文字列を出力し、has_conflict が True なら Yes、そうでなければ No を出力する。

（例） - \(S=\text{"a?c"}\), \(T=\text{"ab?"}\) のとき
- 1文字目：a と a → a
- 2文字目：? と b → b
- 3文字目：c と ? → c
復元結果は "abc"、矛盾なしなので No。

計算量

• 時間計算量: \(O(N)\)（各位置を1回ずつ処理）
• 空間計算量: \(O(N)\)（復元結果の文字列を保持）

実装のポイント

• \(N\) が最大 \(5 \times 10^5\) と大きいので、1文字ずつ += で文字列連結すると遅くなることがあります。配列（リスト）に入れて最後に ''.join(res) するのが安全です。

• 入力も大きいので、sys.stdin.buffer.read() を使うと高速に読み取れます。

• S[i]==T[i] の分岐により ? 同士（? と ?）も自然に処理できます。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().splitlines()
    n = int(data[0])
    s = data[1].decode()
    t = data[2].decode()

    res = [''] * n
    has_conflict = False

    for i, (a, b) in enumerate(zip(s, t)):
        if a == b:
            res[i] = a
        elif a == '?':
            res[i] = b
        elif b == '?':
            res[i] = a
        else:
            res[i] = '!'
            has_conflict = True

    sys.stdout.write(''.join(res) + '\n' + ('Yes' if has_conflict else 'No'))

if __name__ == "__main__":
    main()

---

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