概要

ブースの座標と集客力が与えられ、座標の差が\(D\)以下のブースペアについて集客力の積の総和を求める問題です。

考察

素朴なアプローチでは、すべてのブースのペア\((i, j)\)について\(|X_i - X_j| \leq D\)かを判定し、条件を満たすペアの\(S_i \times S_j\)を足し上げる方法が考えられます。しかし、この方法の時間計算量は\(O(N^2)\)であり、\(N\)が最大\(2 \times 10^5\)と大きいため、実行時間制限に間に合いません。

効率的に解くためには、ブースを座標順にソートし、しゃくとり法を用いて条件を満たす範囲内のブースを管理しながら計算する方法が有効です。これにより、各ブースに対して条件を満たす左端のブースを高速に見つけることができます。

アルゴリズム

1. ブースを座標\(X_i\)の昇順にソートします。
2. 左端のインデックスleftを0に初期化し、累積和prefix_sumを0で初期化します。
3. 右端のインデックスrightを0から\(N-1\)まで順に動かします：
   • 現在のブースpoints[right]と左端のブースpoints[left]の座標の差が\(D\)より大きい間、leftを進めながらprefix_sumから対応する集客力を引きます。
   • 現在のブースの集客力と、現在の範囲内にあるブースの集客力の合計（prefix_sum）の積を総和totalに加算します。
   • 現在のブースの集客力をprefix_sumに加算します。

この方法では、各ブースjについて、条件を満たすブースi（\(i < j\)かつ\(X_j - X_i \leq D\)）の集客力の合計を効率的に求め、\(S_j \times (\sum S_i)\)を計算しています。

計算量

• 時間計算量: \(O(N \log N)\)（ソートに\(O(N \log N)\)、しゃくとり法の処理に\(O(N)\)）
• 空間計算量: \(O(N)\)（ブースの情報を格納するための配列）

実装のポイント

• ブースを座標でソートする必要があります。

• しゃくとり法では、左端のインデックスleftを条件に応じて調整しながら、現在の範囲内の集客力の合計を管理します。

• 累積和prefix_sumを更新するタイミングに注意します（現在のブースを加算する前に積の計算を行う）。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    D = int(data[1])
    points = []
    index = 2
    for i in range(n):
        x = int(data[index])
        s = int(data[index+1])
        index += 2
        points.append((x, s))
    
    points.sort()
    total = 0
    prefix_sum = 0
    left = 0
    for right in range(n):
        while points[right][0] - points[left][0] > D:
            prefix_sum -= points[left][1]
            left += 1
        total += points[right][1] * prefix_sum
        prefix_sum += points[right][1]
    
    print(total)

if __name__ == "__main__":
    main()

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