問題文

Petyaは点が大好きです。彼の母親は彼に数直線OX上のn個の点を与えました。Petyaは、最も遠い2点間の距離がd以下となるような3つの異なる点を選ぶ方法がいくつあるか知りたいです。3つの点の順序は関係ありません。

入出力形式

入力

最初の行には2つの整数n (1 ≤ n ≤ 10⁵) と d (1 ≤ d ≤ 10⁹) が含まれます。次の行には、Petyaが持つ点のx座標を表すn個の整数x₁, x₂, ..., x_nが含まれています。座標の絶対値は10⁹以下です。座標は厳密に昇順で与えられます。

出力

3つの点を選び、最も遠い2点間の距離がd以下となるような組み合わせの数を表す整数を出力してください。

解法

1. 暴力解法 (O(n³))

3つの点をすべて列挙し、条件を満たす場合にカウントを増やします。これはnが大きいために時間がかかりすぎます。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, d;
    cin >> n >> d;
    vector<ll> coordinates(n);
    for (ll i = 0; i < n; ++i) {
        cin >> coordinates[i];
    }

    ll total_ways = 0;
    for (ll i = 0; i < n; ++i) {
        for (ll j = i + 1; j < n; ++j) {
            for (ll k = j + 1; k < n; ++k) {
                if (coordinates[k] - coordinates[i] <= d) {
                    total_ways++;
                }
            }
        }
    }

    cout << total_ways << "
";
    return 0;
}

このコードは、大きな入力に対して時間切れ (TLE) になります。

2. 最適解法 (O(n log n))

この問題を解くより効率的な方法は、二分探索と組み合わせ数学を組み合わせることです。

• 最も左側の点を固定します。
• その点から距離d以内にある最も右側の点を見つけます。これは、upper_bound関数を使用して高速に行うことができます。
• 最も左側の点と最も右側の点が決まると、その間の点からさらに2つを選ぶ方法の数を計算できます。これは、C(k, 2) の組み合わせの数です。ここで、kはその間にある点の数です。
• このプロセスをすべての点に対して繰り返します。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll combination(ll x) {
    return x * (x - 1) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, d;
    cin >> n >> d;
    vector<ll> coordinates(n);
    for (ll i = 0; i < n; ++i) {
        cin >> coordinates[i];
    }

    ll result = 0;
    for (ll left_index = 0; left_index < n; ++left_index) {
        ll right_limit = coordinates[left_index] + d;
        ll right_index = upper_bound(coordinates.begin(), coordinates.end(), right_limit) - coordinates.begin() - 1;
        ll num_points_in_range = right_index - left_index;
        if (num_points_in_range >= 2) {
            result += combination(num_points_in_range);
        }
    }

    cout << result << "
";
    return 0;
}