概要

この問題は、与えられたクエリ文字列 \(T\) が、各本棚にある本のタイトル \(S\) の「部分列」となっているかを判定し、条件を満たす本が1冊以上存在する本棚の総数を求める問題です。

考察

まず、素朴な解法を考えると、各クエリに対して「全本棚 × その中の全タイトル」をチェックすることになります。 制約を確認すると、クエリ数 \(Q \le 200\)、本の総数 \(\sum K_i \le 5000\)、文字列の長さは最大 \(1000\) です。単純なループで部分列判定を行うと、最悪ケースで \(200 \times 5000 \times 1000 = 10^9\) 回程度の計算が必要になり、実行時間制限に間に合わない可能性があります。

そこで、以下の最適化を組み合わせることで効率化を図ります。

1. 本の重複排除と本棚の管理: 同じタイトルの本が複数の本棚に置かれている場合や、同じ本棚に複数ある場合があります。タイトルをキーとして「その本が含まれる本棚のリスト」を保持することで、判定回数を減らします。
2. 高速な判定スキップ（枝刈り）: あるタイトル \(S\) がクエリ \(T\) を部分列として含むためには、最低限以下の条件を満たす必要があります。
   • \(|S| \geq |T|\) （タイトルの長さがクエリ以上）
   • \(T\) に含まれるすべての文字が \(S\) にも含まれている 特に後者は、英小文字 26 種類をビットフラグ（ビットマスク）として管理することで、非常に高速に判定できます。
3. 本棚ごとの早期終了: あるクエリに対して、本棚 \(i\) がすでに「ヒット」したと分かれば、その本棚にある他の本を調べる必要はありません。また、すべての本棚がヒットした時点でそのクエリの処理を終了できます。

アルゴリズム

1. 前処理:
   • 全ての本のタイトルを走査し、ユニークなタイトルごとに以下の情報を記録します。
     • そのタイトルが含まれる本棚のインデックス（リスト）
     • タイトルの長さ
     • タイトルに含まれる文字の集合（ビットマスク：aなら1ビット目、bなら2ビット目を立てる）
2. クエリ処理: 各クエリ \(T\) に対して以下を行います。
   • クエリ \(T\) のビットマスクを作成します。
   • 各本棚がヒットしたかを管理する配列 shelf_hits（長さ \(N\)）を用意します。
   • ユニークなタイトルを順に調べます：
     1. そのタイトルが含まれるすべての本棚がすでに shelf_hits で True なら、判定をスキップします。
     2. タイトルの長さが \(T\) より短い、またはビットマスクで \(T\) にある文字が欠けているなら、判定をスキップします。
     3. 実際に部分列判定を行います（欲張り法）。
     4. 部分列であれば、そのタイトルを持つすべての本棚を shelf_hits で True に更新し、ヒットした本棚の数をカウントします。
     5. すべての本棚がヒット（カウント \(= N\)）したら、そのクエリのループを抜けます。
3. 部分列判定の効率化: Pythonでは iter() を利用した以下の書き方が非常に高速です。

   
   s_iter = iter(S)
   all(char in s_iter for char in T)
   

   これは \(T\) の各文字について、\(S\) のイテレータを順に進めながら文字を探す「欲張り法」を簡潔に記述したものです。

計算量

• 時間計算量: \(O(\sum |S_{i,j}| + Q \cdot (\text{UniqueBooks} \times \text{判定コスト}))\)
  • 前処理に全体の文字列長に比例する時間がかかります。
  • 各クエリでは、ビットマスク等による強力な枝刈りが行われるため、実際に重い部分列判定が行われる回数は大幅に削減されます。最悪ケースでも \(N\) や \(Q\) の値が小さいため、十分に間に合います。
• 空間計算量: \(O(\sum |S_{i,j}|)\)
  • ユニークなタイトルとその情報を保存するためのメモリが必要です。

実装のポイント

• ビットマスク: ord(char) - ord('a') を使って 0〜25 のビット位置を計算します。

• 早期終了: すでにその本が含まれる本棚がすべてチェック済みかどうかを判定することで、無駄な部分列判定を避けるのがポイントです。

• キャッシュ: 同じクエリが複数回投げられる可能性がある場合、クエリ結果を辞書などでキャッシュしておくとさらに安全です。

  ソースコード

import sys

def solve():
    # Fast input reading
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    ptr = 0
    N = int(input_data[ptr])
    ptr += 1
    
    # Pre-process unique books across all bookshelves
    # unique_books map: title -> [bitmask, length, [list of shelf indices]]
    unique_books = {}
    for i in range(N):
        K = int(input_data[ptr])
        ptr += 1
        
        # Use a set to handle duplicate titles within the same shelf
        shelf_titles = set()
        for _ in range(K):
            shelf_titles.add(input_data[ptr])
            ptr += 1
        
        for s in shelf_titles:
            if s not in unique_books:
                # Precompute bitmask of characters in the title
                m = 0
                for char in s:
                    m |= (1 << (ord(char) - 97))
                unique_books[s] = [m, len(s), [i]]
            else:
                # Append the current shelf index to the list of shelves containing this title
                unique_books[s][2].append(i)
    
    # Convert unique_books to a list for efficient iteration
    # Structure: (title, bitmask, length, shelf_indices)
    book_list = []
    for s, (m, length, indices) in unique_books.items():
        book_list.append((s, m, length, indices))
    
    # Sort books to improve the probability of hitting bookshelves early
    # Prioritize longer books and books appearing in more shelves
    book_list.sort(key=lambda x: (x[2], len(x[3])), reverse=True)
    
    # Read the number of queries
    if ptr >= len(input_data):
        return
    Q_count = int(input_data[ptr])
    ptr += 1
    
    query_cache = {}
    results = []
    
    for _ in range(Q_count):
        if ptr >= len(input_data):
            break
        T = input_data[ptr]
        ptr += 1
        
        # If the same query has been processed before, use the cached result
        if T in query_cache:
            results.append(query_cache[T])
            continue
        
        # Precompute bitmask for the query string
        mask_T = 0
        for char in T:
            mask_T |= (1 << (ord(char) - 97))
        
        len_T = len(T)
        shelf_hits = [False] * N
        hits_count = 0
        
        for s, mask_S, length_S, indices in book_list:
            # If all bookshelves are already hit, stop checking further books
            if hits_count == N:
                break
            
            # Check if this book belongs to any shelf that hasn't been hit yet
            already_hit = True
            for idx in indices:
                if not shelf_hits[idx]:
                    already_hit = False
                    break
            if already_hit:
                continue
            
            # Fast filtering using length and character existence (bitmask)
            if length_S < len_T or (mask_T & mask_S) != mask_T:
                continue
            
            # Efficient greedy subsequence check using iterators
            s_iter = iter(s)
            if all(c in s_iter for c in T):
                # If T is a subsequence, mark all shelves containing this book as hit
                for idx in indices:
                    if not shelf_hits[idx]:
                        shelf_hits[idx] = True
                        hits_count += 1
        
        res_str = str(hits_count)
        query_cache[T] = res_str
        results.append(res_str)
    
    # Fast output using sys.stdout.write
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。