複数の隣接する配置ユニットが一列に連なっている状態を想定する。これらユニットのうち特定の位置には対象物が存在しており、それらの位置を最大 $M$ 枚の連続する板材で覆う必要がある。各板材は任意の長さを指定可能だが、使用できる総数は上限 $M$ に固定されている。すべての存在位置が含まれるように板材を設置した際、板材が占めるユニットの合計数を最小化するための処理を実装せよ。

入出力仕様

最初の行に整数 $M, S, C$ が空白区切りで与えられる。$M$ は利用可能な板材の上限枚数、$S$ は配置ユニットの総数、$C$ は対象物が存在する位置の数である。続く $C$ 行の各行に、存在位置の番号（$1$ から $S$ の範囲）が記録される。

標準出力へは、最小となる被覆ユニット数を整数で出力する。

データ制約

• $1 \le M \le 50$
• $1 \le S \le 200$
• $1 \le C \le S$
• 存在位置は $1$ から $S$ の範囲内にある整数

実行例

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

出力結果：

25

本例では、区間 $[3, 8]$、$[14, 21]$、$[25, 31]$、$[40, 43]$ の各領域に一枚ずつ板材を設置することで、対象外のユニットを最小限に抑えつつ合計 $25$ ユニットのみを被覆できる。

アルゴリズム設計方針

本問題は、制約付き線分被覆における貪欲戦略の典型的な応用である。最適解を導くロジックは以下の段階で構成される。

1. 全体スパンの初期化： 存在位置を昇順に整列させ、最小インデックスと最大インデックスの差に $1$ を加算する。これが単一の板材で全ての位置を覆った場合のコストとなる。
2. 空隙（ギャップ）の抽出： 整列済みの配列において、隣接する要素の差分から $1$ を引くことで、対象物同士の間に空いているユニット数（空隙幅）を算出する。
3. 区間の分割戦略： 使用可能板材が $k$ 枚まで増えるたびに、連続区間は $k-1$ 箇所切断される。つまり、最も空隙が広い $M-1$ 箇所を意図的にスルーして区間を分割すれば、被覆コストを最大化して削減できる。
4. 最適値の導出： 算出した空隙幅を降順にソートし、上位 $M-1$ 個の値を全体スパンから順次減算する。残値が求める最小被覆数となる。

C++実装例

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

int main() {
    int max_planks, total_units, occupied_count;
    if (!(std::cin >> max_planks >> total_units >> occupied_count)) return 0;

    std::vector<int> positions(occupied_count);
    for (int i = 0; i < occupied_count; ++i) {
        std::cin >> positions[i];
    }

    // 坐标を昇順にソート
    std::sort(positions.begin(), positions.end());

    // 両端を覆った場合の初期コスト
    int current_span = positions.back() - positions.front() + 1;

    // 隣接ポイント間の空隙長を抽出
    std::vector<int> gap_lengths;
    for (size_t i = 1; i < positions.size(); ++i) {
        gap_lengths.push_back(positions[i] - positions[i - 1] - 1);
    }

    // 空隙を長い順に並べ替え
    std::sort(gap_lengths.begin(), gap_lengths.end(), std::greater<int>());

    // 最大 $M-1$ 個の空隙を除外（既存の素材枚数を超える分割を防ぐためのガード処理含む）
    const int split_points = std::min(max_planks - 1, static_cast<int>(gap_lengths.size()));
    for (int i = 0; i < split_points; ++i) {
        current_span -= gap_lengths[i];
    }

    std::cout << current_span << std::endl;
    return 0;
}