概要

2つの文字列を各位置ごとに比較し、ルールに従って1文字ずつ復元結果を決定する問題です。

考察

この問題は、各位置 \(i\) について \(S[i]\) と \(T[i]\) の2文字だけを見れば復元結果が決まるため、位置ごとに独立して処理できます。

場合分けは以下の4パターンです：

\(S[i]\)	\(T[i]\)	復元結果	例
?	?	?（どちらも読めなかった）	?, ? → ?
?	英小文字	\(T[i]\) を採用	?, b → b
英小文字	?	\(S[i]\) を採用	a, ? → a
同じ英小文字	同じ英小文字	その文字を採用	a, a → a
異なる英小文字	異なる英小文字	!（矛盾）	a, b → !

例えば、\(S = \) ab?d?f、\(T = \) a?cd?g の場合：

• 位置1: a と a → 一致 → a
• 位置2: b と ? → b を採用
• 位置3: ? と c → c を採用
• 位置4: d と d → 一致 → d
• 位置5: ? と ? → ?
• 位置6: f と g → 矛盾 → !

復元結果は abcd?! となり、! が含まれるので Yes を出力します。

この問題は単純な場合分けなので、素朴に \(N\) 回ループするだけで十分高速です。特別なアルゴリズムは不要ですが、\(N\) が最大 \(5 \times 10^5\) であるため、入出力を効率的に行うことが重要です。

アルゴリズム

1. 文字列 \(S\), \(T\) を読み込む。
2. 各位置 \(i = 0, 1, \ldots, N-1\) について、\(S[i]\) と \(T[i]\) を比較し、上記のルールに従って復元文字を決定する。
3. 復元文字をすべてつなげた文字列を出力する。
4. 復元結果に ! が1つでも含まれていれば Yes、なければ No を出力する。

計算量

• 時間計算量: \(O(N)\) — 各位置を1回ずつ見るだけ
• 空間計算量: \(O(N)\) — 復元結果の文字列を格納するため

実装のポイント

• 高速な入力: Python では sys.stdin.buffer.read() を使うことで、大きな入力を高速に読み込めます。input() を \(N\) 回呼ぶよりもはるかに効率的です。

• リストに追加してから結合: 文字列の連結を繰り返すと \(O(N^2)\) になる可能性があるため、リストに append していき、最後に ''.join(result) で一括結合するのが定石です。

• フラグ管理: ! が出現したかどうかを has_conflict というブール変数で管理し、最後にまとめて判定しています。復元文字列を全探索して ! を探すよりも効率的です（定数倍の差ですが）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    lines = input_data.split()
    N = int(lines[0])
    S = lines[1]
    T = lines[2]
    
    result = []
    has_conflict = False
    
    for i in range(N):
        s = S[i]
        t = T[i]
        if s == '?' and t == '?':
            result.append('?')
        elif s == '?':
            result.append(t)
        elif t == '?':
            result.append(s)
        elif s == t:
            result.append(s)
        else:
            result.append('!')
            has_conflict = True
    
    print(''.join(result))
    print('Yes' if has_conflict else 'No')

main()

---

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