【AtCoder】ABC 430 D - Neighbor Distance

2025-11-32025-11-4

実行時間制限: 4 sec / メモリ制限: 1024 MiB / Difficulty: 982 / NoviSteps: 1Q / 配点: 400 点

問題概要

数直線があり、最初は座標 $0$ に人 $0$ がひとりで立っている。

これから、人 $1,2,\ldots,N$ がこの順に到着し、人 $i$ は数直線上の座標 $X_i$ に立つ。

人が到着するたびに、以下の問いに答えよ。

現在数直線に人 $0,1,\dots,r$ の $r+1$ 人が立っているとする。
このとき、 $d_i$ を「人 $i$ に最も近い別の人までの距離」と定義する。
この $d$ の総和 $\sum_{i=0}^r d_i$ を求めよ。

制約

入力は全て整数
$1 \le N \le 5 \times 10^5$
$1 \le X_i \le 10^9$
$X_i$ は相異なる。

考察

サンプルケース 1 を例に、確認の到着時の $D_i = \sum d_i$ の変化を見てみる。

\begin{align*} D_1 & = |0 - 5| & & & + |5 - 0| & & = 10 \\ D_2 & = |0 - 2| & + |2 - 0| & & + |5 - 2| & & = 7 \\ D_3 & = |0 - 2| & + |2 - 0| & & + |5 - 7| & + |7 - 5| & = 8 \\ D_4 & = |0 - 2| & + |2 - 0| & + |4 - 5| & + |5 - 4| & + |7 - 5| & = 8 \\ \cdots \end{align*}

これを見ると、新たに人が到着したときに $d_i$ の値が影響を受けるのは、新たに到着した人と(もし存在すれば)その左右の人だけであることが分かる。

したがって、 $D_i$ の差分としては、新たに到着した人とその左右の人に関する $d_i$ の和の差分だけを考えればよい。

具体的には、新たに到着した人の左隣の人の座標を $l$ 、右隣の人を $r$ として、新たな人の到着によって $d_l \rightarrow d_l^{\prime}, d_r \rightarrow d_r^{\prime}$ と変化したとき、 $D_i$ の差分 $\Delta D$ は次のように表せる。

\Delta D = (d_l^{\prime} + d_{X_i} + d_r^{\prime}) - (d_l + d_r)

あとは $d_i$ を計算すればよいのだが、人の座標を管理するためにsetを用いることで、座標をキーとした二分探索によって新たに到着した人の左右の人を高速に求めることができる(詳細は実装例を参照)。

全体の計算量は $O(N \log N)$ である。

実装例

get_d関数は、引数の座標(内部的にはsetのイテレータ)に立っている人に対して $d_i$ を計算する。

新たに到着した人の右隣に人が存在することを事前にチェックすることを忘れずに。

なお、 C++ のset::insertは返り値の第一要素に新しく挿入された要素を指すイテレータを返すので、これを利用している。

set::insert - cpprefjp C++日本語リファレンス

新しく一つの要素(引数 `x`, `y`を使う)または要素のシーケンス(入力イテレータまたは `initializer_list` を使う)を挿入することにより、 `set` コンテナを拡張する。

cpprefjp - C++日本語リファレンス

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.constexpr long long INFL = 1e+18;
7. 
8.using ll = long long;
9. 
10.template <typename T>
11.inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    int N;
18.    cin >> N;
19.    vector<ll> X(N);
20.    rep(i, 0, N) cin >> X[i];
21. 
22.    set<ll> st;
23.    st.insert(0);
24. 
25.    auto get_d = [&](const auto itr) -> ll
26.    {
27.        if (st.size() == 1)
28.            return 0;
29. 
30.        ll res = INFL;
31.        if (itr != st.begin())
32.            chmin(res, abs(*itr - *prev(itr)));
33.        if (next(itr) != st.end())
34.            chmin(res, abs(*itr - *next(itr)));
35. 
36.        return res;
37.    };
38. 
39.    ll D = 0;
40.    rep(i, 0, N)
41.    {
42.        auto itr_r = st.lower_bound(X[i]);
43.        auto itr_l = prev(itr_r);
44. 
45.        ll d_l_old = get_d(itr_l);
46.        ll d_r_old = 0;
47.        if (itr_r != st.end())
48.            d_r_old = get_d(itr_r);
49. 
50.        auto itr_x = st.insert(X[i]).first;
51.        ll d_x = get_d(itr_x);
52. 
53.        ll d_l_new = get_d(itr_l);
54.        ll d_r_new = 0;
55.        if (itr_r != st.end())
56.            d_r_new = get_d(itr_r);
57. 
58.        D += (d_l_new + d_x + d_r_new) - (d_l_old + d_r_old);
59. 
60.        cout << D << endl;
61.    }
62. 
63.    return 0;
64.}