概要

一直線上に並んだ \(M\) 個のポイントから、隣り合う選択点の距離がすべて \(K\) 以上になるように \(N\) 個選びます。
条件を満たす選び方が存在するなら、最も左と最も右の距離の最大値を求めます。

考察

ポイント \(1\) の座標を \(0\) とし、ポイント \(i\) の座標を \(P_i\) とします。
花壇全体の長さは

\(P_M - P_1 = P_M\)

です。

選んだ点のうち、最も左の点と最も右の点の距離は、当然ながら花壇全体の長さ \(P_M\) を超えることはありません。

ここで重要な観察があります。

もし条件を満たす選び方が \(1\) つでも存在するとします。
その選び方を左から順に

\(x_1, x_2, \dots, x_N\)

とします。

\(N \geq 2\) のとき、左端の点 \(x_1\) をポイント \(1\)、つまり座標 \(0\) に移動しても、

\(x_2 - 0 \geq x_2 - x_1 \geq K\)

なので条件は壊れません。

同様に、右端の点 \(x_N\) をポイント \(M\)、つまり座標 \(P_M\) に移動しても、

\(P_M - x_{N-1} \geq x_N - x_{N-1} \geq K\)

なので条件は壊れません。

したがって、\(N \geq 2\) で条件を満たす選び方が存在するなら、必ずポイント \(1\) とポイント \(M\) の両方を選ぶことができ、答えは花壇全体の長さ \(P_M\) になります。

つまり、この問題は次のように言い換えられます。

• \(N = 1\) の場合、答えは常に \(0\)
• \(N \geq 2\) の場合、条件を満たして \(N\) 個選べるなら答えは全長
• 選べないなら -1

あとは「距離が \(K\) 以上離れるように最大何個選べるか」を調べればよいです。

素朴に全ての組み合わせを試すと、選び方は非常に多く、到底間に合いません。
また、DP で「何個目をどこに置くか」を考えると \(O(NM)\) になり、最大で \(5 \times 10^5\) なのでこれも間に合いません。

そこで、左から順に見て「置けるならすぐ置く」という貪欲法を使います。

できるだけ左に置いておけば、その後に使えるスペースが最大になります。
そのため、この貪欲法で選べる個数が最大になります。

アルゴリズム

ポイント \(1\) の座標を \(0\) として、左から順に座標を計算していきます。

1. 最初にポイント \(1\) を選ぶ
   
   • cnt = 1
   • 最後に選んだ座標を last = 0 とする
2. 左から順に各ポイントの座標 coord を求める
3. coord - last >= K なら、そのポイントを選ぶ
   • cnt を \(1\) 増やす
   • last = coord とする
4. 最後まで見た後、花壇全体の長さを total とする
5. 答えを判定する
   • \(N = 1\) なら 0
   • cnt >= N なら total
   • そうでなければ -1

例えば、座標が

\(0, 4, 10, 13, 21\)

で、\(K = 7\) の場合を考えます。

左から貪欲に選ぶと、

• 最初に \(0\) を選ぶ
• \(4\) は距離が \(4\) なので選べない
• \(10\) は距離が \(10\) なので選ぶ
• \(13\) は直前の \(10\) から距離 \(3\) なので選べない
• \(21\) は直前の \(10\) から距離 \(11\) なので選ぶ

よって \(3\) 個選べます。
もし \(N = 3\) なら条件を満たす選び方が存在するので、答えは全長 \(21\) です。

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(1)\)

実装のポイント

距離の合計は大きくなる可能性があるため、座標や距離は long long で扱います。

また、各 \(D_i\) を配列に保存する必要はありません。
入力を読みながら現在の座標を更新し、その場で貪欲に選べるか判定すれば十分です。

\(N = 1\) の場合は、選んだ点の最も左と最も右は同じ点なので、答えは必ず \(0\) になります。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    long long coord = 0;
    long long total = 0;

    int cnt = 1;
    long long last = 0;

    for (int i = 1; i <= M - 1; i++) {
        long long d;
        cin >> d;
        coord += d;
        if (coord - last >= K) {
            cnt++;
            last = coord;
        }
    }
    total = coord;

    if (N == 1) {
        cout << 0 << '\n';
    } else if (cnt >= N) {
        cout << total << '\n';
    } else {
        cout << -1 << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。