概要

一列に並んだドミノに初期衝撃値 \(S\) でボールを当て、衝撃が増加しながら伝わっていく中で、何番目のドミノまで正常に倒れるかを各クエリについて高速に求める問題です。

考察

衝撃値の累積に注目する

ドミノ \(i\)（1-indexed）に到達する衝撃値 \(C_i\) を整理します。

• \(C_1 = S\)
• \(C_2 = S + D_1\)
• \(C_3 = S + D_1 + D_2\)
• 一般に \(C_i = S + \sum_{k=1}^{i-1} D_k\)

ここで \(\text{prefD}[i] = D_1 + D_2 + \cdots + D_{i-1}\)（\(\text{prefD}[1] = 0\)）と定義すると、\(C_i = S + \text{prefD}[i]\) です。

正常に倒れる条件の変換

ドミノ \(i\) が正常に倒れる条件は \(C_i \leq P_i\)、すなわち：

\[S + \text{prefD}[i] \leq P_i \iff S \leq P_i - \text{prefD}[i]\]

ここで \(\text{threshold}[i] = P_i - \text{prefD}[i]\) と定義します。すると、ドミノ \(i\) が正常に倒れるための \(S\) の上限が \(\text{threshold}[i]\) です。

「最後に正常に倒れたドミノ」を求める

重要な点は、ドミノ \(k\) が粉砕されると、それ以降のドミノには衝撃が伝わらないことです。したがって、ドミノ \(1, 2, \ldots, i\) がすべて正常に倒れる条件は：

\[S \leq \text{threshold}[1] \text{ かつ } S \leq \text{threshold}[2] \text{ かつ } \cdots \text{ かつ } S \leq \text{threshold}[i]\]

これは \(S \leq \min(\text{threshold}[1], \ldots, \text{threshold}[i])\) と同値です。

そこで累積最小値 \(\text{minThresh}[i] = \min(\text{threshold}[1], \ldots, \text{threshold}[i])\) を前計算します。\(\text{minThresh}\) は定義上単調非増加です。

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

各クエリごとにドミノを1つずつシミュレーションすると \(O(N)\) かかり、全体で \(O(NQ)\) となり、\(N, Q\) がともに \(2 \times 10^5\) のとき TLE になります。

二分探索による高速化

\(\text{minThresh}\) が単調非増加であることを利用すると、与えられた \(S\) に対して「\(S \leq \text{minThresh}[i]\) を満たす最大の \(i\)」を二分探索で \(O(\log N)\) で求められます。

アルゴリズム

1. 前計算：\(D\) の累積和 \(\text{prefD}[i]\) を計算する。
2. 閾値の計算：\(\text{threshold}[i] = P_i - \text{prefD}[i]\) を計算する。
3. 累積最小値：\(\text{minThresh}[i] = \min(\text{minThresh}[i-1], \text{threshold}[i])\) を計算する。
4. 各クエリ処理：\(\text{minThresh}\) は単調非増加なので、\(-\text{minThresh}\) は単調非減少。Python の bisect_right を用いて、\(-\text{minThresh}[i] \leq -S\) となる要素数を求めれば、それが正常に倒れたドミノの個数（= 答え）になる。

具体例：\(N=3\), \(P = [5, 3, 10]\), \(D = [2, 1, 0]\), \(S = 2\) の場合

• \(\text{prefD} = [0, 2, 3]\), \(\text{threshold} = [5, 1, 7]\), \(\text{minThresh} = [5, 1, 1]\)
• \(S=2\)：\(\text{minThresh}[1]=5 \geq 2\) ✓、\(\text{minThresh}[2]=1 < 2\) ✗ → 答えは \(1\)

計算量

• 時間計算量: \(O(N + Q \log N)\)（前計算に \(O(N)\)、各クエリに二分探索 \(O(\log N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• \(\text{threshold}[i] = P_i - \text{prefD}[i]\) は負の値になりうるので注意。負でも問題なく動作する。

• Python の bisect モジュールは単調非減少列にしか使えないため、\(\text{minThresh}\) を符号反転して非減少列に変換してから bisect_right を適用する。

• 衝撃値は最大 \(10^9 + (2 \times 10^5) \times 10^9\) 程度になりうるが、Python は多倍長整数なのでオーバーフローの心配は不要。C++ などでは long long を使う必要がある。

  ソースコード

import sys
import bisect

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    P = [0] * N
    D = [0] * N
    for i in range(N):
        P[i] = int(input_data[idx]); idx += 1
        D[i] = int(input_data[idx]); idx += 1
    
    # For domino i, the cumulative衝撃 at domino i is S + sum(D[0..i-1])
    # Let prefix_D[i] = D[0] + D[1] + ... + D[i-1] (prefix_D[0] = 0)
    # So C_i = S + prefix_D[i]
    # Domino i is okay if C_i <= P[i], i.e., S <= P[i] - prefix_D[i]
    # 
    # Define threshold[i] = P[i] - prefix_D[i]
    # Domino i falls normally iff S <= threshold[i]
    # 
    # We need the last domino that falls normally, i.e., the largest i such that
    # all dominoes 1..i have S <= threshold[k] for k=1..i.
    # Because if domino k is crushed (S > threshold[k]), then domino k+1 never receives impact.
    # So the answer is: the largest i such that S <= min(threshold[1], threshold[2], ..., threshold[i])
    # Or equivalently, the largest i such that S <= min_threshold_prefix[i]
    # where min_threshold_prefix[i] = min(threshold[0], threshold[1], ..., threshold[i])
    # (using 0-indexed)
    
    # Compute prefix sums of D
    prefix_D = [0] * (N + 1)
    for i in range(N):
        prefix_D[i + 1] = prefix_D[i] + D[i]
    
    # threshold[i] = P[i] - prefix_D[i] for i in 0..N-1
    # min_threshold_prefix[i] = min(threshold[0..i])
    min_thresh = [0] * N
    min_thresh[0] = P[0]  # prefix_D[0] = 0
    for i in range(1, N):
        thresh_i = P[i] - prefix_D[i]
        min_thresh[i] = min(min_thresh[i - 1], thresh_i)
    
    # min_thresh is non-increasing (since we take running minimum)
    # For a given S, we need the largest i (0-indexed) such that S <= min_thresh[i]
    # Since min_thresh is non-increasing, we can binary search.
    # Answer (1-indexed) = number of dominoes that fall = (largest 0-indexed i with S <= min_thresh[i]) + 1
    # If S > min_thresh[0] (= P[0]), answer is 0.
    # If S <= min_thresh[N-1], answer is N.
    
    # min_thresh is non-increasing, so we want the rightmost position where min_thresh[i] >= S
    # Equivalently, using bisect on the negated array (which would be non-decreasing)
    # Or we can use bisect_left on -min_thresh for -S
    
    # Let's create neg_min_thresh which is non-decreasing
    neg_min_thresh = [-min_thresh[i] for i in range(N)]
    # neg_min_thresh is non-decreasing
    # We want largest i with min_thresh[i] >= S, i.e., -min_thresh[i] <= -S
    # Number of elements with -min_thresh[i] <= -S is bisect_right(neg_min_thresh, -S)
    # That gives us the count, and the answer is that count (since 0-indexed count = 1-indexed last index)
    
    out = []
    for _ in range(Q):
        S = int(input_data[idx]); idx += 1
        # bisect_right finds first index where neg_min_thresh[i] > -S
        # All indices before that have neg_min_thresh[i] <= -S, meaning min_thresh[i] >= S
        ans = bisect.bisect_right(neg_min_thresh, -S)
        out.append(str(ans))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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