概要

直線上に並んだ \(M\) 個のポイントから \(N\) 個のポイントを選び、隣り合うポイント同士の距離をすべて \(K\) 以上に保ちつつ、選んだポイントの「最も左」と「最も右」の距離を最大化する問題です。

考察

1. 最大値はいくらになるか？

選んだポイントのうち、最も左にあるものを \(L\)、最も右にあるものを \(R\) とします。このとき、求めたい距離は \(X_R - X_L\) です（ただし、\(X_i\) はポイント \(i\) の座標）。

この距離を最大化したいので、理想的には 最も左のポイントとして \(1\)（座標 \(X_0\)）を、最も右のポイントとして \(M\)（座標 \(X_{M-1}\)）を選びたい です。もしこれが可能なら、最大値は花壇の端から端までの距離、すなわち \(X_{M-1} - X_0\) になります。

実は、条件を満たす選び方が存在するならば、常に最大値は \(X_{M-1} - X_0\) になります。

2. なぜ全体の長さが最大値になるのか？

「左端をポイント \(1\) に固定し、そこから右に向かって間隔 \(K\) 以上あくように貪欲（できるだけ左寄り）に \(N\) 個の花を配置する」というシミュレーションを考えます。

このシミュレーションで、最後の \(N\) 番目の花がポイント \(P\) に置けたとします。 - \(P \leq M\) のとき（配置に成功した場合）： 最後の \(N\) 番目の花を、ポイント \(P\) からさらに右にあるポイント \(M\) に移動させても、隣り合う花との距離は広がるだけなので、制約（距離 \(\geq K\)）を満たしたままです。 したがって、左端を \(1\)、右端を \(M\) にした有効な配置が必ず存在します。このときの距離は \(X_{M-1} - X_0\) です。 - 途中で配置できなくなった場合： 左端からできるだけ詰めて置いても \(N\) 個置けないということは、どのように選んでも条件を満たす配置は存在しません。したがって、答えは -1 になります。

この考察により、問題は「左端から貪欲に \(N\) 個の花を配置できるか？」という判定問題に帰着されます。

3. 高速化の工夫

各ポイントの座標 \(X\) は、隣り合う距離 \(D_i\) の累積和をとることで事前に計算できます。 左から順に次の配置ポイントを探す際、素朴に \(1\) つずつ調べていくと最悪の場合 \(O(NM)\) の時間がかかり、実行時間制限に間に合いません。

座標配列 \(X\) は昇順にソートされているため、二分探索（std::lower_bound）を使うことで、現在地から距離 \(K\) 以上離れた次のポイントを \(O(\log M)\) で高速に見つけることができます。

---

アルゴリズム

1. 座標の準備: 各ポイントの座標を累積和を用いて計算し、配列 \(X\) に格納します。 \(X_0 = 0\) とし、\(X_{i+1} = X_i + D_i\) とします。

2. コーナーケースの処理: \(N = 1\) の場合は、最も左と最も右のポイントが同じになるため、距離は常に 0 です。

3. 貪欲法によるシミュレーション:

   • \(1\) 番目の花を \(X_0\)（ポイント \(1\)）に置きます。
   • \(i\) 番目の花を置いた座標を curr としたとき、\((i+1)\) 番目の花は curr + K 以上の座標を持つ最も左のポイントに置きます。この探索に二分探索（lower_bound）を使用します。
   • これを \(N\) 個置けるまで繰り返します。途中で置けなくなったら、条件を満たす配置は存在しないため -1 を出力します。

4. 答えの出力: \(N\) 個置くことができた場合、最大距離である \(X_{M-1} - X_0\) を出力します。

---

計算量

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

  • 累積和による座標の計算に \(O(M)\) かかります。
  • 貪欲法のシミュレーションにおいて、二分探索を \(N-1\) 回行うため、この部分は \(O(N \log M)\) となります。
  • 全体として実行時間制限に十分間に合います。

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

  • 各ポイントの座標を保持する配列 \(X\) のために \(O(M)\) のメモリを使用します。

---

実装のポイント

• 型への注意: 距離の総和や \(K\) は非常に大きな値（最大で \(5 \times 10^{14}\) 程度）になるため、オーバーフローを防ぐために C++ では long long 型を使用する必要があります。

• 二分探索の利用: std::lower_bound を使用することで、条件を満たす最小のインデックスを \(O(\log M)\) で取得できます。見つからなかった場合（it == X.end()）の境界条件の処理に注意しましょう。

  ソースコード

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

using namespace std;

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<long long> D(M - 1);
    for (int i = 0; i < M - 1; ++i) {
        cin >> D[i];
    }

    // Corner case: If only 1 flower is to be planted, the distance is always 0.
    if (N == 1) {
        cout << 0 << "\n";
        return 0;
    }

    // X[i] stores the coordinate of point i+1 (0-indexed)
    vector<long long> X(M, 0);
    for (int i = 0; i < M - 1; ++i) {
        X[i + 1] = X[i] + D[i];
    }

    // Greedy simulation to check if it's possible to place N flowers
    int curr = 0;
    bool possible = true;
    for (int step = 1; step < N; ++step) {
        long long target = X[curr] + K;
        auto it = lower_bound(X.begin(), X.end(), target);
        if (it == X.end()) {
            possible = false;
            break;
        }
        curr = distance(X.begin(), it);
    }

    // If a valid configuration exists, the maximum distance is always the total length X[M-1] - X[0].
    if (possible) {
        cout << X[M - 1] << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

---

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