概要

復旧できた位置だけ文字が一致するかを各候補文字列ごとに確認し、すべて一致すれば Yes、1つでも違えば No を出力する問題です。

考察

この照合システムは「復旧済みの位置だけをチェックし、それ以外は何でもよい」というルールなので、各候補文字列 \(T_j\) が正しいと判定される条件は次の一言に尽きます：

• 復旧情報 \((P_i, C_i)\) のすべてについて、\(T_j\) の \(P_i\) 文字目が \(C_i\) と一致すること

つまり、文字列全体（長さ \(N\)）を毎回比較する必要はありません。見るべきなのは復旧できた \(M\) 箇所だけです。

素朴に「毎回 \(N\) 文字すべてを見る」実装にすると、計算量が \(O(NQ)\) になります。最大で \(N=10^5, Q=10^3\) なので \(10^8\) 文字チェックとなり、言語や定数次第で重くなりがちです。
そこで、「復旧済み位置 \(M\) 個だけを見る」ことで、各クエリを \(O(M)\) に抑えられます。

具体例： - \(N=5\) - 復旧: \((2,'a'), (5,'z')\) - 候補 baqqz は 2文字目が a、5文字目が z なので Yes - 候補 bbqqz は 2文字目が b で不一致なので No
（他の位置は何でもよい）

アルゴリズム

1. 復旧情報を配列に保存する
   
   • 位置 \(P_i\) は 0-index に直して pos[i] = P_i - 1
   • 期待する文字を exp[i] = C_i として保持
2. 各候補文字列 \(T\) について以下を行う
   
   • \(i=1..M\) について、T[pos[i]] == exp[i] を確認
   • 1つでも不一致なら No、すべて一致なら Yes
3. 特別ケースとして \(M=0\) のときは、どの位置もチェックされないため全候補が必ず Yes

計算量

• 時間計算量: \(O(MQ)\)（\(M=0\) のときは \(O(Q)\)）
• 空間計算量: \(O(M)\)

実装のポイント

• 位置は 0-index に変換して扱う（P_i - 1）。

• Python では高速化のために、入力文字列を bytes として扱うと添字アクセスが速いです。
  コードでは sys.stdin.buffer.readline と strip() を使い、t[pos]（整数）と exp（ASCII整数）を比較しています。

• 途中で不一致が見つかったら 即 break して無駄な比較を避けます。

• \(M=0\) の場合は全て Yes なので、候補文字列を読むだけ読んで結果を出せます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M, Q = map(int, input().split())
    pos = [0] * M
    exp = [0] * M

    for i in range(M):
        p, c = input().split()
        pos[i] = int(p) - 1
        exp[i] = c[0]  # int (ASCII)

    out = []
    if M == 0:
        for _ in range(Q):
            input()
            out.append("Yes")
    else:
        pos_l = pos
        exp_l = exp
        for _ in range(Q):
            t = input().strip()  # bytes
            ok = True
            for i in range(M):
                if t[pos_l[i]] != exp_l[i]:
                    ok = False
                    break
            out.append("Yes" if ok else "No")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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