概要

各本棚に複数の本があり、検索クエリが本のタイトルの部分列として含まれるかどうかを判定し、条件を満たす本を1冊以上持つ本棚の数を求める問題です。

考察

問題の核心は、与えられたクエリ文字列が各本のタイトルの部分列であるかを効率的に判定することです。部分列判定は、タイトルの文字列を先頭から順に走査しながらクエリの各文字が順番に出現するか確認することで行えます。各クエリに対して全ての本棚とその中の全ての本をチェックする必要がありますが、制約条件から総当たりでも十分処理可能です。

アルゴリズム

1. 部分列判定関数 is_subsequence を実装します
   • パターン（クエリ）の各文字が、テキスト（タイトル）中で順番に出現するかを判定
   • イテレータを使用してテキストを順に走査し、パターンの各文字が次々に見つかるか確認
2. 各クエリに対して以下の処理を行います
   • 各本棚について、その本棚内の本を1冊ずつチェック
   • 少なくとも1冊の本のタイトルがクエリを部分列として含んでいれば、その本棚をカウント
   • 条件を満たす本棚の数を出力

計算量

• 時間計算量: \(O(N \cdot K \cdot L \cdot M)\)
  • \(N\): 本棚の数（最大100）
  • \(K\): 1本棚あたりの平均本数
  • \(L\): タイトルの平均長（最大1000）
  • \(M\): クエリの平均長（最大1000）
  • 全体の文字列総長の制約（\(10^5\)）により実用的な速度で動作
• 空間計算量: \(O(\sum |S_{i,j}| + \sum |T_j|)\)
  • 入力データを保存するためのメモリ

実装のポイント

• 部分列判定ではイテレータを使用することで、効率的に文字のマッチングを行えます

• 本棚ごとに内側のループで早期breakを行うことで、1冊でも条件を満たす本が見つかったらすぐに次の本棚に進む最適化をしています

• 入力データの読み込みでは、行単位で処理しsplitで分割することで効率的にデータを取得しています

  ソースコード

import sys

def is_subsequence(pattern, text):
    it = iter(text)
    return all(c in it for c in pattern)

def main():
    data = sys.stdin.read().splitlines()
    idx = 0
    N = int(data[idx]); idx += 1
    shelves = []
    for _ in range(N):
        parts = data[idx].split(); idx += 1
        k = int(parts[0])
        titles = parts[1:1+k]
        shelves.append(titles)
    
    Q = int(data[idx]); idx += 1
    queries = []
    for _ in range(Q):
        queries.append(data[idx].strip()); idx += 1
    
    for query in queries:
        count = 0
        for shelf in shelves:
            found = False
            for title in shelf:
                if is_subsequence(query, title):
                    found = True
                    break
            if found:
                count += 1
        print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。