概要

一直線上に並んだ \(N\) 軒の家すべてを、購入可能な \(M\) 種類の街灯をいくつか設置してカバーするときの最小費用を求める問題です。

考察

1. 家のソートと区間への分割

家は数直線上に散らばっています。扱いやすくするために、まずは家の座標を昇順にソートして \(X_1 < X_2 < \dots < X_N\) とします。

すべての家をカバーするとき、ある1つの街灯がカバーする家の集合は、ソートされた家の中で連続する部分列（区間）になります。 例えば、ある街灯が家 \(j+1\) と家 \(i\) (\(j+1 < i\)) をカバーしているなら、その間にある家 \(j+2, \dots, i-1\) も必ず同じ街灯の範囲内に収まります。 したがって、この問題は「すべての家をいくつかの連続する区間に分割し、それぞれの区間を1つの街灯でカバーする」という問題に帰着できます。

2. 1つの区間をカバーする条件

家 \(j+1\) から家 \(i\) までの区間（\(X_{j+1}, \dots, X_i\)）を1つの街灯でカバーすることを考えます。 この区間の両端の距離は \(D = X_i - X_{j+1}\) です。 半径 \(R\) の街灯は、設置場所を適切に選ぶ（区間のちょうど真ん中に置く）ことで、最大で長さ \(2R\) の区間をカバーできます。 したがって、直径 \(2R \ge D\) を満たす街灯であれば、この区間のすべての家を1つの街灯でカバーすることができます。

3. 動的計画法 (DP) の適用

「最初の \(i\) 軒の家をカバーする最小コスト」を \(dp[i]\) と定義します。 \(dp[i]\) を求めるために、最後にカバーする区間を「家 \(j+1\) から家 \(i\) までの区間」（\(0 \le j < i\)）として全探索します。 このとき、以下の遷移式が成り立ちます。

\[dp[i] = \min_{0 \le j < i} \left( dp[j] + (\text{直径が } X_i - X_{j+1} \text{ 以上の街灯の最小コスト}) \right)\]

4. 最適な街灯の高速な取得

各遷移で「直径が \(D\) 以上の街灯の最小コスト」を高速に求める必要があります。 あらかじめ、街灯を直径 \(2R\) の昇順にソートしておき、各街灯について「自身より直径が大きい（または等しい）街灯の中での最小コスト」を累積最小値（Suffix Min）として計算しておきます。

\(j\) を \(i-1\) から \(0\) に向かって減らしていくとき、必要な直径 \(D = X_i - X_{j+1}\) は単調に増加します。 これを利用して、ポインタ \(k\) を左から右に進める尺取り法の要領で探索することで、各遷移における最適な街灯をアモルタイズ（ならし） \(O(1)\) で見つけることができます。

アルゴリズム

1. 家の座標 \(X\) を昇順にソートします。
2. 街灯の情報を（直径 \(2R_j\), コスト \(C_j\)）のペアとして、直径の昇順にソートします。
3. 街灯のコストの後ろからの累積最小値 suffix_min を構築します。
   • suffix_min[j] は、ソート後の \(j\) 番目以降の街灯における最小のコストを表します。
4. DPテーブル dp を無限大（\(INF\)）で初期化し、dp[0] = 0 とします。
5. \(i = 1\) から \(N\) までループを回します：
   • ポインタ \(k = 0\) とおきます。
   • \(j = i-1\) から \(0\) まで逆順にループを回します：
     • 必要な直径 \(D = X_i - X_{j+1}\) を計算します。
     • 街灯の直径が \(D\) 未満である限り（S[k].first < D）、ポインタ \(k\) を進めます。
     • 直径 \(D\) 以上を満たす街灯の最小コストは suffix_min[k] となります。
     • dp[i] = min(dp[i], dp[j] + suffix_min[k]) で更新します。
6. すべての家をカバーしたときの最小コストである dp[N] を出力します。

計算量

• 時間計算量: \(O(N^2 + NM + M \log M)\)

  • 家のソートに \(O(N \log N)\)、街灯のソートに \(O(M \log M)\) かかります。
  • DPの遷移において、外側のループが \(N\) 回、内側のループが \(N\) 回回ります。各 \(i\) のループにおいて、ポインタ \(k\) は最大で \(M\) 回しか増加しないため、内側ループ内の処理（ポインタの移動を含む）は全体で \(O(N^2 + NM)\) となります。
  • \(N, M \le 3000\) であるため、全体の計算回数は最大でも約 \(1.8 \times 10^7\) 回となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N + M)\)

  • 家の座標、街灯のデータ、DPテーブル、累積最小値配列を保持するために必要なメモリです。

実装のポイント

• ポインタ \(k\) の単調性: 内側のループで \(j\) を \(i-1\) から \(0\) に向かって減らす（カバーする区間を左側に広げる）と、必要な直径 \(D = X_i - X_{j+1}\) は必ず増加します。このため、ポインタ \(k\) を右に動かすだけで最適な街灯を探索でき、二分探索を使う必要がなくなります。

• オーバーフローへの注意: コストの合計や座標の差は \(10^9\) を超える可能性があるため、DPテーブルや累積最小値、距離の計算には 64 ビット整数型（C++ の long long）を使用します。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> X(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> X[i];
    }
    // 家の座標を昇順にソート
    sort(X.begin() + 1, X.end());

    // 街灯の情報を格納 (2 * R_j, C_j)
    vector<pair<long long, long long>> S(M);
    for (int j = 0; j < M; ++j) {
        long long R, C;
        cin >> R >> C;
        S[j] = {2 * R, C};
    }
    // 直径(2*R)の昇順にソート
    sort(S.begin(), S.end());

    // suffix_min[j] : インデックス j 以降の街灯における最小コスト
    vector<long long> suffix_min(M + 1, INF);
    for (int j = M - 1; j >= 0; --j) {
        suffix_min[j] = min(suffix_min[j + 1], S[j].second);
    }

    // dp[i] : 最初の i 軒の家をすべてカバーするための最小コスト
    vector<long long> dp(N + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= N; ++i) {
        int k = 0;
        for (int j = i - 1; j >= 0; --j) {
            long long D = X[i] - X[j + 1];
            // 直径 D 以上の街灯を探す
            while (k < M && S[k].first < D) {
                k++;
            }
            long long cost = (k < M) ? suffix_min[k] : INF;
            if (cost != INF && dp[j] != INF) {
                dp[i] = min(dp[i], dp[j] + cost);
            }
        }
    }

    cout << dp[N] << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。