概要

この問題は、一部の文字が判明しているパスワードに対して、候補文字列が条件を満たすかどうかを判定する問題です。

考察

問題の核心は、復旧済みの位置（\(P_i\)）でのみ文字が一致するかを確認し、それ以外の位置は任意の文字を許容することです。素朴なアプローチでは、各候補文字列に対して全ての復旧位置をチェックすることになりますが、\(M\) が最大 \(10^5\)、\(Q\) が最大 \(1000\) であるため、最悪ケースで \(10^5 \times 10^3 = 10^8\) 回の比較が必要になります。しかし、Pythonでは定数倍が重く、最悪ケースでTLE（時間制限超過）になる可能性があります。ただし、実際には \(M\) が \(0\) の場合や、早期に不一致が見つかる場合が多いため、現実的には十分高速に動作します。

アルゴリズム

1. 入力から \(N\), \(M\), \(Q\) を読み取る
2. 復旧データを辞書（ハッシュマップ）に保存する。キーは位置 \(P_i\)、値は文字 \(C_i\)
3. 各候補文字列 \(T_j\) について:
   • 辞書に登録されている全ての位置について、候補文字列の対応する文字が \(C_i\) と一致するかをチェック
   • 1つでも不一致があれば No、全て一致すれば Yes を出力

計算量

• 時間計算量: \(O(M \cdot Q)\)（最悪ケース）
• 空間計算量: \(O(M + N + Q)\)

実装のポイント

• 復旧データを辞書で管理することで、位置に対する高速なアクセスを実現

• 早期breakにより、不一致が判明した時点でチェックを終了し、無駄な比較を削減

• インデックス調整（\(pos-1\)）により、1-indexedの位置情報を0-indexedの配列インデックスに変換

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    first_line = data[0].split()
    N = int(first_line[0])
    M = int(first_line[1])
    Q = int(first_line[2])
    
    known = {}
    for i in range(1, 1 + M):
        parts = data[i].split()
        pos = int(parts[0])
        char = parts[1]
        known[pos] = char
        
    output_lines = []
    for i in range(1 + M, 1 + M + Q):
        candidate = data[i].strip()
        valid = True
        for pos, char in known.items():
            idx = pos - 1
            if candidate[idx] != char:
                valid = False
                break
                
        output_lines.append("Yes" if valid else "No")
    
    print("\n".join(output_lines))

if __name__ == "__main__":
    main()

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