概要

この問題は、長さ \(N\) のパスワードのうち \(M\) 箇所の文字が判明しているとき、与えられる \(Q\) 個の候補文字列がその条件（判明している位置の文字が一致しているか）を満たしているかを判定する問題です。

考察

パスワードの照合において、以下の2つのポイントが重要です。

1. チェックが必要な場所: 復旧された \(M\) 箇所の位置 \(P_i\) についてのみ、候補文字列 \(T_j\) の文字が \(C_i\) と一致するかを確認すればよいです。復旧されていない位置については、どんな文字であっても判定に影響しません。
2. 計算量の見積もり:
   • 文字列の長さ \(N\) は最大 \(10^5\)、候補の数 \(Q\) は \(10^3\) です。
   • 各候補文字列に対して最大 \(M\) 箇所のチェックを行うため、全体の計算量は最悪で \(O(Q \times M)\) となります。
   • \(M \leq N\) なので、\(10^3 \times 10^5 = 10^8\) 回程度の比較が発生する可能性があります。Pythonの場合、この計算量は実行制限時間に対してやや厳しいため、効率的な実装（高速な入出力や不要な処理の削減）が求められます。

アルゴリズム

以下の手順で判定を行います。

1. 復旧データの保存: \(M\) 個の復旧データ \((P_i, C_i)\) をリストに格納します。このとき、プログラミング言語の配列の添字に合わせて \(P_i\) を \(1\) 減らして「0-indexed」にしておくと扱いやすくなります。
2. クエリの処理: 各候補文字列 \(T_j\) について、以下の処理を繰り返します。
   • 一致フラグ（is_match）を True に初期化する。
   • 保存した \(M\) 個の復旧データを順に見ていき、\(T_j\) の \(P_i\) 文字目が \(C_i\) と異なる場合は、フラグを False にしてループを抜ける（早期終了）。
   • フラグが True のままなら Yes、そうでなければ No を出力する。

計算量

• 時間計算量: \(O(QN)\)
  • 各クエリに対して最大 \(M\) 回の比較を行います。\(M \leq N\) であるため、全体で \(O(QM)\)、あるいは文字列の読み込みを含めて \(O(QN)\) となります。
  • 今回の制約（\(QN \approx 10^8\)）では、早期終了（break）や高速な入出力が実行時間に大きく貢献します。
• 空間計算量: \(O(N + M)\)
  • 復旧データの保存に \(O(M)\)、入力文字列の保持に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: input() の代わりに sys.stdin.readline() を使用することで、大量の文字列入力にかかる時間を短縮しています。

• 不要な文字列操作の回避: t.strip() などのメソッドは、呼び出すたびに長さ \(N\) の新しい文字列を生成するため、ループ内で行うと \(O(QN)\) の重い処理になります。改行文字が含まれていても、インデックス \(P_i\)（\(< N\)）を指定してアクセスする分には影響がないため、そのまま比較を行っています。

• 早期終了: 1箇所でも文字が異なればその時点で No と確定するため、break を使って残りのチェックをスキップします。

  ソースコード

import sys

def solve():
    # Use sys.stdin.readline for fast input reading
    input_readline = sys.stdin.readline
    
    # Read the first line containing N (length), M (known characters), and Q (queries)
    line1 = input_readline().split()
    if not line1:
        return
    n, m, q = map(int, line1)
    
    # Store the known characters as a list of tuples (0-indexed position, character)
    # Using a list of tuples is efficient for iteration in the main loop
    known = []
    for _ in range(m):
        line = input_readline().split()
        if not line:
            break
        # The position P_i is 1-indexed, so we subtract 1 to make it 0-indexed
        p = int(line[0]) - 1
        c = line[1]
        known.append((p, c))
        
    # Prepare a list to collect results for each query
    output = []
    # Pre-binding the append method of the list can provide a slight speed boost
    out_append = output.append
    
    # Process each candidate string T_j
    for _ in range(q):
        # Read the next candidate string
        t = input_readline()
        if not t:
            break
        
        # We perform the matching check for each known position.
        # Note: We do not call t.strip() here because it would create a new string 
        # of length N in every iteration, which is O(N). Since we only care 
        # about the characters at specific indices p < N, and sys.stdin.readline() 
        # includes the newline character at index N or later, t[p] is safe.
        is_match = True
        for p, c in known:
            if t[p] != c:
                is_match = False
                break
        
        # Append "Yes" if all restored positions matched, otherwise "No"
        if is_match:
            out_append("Yes")
        else:
            out_append("No")
    
    # Print all accumulated results at once, separated by newlines
    if output:
        sys.stdout.write('\n'.join(output) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。