概要

書棚の \(N\) 冊の本に対して、指定された区間 \([L, R]\) 内にタイトルが \(T\) と一致する本が何冊あるかを、\(Q\) 個の問い合わせそれぞれについて高速に求める問題です。

考察

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

最も単純な方法は、各問い合わせごとに \(L\) 番目から \(R\) 番目までの本を一つずつ見て、タイトルが \(T\) と一致するか確認することです。しかし、この方法では1回の問い合わせに最大 \(O(N)\) かかり、全体で \(O(NQ)\) となります。\(N, Q\) がともに最大 \(10^5\) なので、最悪 \(10^{10}\) 回の操作となり TLE（時間超過） になります。

重要な気づき

問い合わせの本質は「あるタイトル \(T\) が、位置 \(L\) 以上 \(R\) 以下に何個存在するか」です。

これは、タイトルごとにそのタイトルが出現する位置を昇順に記録しておけば、二分探索（Binary Search） で高速に答えられます。

例えば、タイトル "abc" が位置 \([2, 5, 8, 12]\) に出現しているとき、区間 \([3, 10]\) に含まれる個数を知りたければ：

• \(3\) 以上の最初の位置 → \(5\)（左からのインデックス 1）
• \(10\) 以下の最後の位置 → \(8\)（左からのインデックス 2）
• 個数 = \(2 - 1 + 1 = 2\) 個（インデックス 1, 2 の要素）

Pythonの bisect_left と bisect_right を使えば、これを \(O(\log N)\) で計算できます。

アルゴリズム

1. 前処理: 辞書（ハッシュマップ）を用意し、各タイトルをキーとして、そのタイトルが出現する位置（1-indexed）のリストを昇順で格納する。本は左から順に読むので、自然に昇順になる。

2. 各問い合わせへの回答: タイトル \(T_j\) に対応する位置リストを取得し、二分探索で区間 \([L_j, R_j]\) 内に含まれる要素数を求める。

   • bisect_left(pos_list, L) で \(L\) 以上の要素が始まるインデックスを取得
   • bisect_right(pos_list, R) で \(R\) より大きい要素が始まるインデックスを取得
   • 差を取れば区間内の個数が得られる

3. タイトル \(T_j\) が辞書に存在しない場合、答えは \(0\)。

計算量

• 時間計算量: \(O(N + Q \log N)\)
  • 前処理で \(N\) 冊の本を辞書に登録: \(O(N)\)
  • 各問い合わせで二分探索を2回行う: \(O(\log N)\) × \(Q\) 回
• 空間計算量: \(O(N)\)
  • 全タイトルの出現位置を合計 \(N\) 個保持する

実装のポイント

• 入力の高速化: sys.stdin.buffer.read() で一括読み込みし、split() でトークンに分割することで、Pythonでも高速にI/O処理ができる。

• 出力の高速化: 各問い合わせの結果をリストに溜めておき、最後に '\n'.join(out) で一括出力する。print を \(Q\) 回呼ぶより大幅に速い。

• 1-indexed の扱い: 本の位置は問題文で1始まりなので、位置リストにも1-indexedで格納し、問い合わせの \(L, R\) とそのまま比較できるようにしている。

• defaultdict(list): タイトルが初めて登場したときに自動的に空リストが作られるため、キーの存在チェックを省略でき、コードが簡潔になる。

  ソースコード

import sys
from collections import defaultdict
from bisect import bisect_left, bisect_right

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    Q = int(tokens[idx]); idx += 1
    
    # For each title, store sorted list of positions (1-indexed)
    title_positions = defaultdict(list)
    for i in range(1, N + 1):
        s = tokens[idx]; idx += 1
        title_positions[s].append(i)
    
    out = []
    for _ in range(Q):
        L = int(tokens[idx]); idx += 1
        R = int(tokens[idx]); idx += 1
        T = tokens[idx]; idx += 1
        
        if T in title_positions:
            pos_list = title_positions[T]
            count = bisect_right(pos_list, R) - bisect_left(pos_list, L)
            out.append(str(count))
        else:
            out.append('0')
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

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