概要

この問題は、一直線上に並んだ \(M\) 個のポイントから、隣り合うポイント間の距離がすべて \(K\) メートル以上となるように \(N\) 個のポイントを選ぶとき、選んだポイントの「左端から右端までの距離」を最大化する問題です。条件を満たす選び方が存在しない場合は -1 を出力します。

---

考察

1. 重要な気づき：最大距離は常に「端から端までの距離」になる

この問題の最も重要なポイントは、「条件を満たす選び方が存在するならば、最大距離は常に『最も左のポイント \(1\)』と『最も右のポイント \(M\)』を選んだときの距離になる」という点です。

なぜこれが成り立つのかを考えてみましょう。 今、条件を満たす \(N\) 個のポイントの選び方 \(p_1 < p_2 < \dots < p_N\) が存在すると仮定します。 このとき、 - 一番左のポイント \(p_1\) を、さらに左にある「ポイント \(1\)」へと変更する - 一番右のポイント \(p_N\) を、さらに右にある「ポイント \(M\)」へと変更する

という操作を行っても、隣り合うポイント同士の距離（\(p_2 - p_1\) や \(p_N - p_{n-1}\)）は広がるだけなので、隣接距離が \(K\) 以上であるという制約を破ることはありません。

したがって、条件を満たす選び方が \(1\) つでも存在するならば、必ず「左端（ポイント \(1\)）と右端（ポイント \(M\)）を両方選ぶような条件を満たす選び方」も必ず存在します。よって、求める最大距離は常に全体の長さ（ポイント \(1\) から \(M\) までの距離）になります。

2. 条件を満たす選び方が存在するかどうかの判定

では、条件を満たす選び方が存在するかどうか（＝隣接距離 \(K\) 以上で \(N\) 個のポイントを配置できるか）はどのように判定すればよいでしょうか。

これは、「できるだけ左詰めで貪欲にポイントを選んでいく」という貪欲法で判定できます。 1. \(1\) つ目のポイントを、最も左の「ポイント \(1\)」に固定します。 2. \(2\) つ目のポイントは、「\(1\) つ目のポイントから距離が \(K\) 以上離れているポイントのうち、最も左にあるもの」を選びます。 3. \(3\) つ目のポイントは、「\(2\) つ目のポイントから距離が \(K\) 以上離れているポイントのうち、最も左にあるもの」を選びます。 4. これを \(N\) 個目のポイントを選ぶまで繰り返します。

この方法で \(N\) 個のポイントをすべて選ぶことができれば（最後のポイントが \(M\) 以下に収まれば）、条件を満たす配置が存在すると判定できます。途中でポイントが足りなくなってしまった場合は、どのように工夫して選んでも \(N\) 個配置することは不可能なため、解は存在しません（-1）。

---

アルゴリズム

1. 各ポイントの座標の計算 隣接するポイント間の距離 \(D_i\) から、ポイント \(1\) を原点 \(0\) としたときの各ポイントの座標 \(X_0, X_1, \dots, X_{M-1}\) を累積和を用いて計算します。

   • \(X_0 = 0\)
   • \(X_i = X_{i-1} + D_{i-1} \quad (1 \leq i \leq M-1)\)

2. 貪欲法による判定（尺取り法ライクなポインタ遷移） 現在選んでいるポイントのインデックスを curr_idx とします。 次のポイントの候補を探索するために、X[next_idx] >= X[curr_idx] + K を満たす最小の next_idx を探します。 これを \(N-1\) 回繰り返します。

   • next_idx が \(M\) を超えてしまった場合は、条件を満たす配置が不可能であるため -1 を出力します。
   • 無事に \(N\) 個選べた場合は、全体の長さである \(X_{M-1}\) を出力します。

---

計算量

• 時間計算量: \(O(M)\)
  • 座標配列 \(X\) の構築に \(O(M)\) かかります。
  • 貪欲法による探索において、ポインタ next_idx は常に右に進むだけ（巻き戻らない）なので、全体で最大 \(M\) 回しかインクリメントされません。したがって、判定パートも \(O(M)\) で動作します。
• 空間計算量: \(O(M)\)
  • 各ポイントの座標を保持する配列 \(X\) のために \(O(M)\) のメモリを使用します。

---

実装のポイント

• \(N = 1\) のコーナーケース \(N = 1\) の場合は、最も左のポイントと最も右のポイントが同じ（ポイント \(1\)）になるため、距離は必ず 0 になります。このケースをはじめに処理しておくことで、以降の実装で \(N \geq 2\) を前提にシンプルに書くことができます。

• 高速な入出力 \(M\) が最大で \(5 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() を用いて入力を一括で取得することで、実行時間を大幅に短縮できます。

  ソースコード

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # N = 1 の場合は、最も左と最も右が同じポイントになるため距離は 0
    if N == 1:
        print(0)
        return
        
    D = [int(x) for x in input_data[3:]]
    
    # 各ポイントの座標を計算
    X = [0] * M
    for i in range(M - 1):
        X[i+1] = X[i] + D[i]
        
    # 尺取り法を用いて、隣接距離 K 以上で N 個のポイントを選べるか判定
    curr_idx = 0
    next_idx = 0
    for _ in range(N - 1):
        target = X[curr_idx] + K
        while next_idx < M and X[next_idx] < target:
            next_idx += 1
        if next_idx == M:
            print(-1)
            return
        curr_idx = next_idx
        
    # 条件を満たす選び方が存在する場合、最大距離は常に全体の端から端までの距離となる
    print(X[M-1])

if __name__ == '__main__':
    solve()

---

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