概要

パスワードの一部の位置だけが判明している状態で、候補文字列がその判明部分とすべて一致しているかを判定する問題です。

考察

この問題のポイントは、パスワード全体は不明だが「位置 \(P_i\) の文字は \(C_i\) である」という情報が \(M\) 個あることです。候補文字列を受理するかどうかは、復旧済みの位置だけをチェックすればよく、それ以外の位置は何でもOKです。

例えば、\(N = 5\)、復旧データが「2文字目が a」「4文字目が c」の場合を考えます。

• 候補 xaxcx → 2文字目が a、4文字目が c で一致 → Yes
• 候補 xbxcx → 2文字目が b で不一致 → No

素朴に毎回パスワード全体（\(N\) 文字）を走査する方法でも動きますが、復旧済みの \(M\) 箇所だけをチェックすれば十分なので、無駄な比較を省けます。

本問では \(Q \leq 10^3\)、\(M \leq N \leq 10^5\) なので、各候補につき \(M\) 箇所をチェックしても最大 \(10^3 \times 10^5 = 10^8\) 程度の操作ですが、辞書の走査とインデックスアクセスは軽量なため十分間に合います。

アルゴリズム

1. 復旧データの読み込み: \(M\) 個の \((P_i, C_i)\) を辞書（ハッシュマップ）に格納する。キーは 0-indexed の位置 \(P_i - 1\)、値は文字 \(C_i\)。

2. 各候補文字列の判定: \(Q\) 個の候補文字列 \(T\) それぞれについて、辞書に格納された全ての位置 pos に対して T[pos] が対応する文字 ch と一致するかを確認する。

   • すべて一致すれば Yes
   • 1つでも不一致があれば No（即座に打ち切る）

3. 結果の出力: 各候補について Yes または No を出力する。

計算量

• 時間計算量: \(O(M + Q \cdot M)\)
  • 復旧データの読み込みに \(O(M)\)、各候補文字列について \(M\) 箇所のチェックに \(O(M)\)、これを \(Q\) 回繰り返す。
• 空間計算量: \(O(N + M)\)
  • 辞書に \(M\) 個のエントリ、候補文字列に最大 \(N\) 文字を保持。

実装のポイント

• 1-indexed → 0-indexed の変換: 問題文では位置が 1-indexed で与えられるため、辞書に格納する際に \(P_i - 1\) として 0-indexed に変換しています。

• 早期打ち切り（early break）: 不一致が見つかった時点で break してループを抜けることで、無駄な比較を省いています。

• 高速な入力処理: sys.stdin.buffer.read() で一括読み込みし、split() でトークン分割することで、大量入力時のI/Oボトルネックを回避しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    M = int(tokens[idx]); idx += 1
    Q = int(tokens[idx]); idx += 1
    
    known = {}
    for _ in range(M):
        p = int(tokens[idx]); idx += 1
        c = tokens[idx]; idx += 1
        known[p - 1] = c
    
    out = []
    for _ in range(Q):
        T = tokens[idx]; idx += 1
        ok = True
        for pos, ch in known.items():
            if T[pos] != ch:
                ok = False
                break
        out.append("Yes" if ok else "No")
    
    sys.stdout.write("\n".join(out) + "\n")

main()

この解説は claude4.6opus-thinking によって生成されました。