概要

各実験の初期衝撃値 \(S\) に対して、「左から何番目までのドミノが壊れずに倒れるか」を高速に求める問題です。条件を変形して「\(S\) が満たすべき上限」を前計算し、各クエリを二分探索で答えます。

考察

重要な気づき：条件はすべて \(S\) との大小比較に直せる

ドミノ \(i\) に到達する衝撃値は - \(C_1 = S\) - \(C_{i} = S + (D_1 + D_2 + \cdots + D_{i-1})\)

ここで、\(i\) 番目が正常に倒れる条件は \(C_i \le P_i\) なので、 [ S + \sum_{k=1}^{i-1} D_k \le P_i ] [ S \le Pi - \sum{k=1}^{i-1} D_k ] となります。

つまり、「ドミノ \(i\) まで全部倒れる」ためには、\(1 \le k \le i\) のすべてについて [ S \le \left(Pk - \sum{t=1}^{k-1} Dt\right) ] が必要です。よって [ S \le \min{1 \le k \le i}\left(Pk - \sum{t=1}^{k-1} D_t\right) ] ならドミノ \(i\) まで到達できます。

素朴解が遅い理由

各クエリごとにドミノを 1 個ずつシミュレーションすると、最悪で \(O(N)\) かかります。クエリが \(Q\) 個あるので合計 \(O(NQ)\)、制約最大で \(2\times 10^5 \times 2\times 10^5\) となり到底間に合いません。

解決策：前計算 + 二分探索

上の式の「\(i\) まで倒れるための \(S\) の上限」を配列として前計算しておけば、各クエリは「条件を満たす最大の \(i\)」を二分探索で求められます。

アルゴリズム

1. 前計算（配列 \(B\) を作る）

\(i\) 番目の条件を [ T_i = Pi - \sum{k=1}^{i-1} Dk ] と置きます（$\sum{k=1}^{i-1} D_k\( は \)i$ の直前までの増分の累積和）。

さらに [ B_i = \min(T_1, T_2, \dots, T_i) ] と定義します。これは「ドミノ \(i\) まで全て倒すために必要な \(S\) の最大値（上限）」です。

このとき、ドミノ \(i\) まで倒れる条件は単に [ S \le B_i ] になります。

実装では左から順に累積和 pref = D_1 + ... + D_{i-1} を持ちながら - a = P_i - pref（これが \(T_i\)） - cur_min = min(cur_min, a)（これが \(B_i\)） として \(B\) を作ります。

また \(B_i\) は「最小値の累積」なので単調非増加（同じか減る）です。
よって \(S \le B_i\) を満たす \(i\) の集合は「先頭からの連続区間」になり、二分探索が可能です。

2. 各クエリの処理（二分探索）

• もし \(B_1 < S\)（コードでは B[0] < S）なら、ドミノ 1 すら倒れないので答えは \(0\)。
• そうでなければ、条件 \(B_i \ge S\) を満たす最大の \(i\) を二分探索で求め、答えはその \(i\)（1-indexed）です。

計算量

• 時間計算量: 前計算 \(O(N)\)、各クエリ二分探索 \(O(\log N)\) より全体で \(O(N + Q\log N)\)
• 空間計算量: \(B\) 配列などで \(O(N)\)

実装のポイント

• \(C_i\) や累積和は最大で \(S + \sum D\) になり得るため、Python なら問題ありませんが、他言語では 64-bit 整数（long long など）を使う必要があります。

• \(B\) は単調非増加なので、二分探索は「\(B[m] \ge S\) なら右へ進める（より大きい \(i\) を狙う）」形にします。

• 入力が大きいので、sys.stdin.buffer.read() でまとめて読み込むと高速です。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    Q = next(it)

    B = [0] * N
    pref = 0
    cur_min = 10**30  # sufficiently large
    for i in range(N):
        P = next(it)
        D = next(it)
        a = P - pref
        if a < cur_min:
            cur_min = a
        B[i] = cur_min
        pref += D

    out_lines = []
    for _ in range(Q):
        S = next(it)
        if B[0] < S:
            out_lines.append("0")
            continue
        l, r = 0, N - 1
        while l < r:
            m = (l + r + 1) // 2
            if B[m] >= S:
                l = m
            else:
                r = m - 1
        out_lines.append(str(l + 1))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。