概要

高橋君と青木君のノートを照らし合わせて、元の文字列を復元する問題です。ただし、矛盾する箇所（異なる文字が両方にある）があるかどうかを判定する必要があります。

考察

この問題では、2つの文字列 \(S\) と \(T\) を各文字ごとに比較し、ルールに従って新しい文字列を作ります。重要なのは以下の4つのケースです：

1. 両方が ? → 復元できないので ?
2. 片方が ?、もう片方が英小文字 → 英小文字を採用
3. 両方が同じ英小文字 → その文字を採用
4. 両方が異なる英小文字 → 矛盾なので !

これらの処理を愚直に行うだけで十分高速に解けます。特に工夫が必要な処理もなく、ループを1回回すだけでOKです。

アルゴリズム

1. 各インデックス \(i\) について、\(S[i]\) と \(T[i]\) を比較します。
2. 上記の4つの条件に従って、復元後の文字を決定します。
3. 矛盾（!）が一度でも現れたらフラグを立てます。
4. 最後に復元された文字列と、矛盾の有無を出力します。

たとえば、入力が以下の場合：

5
a?c?e
?b?d?

• 1文字目：a vs ? → a
• 2文字目：? vs b → b
• 3文字目：c vs ? → c
• 4文字目：? vs d → d
• 5文字目：e vs ? → e

結果は "abcde"、矛盾なし（No）。

計算量

• 時間計算量: \(O(N)\)
  各文字を一度ずつしか見ないので線形時間。
• 空間計算量: \(O(N)\)
  結果の文字列を保存するリストが必要。

実装のポイント

• Pythonでは文字列の連結に + を使うと遅くなるので、いったんリストに保存して最後に ''.join() で結合するのが良い。

• 矛盾のフラグ管理は、! を追加したタイミングで True にするだけ。

  ソースコード

N = int(input())
S = input()
T = input()

result = []
has_contradiction = False

for i in range(N):
    char_s = S[i]
    char_t = T[i]
    
    if char_s == '?' and char_t == '?':
        result.append('?')
    elif char_s == '?':
        result.append(char_t)
    elif char_t == '?':
        result.append(char_s)
    elif char_s == char_t:
        result.append(char_s)
    else:
        result.append('!')
        has_contradiction = True

print(''.join(result))
if has_contradiction:
    print("Yes")
else:
    print("No")

---

この解説は qwen3-coder-480b によって生成されました。