概要

各検索クエリ文字列が本のタイトルの「部分列」として含まれるかを判定し、該当する本を1冊以上持つ本棚の数を数える問題です。

考察

部分列とは何か

部分列（subsequence）とは、元の文字列から文字の順序を保ったまま0文字以上を取り除いて得られる文字列です。「部分文字列（substring）」とは異なり、連続している必要はありません。

例えば、文字列 "programming" に対して： - "pgm" → p…r…o…g…r…a…m と順に見つかるので 部分列である ✓ - "prg" → p, r は見つかるが、r より後に g があるので 部分列である ✓ - "gp" → g の後に p は現れないので 部分列でない ✗

素朴なアプローチで十分か

制約を確認します： - 本棚数 \(N \leq 100\) - 本の総数 \(\sum K_i \leq 5000\) - タイトルの総文字数 \(\leq 10^5\) - クエリ数 \(Q \leq 200\) - クエリの総文字数 \(\leq 10^5\)

各クエリについて全ての本のタイトルと部分列判定を行う素朴な方法でも、1回の判定は \(O(|S| + |T|)\) で済みます。最悪でも \(Q \times \sum K_i\) 回の判定ですが、各判定のコストはタイトル長とクエリ長の和であり、制約が十分小さいため問題ありません。

アルゴリズム

部分列判定（貪欲法）

文字列 \(T\) が文字列 \(S\) の部分列かどうかは、以下の貪欲法で \(O(|S|)\) で判定できます：

1. \(S\) を先頭から1文字ずつ走査する
2. \(T\) の「まだマッチしていない先頭の文字」と一致したら、\(T\) の次の文字に進む
3. \(T\) の全文字がマッチできたら部分列である

Pythonでは it = iter(s) としてイテレータを作り、all(c in it for c in t) と書くことで簡潔に実装できます。c in it はイテレータを現在位置から進めて c を探すため、順序が自動的に保たれます。

全体の流れ

1. 入力を読み込み、本棚ごとに本のタイトルをまとめる
2. 各クエリ \(T_j\) について：
   • 全本棚を走査し、その本棚の本のうち1冊でも \(T_j\) を部分列として含めば、その本棚をカウント
   • 1冊見つかった時点で次の本棚に移る（早期打ち切り）
3. カウント結果を出力する

計算量

• 時間計算量: \(O\Bigl(Q \times \sum_{i,j} |S_{i,j}| + Q \times \sum_j |T_j|\Bigr)\)
  • 各クエリで全タイトルを走査する最悪ケースを考えると、クエリあたり \(O(\text{タイトル総文字数} + |T|)\)
  • 制約下では \(200 \times 10^5 = 2 \times 10^7\) 程度で十分高速
• 空間計算量: \(O\Bigl(\sum_{i,j} |S_{i,j}| + \sum_j |T_j|\Bigr)\) （入力の保持分）

実装のポイント

• Pythonのイテレータを活用した部分列判定: all(c in it for c in t) は非常に簡潔かつ正確です。in 演算子がイテレータに対して使われると、現在位置から順に探索するため、部分列の順序条件が自然に満たされます。

• 早期打ち切り: ある本棚で1冊でもヒットしたら break して次の本棚に移ることで、無駄な判定を省けます。

• 入力の一括読み込み: sys.stdin.buffer.read() で入力を一度に読み込み、トークン分割することで、行ごとの入力処理より高速になります。

  ソースコード

import sys
from functools import lru_cache

def is_subsequence(t, s):
    """Check if t is a subsequence of s"""
    it = iter(s)
    return all(c in it for c in t)

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    
    N = int(tokens[idx]); idx += 1
    
    shelves = []
    for i in range(N):
        K = int(tokens[idx]); idx += 1
        books = []
        for j in range(K):
            books.append(tokens[idx]); idx += 1
        shelves.append(books)
    
    Q = int(tokens[idx]); idx += 1
    
    results = []
    for _ in range(Q):
        query = tokens[idx]; idx += 1
        count = 0
        for books in shelves:
            found = False
            for title in books:
                if is_subsequence(query, title):
                    found = True
                    break
            if found:
                count += 1
        results.append(count)
    
    print('\n'.join(map(str, results)))

if __name__ == '__main__':
    main()

---

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