ひょっとしたら難易度 5 との境界の問題だったかもしれない。lower_bound() を試すいい感じの例題。

問題概要

一周の長さが $D$ であるような周回コースがあって、コース上に $N$ 個の店舗がある。コース上の 1 点の座標を 0 とし、コースに沿って座標を設定する ( $D = 0$ となる)。

1 個目の店舗は座標 0 のところにあり、2 個目, 3 個目, ..., $N$ 個目の店舗の座標は $d_{2}, \dots, d_{N}$ で与えられる。

以下の $M$ 個のクエリに答えよ。 $i$ 番目のクエリでは座標 $k_{i}$ が与えられる。 $k_{i}$ の位置からもっとも近いところにある店舗との距離を求めよ。

制約

$N \le 10^{5}$
$M \le 10^{4}$

考えたこと

店舗の座標は $0, d_{2}, d_{3}, \dots, d_{N}$ となる。あらかじめこれを座標順にソートしておくことにする。

各クエリ $k_{i}$ に対しては、配列 $0, d_{2}, d_{3}, \dots, d_{N}$ の要素のうち、どの要素とどの要素との間にあるのかを二分探索 (C++ では lower_bound()) を用いて求めることができる。

なお、便宜上、店舗の座標に $D$ を末尾に加えておくと便利。これがちょうど番兵の役割を果たす。

計算量は $O((N+M) \log N)$ となる。

コード

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

int main() {
    long long D, N, M;
    cin >> D >> N >> M;
    vector<long long> a(N+1, 0);
    for (int i = 1; i < N; ++i) cin >> a[i];
    a[N] = D;
    sort(a.begin(), a.end());
    long long res = 0;
    for (int i = 0; i < M; ++i) {
        long long k;
        cin >> k;
        int it = lower_bound(a.begin(), a.end(), k) - a.begin();
        long long tmp = abs(a[it] - k);
        if (it > 0) tmp = min(tmp, abs(a[it-1] - k));
        res += tmp;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2009 B - ピザ (AOJ 0539, 難易度 6)

問題概要

制約

考えたこと

コード