問題概要

数直線上に $N$ 個の鐘がある。 $i$ 番目の鐘は座標 $A_{i}$ の地点に配置されている。

地点 $x$ の人の聞く鐘の音の強さは、各鐘 $i$ に対する $max(K - |x - A_{i}|, 0)$ という値の最大値となる。

今、 $M$ 個の家がある。家 $i$ は座標 $B_{i}$ の地点にある。各家について、その地点で聞く鐘の音の強さを求めよ。

制約

$1 \le N, M \le 10^{5}$

解法

競プロ典型 90 問の 7 問目にとてもよく似た問題ですね！

drken1215.hatenablog.com

まず、 $max(K - |x - A_{i}|, 0)$ という数式の意味を解釈しましょう。これは

地点 $A_{i}$ にある鐘とぴったり重なった場所で聞く鐘 $i$ の音の強さは $K$
地点 $A_{i}$ から 1 離れると、音の強さは 1 小さくなり $K-1$ となる
地点 $A_{i}$ から 2 離れると、音の強さは 2 小さくなり $K-2$ となる
...
地点 $A_{i}$ から $K$ 以上離れると、鐘 $i$ の音の強さは 0 となる (聞こえなくなる)

ということを意味しています。

愚直な解法としては、次のように二重 for 文を使う方法が考えられるかもしれません。

// 各家 i に対して
for (int i = 0; i < M; ++i) {
    // N 個の鐘を全探索して音の強さの最大値を求める
    long long res = 0;
    for (int j = 0; j < N; ++j) {
        res = max(res, K - abs(B[i] - A[j]));
    }
}

しかし、この解法の計算量は $O(NM)$ となります。 $N, M \le 10^{5}$ という制約を考えると TLE となってしまいます (部分点として 40 点まで獲得できます)。工夫しましょう。

二分探索に持ち込む

よく考えると、各家に対して、すべての鐘を考慮する必要はありません。下図のように、家のある地点に対して、前後の最も近い鐘 2 つ (家が端っこの場合は 1 つ) のみ考えればよいのです。

そこで課題となるのは、次の問題です。

各家が、どの鐘とどの鐘の間にあるのかを高速に求めたい

これにはまさにうってつけの方法があります！　C++ であれば lower_bound() を使うことで $O(\log N)$ の計算量で求められます。

lower_bound() の使い方については、次の記事で詳しく解説しています。

drken1215.hatenablog.com

まとめ

各家について、

どの鐘とどの鐘の間にあるかを、lower_bound() で求める (計算量 $O(\log N)$ )
その 2 つの鐘の音の強さを比較して大きい方を答える (計算量 $O(1)$ )

とすればよいです。各家について処理するので、計算量は $O(M \log N)$ となります。

なお、入力を受けとること自体にも $O(N + M)$ の計算量を要するため、コード全体の計算量は $O(N + M \log N)$ となります。

解答例コード

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

int main() {
    // 入力
    long long N, M, K;
    cin >> N >> M >> K;
    vector<long long> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];
    
    // 地点 x で聞こえる音の強さを求める関数
    auto calc = [&](long long x) -> long long {
        // A[i] >= x となる最小の i を求める (lower_bound を活用)
        int i = lower_bound(A.begin(), A.end(), x) - A.begin();
        
        // 調べるべきなのは A[i-1] と A[i]
        // K - abs(x - A[i]) < 0 になる場合は res が更新されないので、考えなくて OK
        long long res = 0;
        if (i-1 >= 0) res = max(res, K - abs(x - A[i-1]));
        if (i < N) res = max(res, K - abs(x - A[i]));
        return res;
    };
    
    // 各家について考える
    for (int i = 0; i < M; ++i) {
        cout << calc(B[i]) << endl;
    }
}