概要

ドミノ倒しの過程で各ドミノが正常に倒れるかどうかを判定し、Q回の実験に対して正常に倒れた最後のドミノの番号を求める問題です。

考察

各ドミノiに到達する衝撃値は \(C_i = S + \sum_{k=1}^{i-1} D_k\) と表せます。ドミノiが正常に倒れる条件は \(C_i \leq P_i\) すなわち \(S \leq P_i - \sum_{k=1}^{i-1} D_k\) です。ここで \(T_i = P_i - \sum_{k=1}^{i-1} D_k\) と定義すると、各実験ではSが最初に \(T_i\) を超える位置を探す問題に帰着します。

素朴なアプローチでは各実験ごとに全ドミノをチェックすると \(O(NQ)\) となり、制約条件（\(N, Q \leq 2 \times 10^5\)）では間に合いません。そこで、二分探索とセグメント木を組み合わせることで効率的に解きます。

アルゴリズム

1. 前処理として累積和 \(\text{cum\_d}[i] = \sum_{k=1}^{i-1} D_k\) を計算
2. 各ドミノiについて閾値 \(T_i = P_i - \text{cum\_d}[i]\) を計算
3. セグメント木（最小値クエリ）を構築し、区間 \([0, r]\) の最小値を高速に取得可能にする
4. 各実験S_jについて二分探索を実行：
   • 区間 \([0, mid]\) の最小値 \(\text{min\_val}\) をセグメント木で取得
   • \(S_j \leq \text{min\_val}\) ならばmidまでは正常に倒れるので探索範囲を右に伸ばす
   • そうでなければ左に縮める
5. 二分探索で得られた位置lowが最初に正常に倒れないドミノの位置（0-indexed）となる

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 前処理（累積和・セグメント木構築）: \(O(N)\)
  • 各実験（二分探索＋セグメント木クエリ）: \(O(\log N)\) × \(Q\)
• 空間計算量: \(O(N)\)

実装のポイント

• 累積和の計算ではインデックスに注意（cum_d[0] = 0, cum_d[1] = D₁, …）

• セグメント木は最小値を求めるように実装

• 二分探索の終了条件に注意（lowが最初に失敗する位置を示す）

• 0-indexedと1-indexedの変換に注意（出力時は1-indexedで、low=0の場合は特別扱い）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); Q = int(next(it))
    dominoes = []
    for i in range(N):
        p = int(next(it)); d = int(next(it))
        dominoes.append((p, d))
    
    S_list = [int(next(it)) for _ in range(Q)]
    
    # 累積和の配列を作成: cum_d[i] = D_1 + D_2 + ... + D_{i-1} (i>=1)
    cum_d = [0] * (N+1)
    for i in range(1, N):
        cum_d[i] = cum_d[i-1] + dominoes[i-1][1]
    
    # 各ドミノiに到達する衝撃値の式: C_i = S + (D_1 + D_2 + ... + D_{i-1}) = S + cum_d[i]
    # 正常に倒れる条件: S + cum_d[i] <= P_i
    # つまり、S <= P_i - cum_d[i]
    
    # 各ドミノiについて、閾値 T_i = P_i - cum_d[i] を計算
    T = [0] * N
    for i in range(N):
        T[i] = dominoes[i][0] - cum_d[i]
    
    # セグメント木（最小値）を構築
    size = 1
    while size < N:
        size *= 2
    seg = [10**18] * (2 * size)
    
    for i in range(N):
        seg[size + i] = T[i]
    for i in range(size-1, 0, -1):
        seg[i] = min(seg[2*i], seg[2*i+1])
    
    def query(l, r):
        l += size
        r += size
        res = 10**18
        while l < r:
            if l % 2 == 1:
                res = min(res, seg[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = min(res, seg[r])
            l //= 2
            r //= 2
        return res
    
    # 二分探索: 最初にS > T_iとなるiを探す
    # 正常に倒れるのは、i=0からi=k-1まで（0-indexedでk-1番目）
    # つまり、答えはk（1-indexed）になるが、k=0の場合は0を出力
    for s in S_list:
        low, high = 0, N
        while low < high:
            mid = (low + high) // 2
            min_val = query(0, mid+1)
            if s <= min_val:
                low = mid + 1
            else:
                high = mid
        # lowが最初に正常に倒れないドミノのindex（0-indexed）
        # 正常に倒れる最後のドミノはlow-1（0-indexed）なので、1-indexedではlow
        # ただし、low=0の場合はドミノ1も倒せないので0
        if low == 0:
            print(0)
        else:
            print(low)

if __name__ == "__main__":
    main()

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