概要

各ドミノが正常に倒れるための初期衝撃値の条件を整理し、前計算と二分探索を組み合わせることで、各実験（クエリ）に対する答えを高速に求める問題です。

考察

まず、素朴な方法を考えてみましょう。各クエリの初期衝撃値 \(S\) に対して、ドミノ \(1\) から順番に衝撃値を計算してシミュレーションを行うと、1回のクエリあたり最大で \(O(N)\) の時間がかかります。クエリは \(Q\) 回あるため、全体の時間計算量は \(O(NQ)\) となり、制約（\(N, Q \le 2 \times 10^5\)）のもとでは実行時間制限（TLE）に引っかかってしまいます。

そこで、「ドミノ \(i\) が正常に倒れるためには、初期衝撃値 \(S\) がどの範囲に収まっていればよいか」 を数式で整理してみます。

ドミノ \(i\) に到達したときの衝撃値 \(C_i\) は、初期衝撃値 \(S\) にそれまでの衝撃増分を足したものになります。 \(C_i = S + D_1 + D_2 + \dots + D_{i-1}\)

ドミノ \(i\) が正常に倒れる条件は \(C_i \le P_i\) です。これに上の式を代入して \(S\) について解くと、以下のようになります。 \(S + D_1 + D_2 + \dots + D_{i-1} \le P_i\) \(S \le P_i - (D_1 + D_2 + \dots + D_{i-1})\)

ここで、右辺を \(M_i\) と置きます。すなわち、\(M_i = P_i - \sum_{k=1}^{i-1} D_k\) です。 ドミノ \(i\) が正常に倒れるためには、\(S \le M_i\) である必要があります。

さらに、「ドミノ \(1\) からドミノ \(i\) まで すべて 正常に倒れる」ための条件は、ドミノ \(1, 2, \dots, i\) のすべてで条件を満たすこと、つまり \(S \le M_1, S \le M_2, \dots, S \le M_i\) をすべて満たすことです。 これは言い換えると、「\(S\) が \(M_1 \sim M_i\) の最小値以下であること」 となります。

そこで、新しい配列 \(L\) を用意し、\(L_i = \min(M_1, M_2, \dots, M_i)\) と定義します。 すると、ドミノ \(i\) まで正常に倒れる条件は単に \(S \le L_i\) と表すことができます。

この配列 \(L\) には「要素が進むにつれて値が単調に減少する（または維持される）」という性質（\(L_1 \ge L_2 \ge \dots \ge L_N\)）があります。この単調性のおかげで、「\(S \le L_i\) を満たす最大の \(i\)」を求める際に二分探索が使えるようになり、1回のクエリを \(O(\log N)\) で処理できるようになります。

アルゴリズム

1. 前計算（配列 \(L\) の構築）:
   • 衝撃増分の累積和を管理する変数 sum_D を \(0\) で初期化します。
   • \(L_1 = P_1\) とします。
   • \(i = 2, 3, \dots, N\) について順番に以下を計算します：
     • sum_D に \(D_{i-1}\) を足します。
     • \(M_i = P_i - \text{sum\_D}\) を計算します。
     • \(L_i = \min(L_{i-1}, M_i)\) を計算し、配列に記録します。
2. クエリ処理（二分探索）:
   • 各実験の初期衝撃値 \(S\) について、条件 \(S \le L_i\) を満たす最大の \(i\) を二分探索で探します。
   • ok = 0（確実に条件を満たす、または \(0\) 個倒れる状態）、ng = N + 1（確実に条件を満たさない状態）として、その中間点 mid を調べながら境界を絞り込んでいきます。
   • 最終的な ok の値が、正常に倒れた最後のドミノの番号になります。

計算量

• 時間計算量: \(O(N + Q \log N)\)
  • 配列 \(L\) の前計算に \(O(N)\) かかります。
  • 1回のクエリに対して二分探索で \(O(\log N)\) かかるため、\(Q\) 回のクエリで \(O(Q \log N)\) かかります。
  • 全体として非常に高速であり、制限時間内に余裕で間に合います。
• 空間計算量: \(O(N + Q)\)
  • ドミノの情報や配列 \(L\) を保持するために \(O(N)\) のメモリを使用します。
  • 出力結果を保持するために \(O(Q)\) のメモリを使用します。

実装のポイント

• 高速な入出力: 制約が大きく入力データが多いため、Pythonでは input() をループで回すのではなく、sys.stdin.read().split() で一括して読み込み、出力も sys.stdout.write() でまとめて行うことで実行時間を大幅に短縮できます。

• 累積和の省メモリ化: \(D_i\) の累積和を専用の配列で持つ必要はなく、ループ内で変数 sum_D に足し込んでいくことでメモリと実装をシンプルにしています。

• 二分探索の境界条件: 「ドミノ \(1\) すら倒れない場合」は答えが \(0\) になります。二分探索の初期値を ok = 0 としておくことで、条件を満たす \(i\) が一つもない場合でも自然に 0 が出力される美しい設計になっています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    P = [0] * (N + 1)
    D = [0] * (N + 1)
    
    idx = 2
    for i in range(1, N + 1):
        P[i] = int(input_data[idx])
        D[i] = int(input_data[idx+1])
        idx += 2
        
    S = [int(x) for x in input_data[idx:]]
    
    L = [0] * (N + 1)
    L[1] = P[1]
    sum_D = 0
    
    for i in range(2, N + 1):
        sum_D += D[i - 1]
        M_i = P[i] - sum_D
        L[i] = L[i - 1] if L[i - 1] < M_i else M_i
        
    out = []
    for s in S:
        ok = 0
        ng = N + 1
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if s <= L[mid]:
                ok = mid
            else:
                ng = mid
        out.append(str(ok))
        
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。