概要

一次元上に配置された \(N\) 個のブースについて、距離 \(D\) 以内にあるブース同士の集客力の積（相乗効果）の総和を求める問題。

考察

この問題では、すべてのブースのペア \((i, j)\) について、距離 \(|X_i - X_j| \leq D\) であれば、\(S_i \times S_j\) を答えに加算する必要があります。

素朴な解法（TLEする理由）

素直な方法としては、すべてのペア \((i, j)\) （\(i < j\)）に対して、距離を確認し、条件を満たしていれば積を足すという方法があります。しかし、これは最大で

\[ \frac{N(N - 1)}{2} \approx 2 \times 10^{10} \]

回の計算が必要になり、制約 \(N \leq 2 \times 10^5\) では到底間に合いません（TLE）。

改善のアイデア

各ブース \(i\) について、それと距離 \(D\) 以内にあるブース \(j\)（\(j > i\)）の集合は、座標がソートされていれば連続した区間になります。つまり、ブースを座標順に並べておけば、「自分より右で距離 \(D\) 以内のブースたちの集客力の和」を高速に求めることで、そのブース \(i\) からの寄与をまとめて計算できます。

この「範囲和」を高速に求めるために、累積和を使います。また、あるブース \(i\) から距離 \(D\) 以内にある右側のブースのうち最も遠いものの位置を求めるには、二分探索（bisect）を使うのが効率的です。

アルゴリズム

1. 各ブースを座標 \(X_i\) の昇順にソートします。
2. 集客力 \(S_i\) の累積和配列 prefix_sum を事前に計算しておきます。
3. 各ブース \(i\) について：
   • 自身の座標を \(x_i\) とする。
   • \(x_j \leq x_i + D\) を満たす最大の \(j\) を二分探索で求める。
   • この範囲の集客力の和を累積和で求める。
   • \(S_i\) とその和を掛けたものを答えに加算する。

計算量

• 時間計算量: \(O(N \log N)\)
  
  • ソートに \(O(N \log N)\)
  • 各ブースに対して二分探索と累積和参照は \(O(\log N + 1) = O(\log N)\) で、全体で \(O(N \log N)\)
• 空間計算量: \(O(N)\)
  
  • 座標・集客力のリスト、および累積和配列に \(O(N)\) 必要

実装のポイント

• ブースは最初に座標でソートしておくこと。

• 累積和は範囲和を高速に求めるために必須。

• bisect.bisect_right(X, x_i + D) は「\(x_i + D\) を超える最初のインデックス」を返すので、実際に範囲内に入る最後の要素のインデックスは -1 する必要がある。

• 自分自身とはペアを作らないように、right > i の条件で判定する。

  ソースコード

import bisect

N, D = map(int, input().split())
XS = [tuple(map(int, input().split())) for _ in range(N)]

# 座標でソート
XS.sort()

X = [x for x, s in XS]
S = [s for x, s in XS]

# 累積和を前計算
prefix_sum = [0] * (N + 1)
for i in range(N):
    prefix_sum[i + 1] = prefix_sum[i] + S[i]

result = 0
for i in range(N):
    x_i, s_i = XS[i]
    # |X_j - X_i| <= D となる j を探す → X_j <= X_i + D
    right = bisect.bisect_right(X, x_i + D) - 1
    if right > i:
        # Σ_{j=i+1}^{right} S_j を計算
        sum_s = prefix_sum[right + 1] - prefix_sum[i + 1]
        result += s_i * sum_s

print(result)

この解説は qwen3-coder-480b によって生成されました。