概要

高橋君と青木君のノートに書かれた2つの文字列を比較し、問題文中のルールに従って復元結果を生成し、矛盾があるかどうかを判定する問題です。

考察

各文字位置について、\(S\) と \(T\) の文字を比較して復元結果を決定します。重要な観察は以下の4つのケースを適切に処理することです： 1. 両方の文字が同じ場合（英小文字または ?）：その文字を採用 2. 一方が ? で他方が英小文字の場合：英小文字を採用 3. 両方とも ? の場合：? を採用 4. 両方とも英小文字だが異なる場合：矛盾を示す ! を採用

素朴なアプローチでは、各位置を1文字ずつ比較するだけで十分であり、\(N\) が最大 \(5 \times 10^5\) であるため、単純なループで効率的に処理できます。

アルゴリズム

1. 入力として文字列の長さ \(N\)、文字列 \(S\)、文字列 \(T\) を受け取ります。
2. 結果を格納するリスト res と、矛盾の有無を表すフラグ has_error を初期化します。
3. 各インデックス \(i\) (\(0 \leq i < N\)) について以下を実行します：
   • \(S[i]\) と \(T[i]\) が等しい場合：
     • 両方が ? なら結果に ? を追加
     • それ以外（英小文字）ならその文字を追加
   • 等しくない場合：
     • \(S[i]\) が ? なら \(T[i]\)（英小文字）を追加
     • \(T[i]\) が ? なら \(S[i]\)（英小文字）を追加
     • どちらも英小文字で異なるなら ! を追加し、has_error を True に設定
4. 結果の文字列を生成して出力し、has_error が True なら “Yes”、そうでなければ “No” を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 各文字を1回ずつ処理するため
• 空間計算量: \(O(N)\)
  • 結果の文字列を格納するためのリストが必要なため

実装のポイント

• 各ケースをif-elseで分岐させ、ルール通りに処理します。

• 矛盾（!）が1回でも出現したかをフラグで管理します。

• 文字列の結合はリストに追加し、最後に join することで効率化しています。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0].strip())
    S = data[1].strip()
    T = data[2].strip()
    
    res = []
    has_error = False
    
    for i in range(n):
        s_char = S[i]
        t_char = T[i]
        
        if s_char == t_char:
            if s_char == '?':
                res.append('?')
            else:
                res.append(s_char)
        else:
            if s_char == '?':
                res.append(t_char)
            elif t_char == '?':
                res.append(s_char)
            else:
                res.append('!')
                has_error = True
                
    result_str = ''.join(res)
    print(result_str)
    print("Yes" if has_error else "No")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。