【AtCoder】ABC 444 E - Sparse Range

2026-02-10

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/緑Diff AtCoder/NoviSteps/未分類 AtCoder/尺取り法 AtCoder/データ構造/set AtCoder/二分探索競技プログラミング

E - Sparse Range

E - Sparse Range

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1107 / NoviSteps: ??? / 配点: 450 点

問題概要

長さ $N$ の整数列 $A$ と正整数 $D$ が与えられるので、以下の条件をともに満たす整数の組 $(L,R)$ の個数を求めよ。

$1 \leq L \leq R \leq N$
$L \leq i < j \leq R$ を満たす全ての整数の組 $(i,j)$ について、 $|A_i-A_j|\geq D$ である

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 2 \times 10^5$
入力される値は全て整数

考察

ある区間 $[L, R]$ が条件を満たすとき、その部分区間( $[L+1, R]$ など)も条件を満たす。

したがって、尺取り法によって、 $L$ を固定したときの条件を満たす最大の $R$ を求めることができる。

ここで、 $[L, R-1]$ が条件を満たしているとして、右端を $R$ に進めるときに、条件を満たすかどうかを判定する必要がある。

愚直にやるなら、新たな要素 $A_R$ を $A_L, A_{L+1}, \cdots, A_{R-1}$ と全て比較して、 $|A_i - A_R| \geq D$ であるかを確認すればよいが、これは $O(N)$ の計算量がかかってしまう。

しかしよく考えると、 $A$ がソートされていれば、追加する $A_R$ に隣接する値のみを確認すればよいことが分かる。

理由 (クリックで展開)

昇順ソートされた数列 $\{\cdots A, B, C, E\cdots\}$ について、新たな数 $X \: (B < X < C)$ を追加するとする。

このとき、 $X - B \geq D$ ならば、当然 $X - A \geq D$ も成り立つ。

右側についても同様で、 $C - X \geq D$ ならば $E - X \geq D$ も成り立つ。

したがって、 $[L, R-1]$ の要素をソートされた状態で管理し、 $A_R$ をキーとして二分探索を行い、以下の2つの条件を満たすかを確認すればよい。

$A_R$ 以上の最小値 $m_R$ について $m_R - A_R \geq D$ である。
$A_R$ 未満の最大値 $m_L$ について $A_R - m_L \geq D$ である。

これはsetとそれに備わっているlower_boundメソッドを用いれば簡単に実装でき、計算量は $O(N \log N)$ となる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.using ll = long long;
7. 
8.// ======================================== //
9. 
10.int main()
11.{
12.    int N;
13.    ll D;
14.    cin >> N >> D;
15.    vector<ll> A(N);
16.    rep(i, 0, N) cin >> A[i];
17. 
18.    ll ans = 0;
19.    set<ll> st;
20.    int R = 0;
21.    rep(L, 0, N)
22.    {
23.        while (R < N)
24.        {
25.            auto itr = st.lower_bound(A[R]);
26. 
27.            if (itr != st.end() && abs(*itr - A[R]) < D)
28.                break;
29.            if (itr != st.begin() && abs(*prev(itr) - A[R]) < D)
30.                break;
31. 
32.            st.insert(A[R]);
33.            R++;
34.        }
35. 
36.        ans += R - L;
37. 
38.        st.erase(A[L]);
39.    }
40. 
41.    cout << ans << endl;
42. 
43.    return 0;
44.}

https://atcoder.jp/contests/abc444/submissions/73090414

実装時間: 20分

コメント

尺取り法のいい練習問題だと思う。