概要

各本棚にある本のタイトルの中から、検索クエリの文字列を部分列として含むものがあるかどうかを判定し、該当する本棚の数を答える問題。

考察

この問題では、「文字列 \(T\) が文字列 \(S\) の部分列であるか？」という判定を繰り返し行う必要があります。
部分列であるとは、\(S\) からいくつかの文字を削除（ただし順序は保持）することで \(T\) を得られることを意味します。

例えば、S = "abcde" に対して T = "ace" は部分列です。a, c, e が順番に現れているためです。

素朴なアプローチとその問題

単純に考えると、クエリごとにすべての本棚→すべての本のタイトルに対して、部分列判定を行えばよいように思えます。
しかし、制約を見ると、

• 最大で \(N = 100\) 個の本棚
• 各本棚に最大で数千冊の本（全体で最大 \(5000\) 冊）
• クエリも最大 \(Q = 200\) 個

となるため、全探索でも十分間に合う可能性があります。ただし、部分列判定の処理が効率的でないと間に合わないことがあります。

部分列判定の工夫

Python では iter() と all(c in it for c in t) の組み合わせを使うことで、効率的に部分列判定が可能です。
これは、イテレータを使いながら前から順に文字が見つかるかをチェックする方法で、一度使った位置以降しか見ないので正しい部分列判定になります。

この実装により、一つの部分列判定が \(O(|S|)\) 程度で済みます。

アルゴリズム

1. まず入力をすべて読み込み、本棚ごとの本のタイトルリストを保持します。
2. 各検索クエリ \(T\) に対して以下を行う：
   • 各本棚について、その中のいずれかのタイトルが \(T\) を部分列として含むかを判定。
   • 含むタイトルが1つでもあれば、その本棚はカウントされる。
3. クエリごとに該当する本棚数を出力。

部分列判定は、イテレータを使った効率的な方法を用いることで、高速に行います。

計算量

• 時間計算量: \(O(Q \cdot N \cdot K_{\text{avg}} \cdot (|S|_{\text{avg}} + |T|))\)
  • 各クエリに対し、全本棚・全タイトルで部分列判定を行う。
  • 一つの部分列判定が \(O(|S|)\)。
• 空間計算量: \(O(\sum |S| + \sum |T|)\)
  • 入力データをすべてメモリ上に保持する。

※ 実際には制約が緩いため、高速化された部分列判定によって十分間に合います。

実装のポイント

• 入力を一度に読み込んで分割する sys.stdin.read を使うことで、入力処理の時間を短縮できる。
• 部分列判定はイテレータを活用した all(c in it for c in t) が簡潔かつ高速。
• 各クエリごとに、本棚単位で「1冊でもヒットすればOK」なので any() を使うと見やすく効率的。

## ソースコード

```python
def is_subsequence(s, t):
    it = iter(s)
    return all(c in it for c in t)

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    
    shelves = []
    for _ in range(N):
        K = int(data[idx])
        idx += 1
        titles = data[idx:idx+K]
        idx += K
        shelves.append(titles)
    
    Q = int(data[idx])
    idx += 1
    queries = data[idx:idx+Q]
    
    results = []
    for T in queries:
        count = 0
        for shelf in shelves:
            if any(is_subsequence(title, T) for title in shelf):
                count += 1
        results.append(count)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

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