概要

\(M\) 個の点から \(N\) 個を選び、選んだ点同士の隣接距離がすべて \(K\) 以上になるようにします。
条件を満たせるなら、最も左と最も右の距離の最大値を求めます。

考察

各ポイントの座標を、左端のポイント \(1\) を \(0\) として考えます。

例えば、距離が

\(D = [2, 3, 4, 2]\)

なら、各ポイントの座標は

\(0, 2, 5, 9, 11\)

となります。

---

重要な気づきは次の通りです。

条件を満たす選び方が存在するなら、両端のポイントを選んでよい

選んだ \(N\) 個のポイントを左から順に

\(p_1, p_2, \dots, p_N\)

とします。

もしこの選び方が条件を満たしているなら、最も左の選択点 \(p_1\) をポイント \(1\) に変えても、次の点との距離は短くなりません。

同様に、最も右の選択点 \(p_N\) をポイント \(M\) に変えても、前の点との距離は短くなりません。

つまり、条件を満たす選び方が存在するなら、ポイント \(1\) とポイント \(M\) を含む選び方も存在します。

したがって、\(N \geq 2\) のとき、答えは次のどちらかです。

• 条件を満たす選び方が存在するなら、答えはポイント \(1\) からポイント \(M\) までの距離
• 存在しないなら、答えは \(-1\)

ポイント \(1\) からポイント \(M\) までの距離は、すべての \(D_i\) の総和です。

---

あとは「条件を満たして \(N\) 個選べるか」を判定すればよい

条件を満たすかどうかは、貪欲法で判定できます。

左から順に見ていき、最後に選んだポイントからの距離が \(K\) 以上になったら、そのポイントを選びます。

これは「できるだけ左に詰めて選ぶ」方法です。

できるだけ早く次のポイントを選んでおけば、その後に選べる余地が最大になります。
そのため、この貪欲法で \(N\) 個選べないなら、どんな選び方でも \(N\) 個選べません。

---

素朴な方法が難しい理由

\(M\) 個から \(N\) 個を選ぶ全探索は、組み合わせ数が非常に大きくなります。

また、動的計画法で「何個選んだか」「最後にどこを選んだか」を管理すると、最悪で \(O(NM)\) 程度になり、制約 \(M \leq 5 \times 10^5\) では間に合いません。

この問題では、答えが「全体の長さ」か「\(-1\)」のどちらかになることを利用することで、線形時間で解けます。

アルゴリズム

\(N = 1\) の場合、選ぶポイントは \(1\) 個だけなので、最も左と最も右は同じポイントです。
したがって答えは常に \(0\) です。

\(N \geq 2\) の場合、以下を行います。

1. ポイント \(1\) を選んだ状態から始める
2. 左から順にポイントを見ていく
3. 最後に選んだポイントからの距離が \(K\) 以上なら、そのポイントを選ぶ
4. \(N\) 個選べたら条件を満たせる
5. 最終的に、
   • \(N\) 個以上選べたなら、答えは全体の距離
   • 選べなければ、答えは \(-1\)

コード中では、以下の変数を使っています。

• total: ポイント \(1\) から現在までの総距離、最終的には全体の距離
• cur: 現在見ているポイントの座標
• last: 最後に選んだポイントの座標
• cnt: 現在選んだポイント数

例えば、座標が

\(0, 2, 5, 9, 11\)

で、\(K = 4\), \(N = 3\) の場合を考えます。

• 最初に座標 \(0\) を選ぶ
• 座標 \(2\) は距離 \(2\) なので選べない
• 座標 \(5\) は距離 \(5\) なので選ぶ
• 座標 \(9\) は距離 \(4\) なので選ぶ

これで \(3\) 個選べたので条件を満たせます。
したがって答えは全体の距離 \(11\) です。

実際には、座標 \(0, 5, 11\) を選べば、両端を使って距離 \(11\) を達成できます。

計算量

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

実装のポイント

\(D_i\) の総和は大きくなる可能性があるため、他の言語では long long などの 64 bit 整数型を使う必要があります。

Python では整数の桁あふれを気にする必要はありません。

また、\(N = 1\) の場合は隣り合う花が存在しないため、制約は常に満たされ、答えは \(0\) になります。

ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    K = next(it)

    if N == 1:
        print(0)
        return

    total = 0
    cur = 0
    last = 0
    cnt = 1

    for d in it:
        total += d
        cur += d
        if cnt < N and cur - last >= K:
            cnt += 1
            last = cur

    print(total if cnt >= N else -1)

if __name__ == "__main__":
    main()

---

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