概要

パスワードの一部が復旧された情報に基づいて、候補となる文字列が正しいパスワードかどうかを判定する問題です。

考察

この問題では、パスワードの一部の位置とその文字が分かっており、それらの位置の文字が候補文字列と一致しているかを確認する必要があります。

素朴な方法として、毎回候補文字列の全位置を調べるのではなく、復旧されている位置だけをチェックすればよいという点に注目します。もし毎回全部の文字を確認していたら、不要な計算が増えてしまい、特に \(N\) が大きいときに無駄になります。

さらに、復旧データ \((P_i, C_i)\) を効率よく管理するために、位置をキー、文字を値とする辞書（連想配列）を使うと、各位置の正しい文字を高速に参照できます。

このように、必要な情報だけを取り出し、効率的なデータ構造で管理することで、高速に判定を行うことができます。

アルゴリズム

1. 復旧データ \((P_i, C_i)\) を読み込み、位置をキー、文字を値とする辞書 restore に格納します。
2. 各候補文字列 \(T_j\) について、restore に登録されている位置の文字と \(T_j\) の該当位置の文字を比較します。
3. 一つでも不一致があれば No、すべて一致していれば Yes を出力します。

たとえば、以下の入力があったとします：

N=5, M=2
P=[2, 5], C=['a', 'b']
=> restore = {2: 'a', 5: 'b'}

候補文字列 "xaxxb" は、位置2が 'a'、位置5が 'b' なので、条件を満たし Yes となります。

計算量

• 時間計算量: \(O(M + Q \cdot M)\)
  （復旧データの読み込みに \(O(M)\)、各クエリで最大 \(M\) 文字を比較）
• 空間計算量: \(O(M + N \cdot Q)\)
  （復旧データの保存に \(O(M)\)、入力文字列全体の保持に \(O(N \cdot Q)\)）

実装のポイント

• 復旧データをリストではなく辞書で管理することで、位置から文字を高速に引き出せる。

• 各クエリ文字列のインデックスは0始まりだが、問題の位置指定は1始まりなので、アクセス時に pos - 1 とすることに注意。

• 入力を高速化するため、sys.stdin.read を使って一度に読み込むと良い。

  ソースコード

# 入力の読み込み
import sys
input = sys.stdin.read

data = input().split()
idx = 0

N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1
Q = int(data[idx])
idx += 1

# 復旧データを辞書で保持
restore = {}
for _ in range(M):
    p = int(data[idx])
    idx += 1
    c = data[idx]
    idx += 1
    restore[p] = c

# 各候補文字列に対して判定
results = []
for _ in range(Q):
    T = data[idx]
    idx += 1
    valid = True
    for pos, char in restore.items():
        if T[pos - 1] != char:
            valid = False
            break
    results.append("Yes" if valid else "No")

# 結果の出力
print("\n".join(results))

---

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