概要

この問題は、すべての畑を収穫可能にする（各畑 \(i\) に \(D_i\) 以上の作業量を割り当てる）ために必要な最小の日数を求める問題です。一見複雑なスケジュール問題に見えますが、作業員の割り当ての自由度が高いため、実は非常にシンプルな数式で解くことができます。

考察

1. 必要な最小日数の下限を考える

すべての畑を収穫可能にするために必要な、すべての畑の必要作業量の総和を \(S\) とします。 $\(S = \sum_{i=1}^{N} D_i\)$

1日あたりに作業員全員がこなせる作業量の合計はちょうど \(M\) です。作業員を休ませることはできないため、1日に進む農場全体の作業量は常に \(M\) となります。

したがって、どうしても最低でも以下の日数はかかります。 $\(\lceil S / M \rceil \text{ 日} \quad （S / M 以上の最小の整数、つまり切り上げ）\)$

2. 本当にこの日数で達成できるか？

「作業員を自由に割り当てられる」という条件があるため、実は無駄な作業を一切発生させずに作業を進めることができます。

イメージとしては、長さ \(D_1, D_2, \ldots, D_N\) のマス目を一列に並べ、そこに毎日 \(M\) 個のスタンプを端から順番に押していくようなものです。

• 1日目: 畑1から順に作業員を割り当てていきます。畑1の目標 \(D_1\) に達したら、残りの作業員は畑2に割り当てます。畑2も達したら畑3へ……と、合計 \(M\) 人分を順に割り当てます。
• 2日目: 1日目に割り当て終わった続きから、同様に作業員を割り当てていきます。

この方法（貪欲法的なアプローチ）をとれば、すでに収穫可能になった畑に余分な作業量を割り当ててしまう（無駄にする）ことなく、最後の1日を除いて毎日ちょうど \(M\) ずつ必要な作業量を消化していくことができます。

最後の1日だけは、残りの必要な作業量が \(M\) 未満になる可能性がありますが、その場合は余った作業員をすでに終わった畑に適当に割り当てればよいため、問題ありません。

したがって、必要な最小日数は正確に 「総作業量 \(S\) を \(M\) で割って切り上げた値」 となります。

アルゴリズム

1. 各畑の必要作業量 \(D_i\) の総和 \(S\) を計算します。
2. \(S\) を \(M\) で割って切り上げた値 \(\lceil S / M \rceil\) を計算します。
   • プログラミングにおいて、正の整数 \(S, M\) の切り上げ除算は (S + M - 1) / M という式で整数型のまま計算できます。
3. 計算した値を答えとして出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 個の入力を順に読み込み、総和を計算するだけなので、畑の数 \(N\) に対して線形時間で動作します。制約 \(N \le 10^6\) に対しても十分高速です。

• 空間計算量: \(O(1)\) 入力された \(D_i\) を配列などに保存しておく必要はなく、入力を受け取りながらその都度総和に加算していけばよいため、余分なメモリは必要ありません。

実装のポイント

• オーバーフローへの対策 \(N \le 10^6\)、 \(D_i \le 10^9\) であるため、総和 \(S\) は最大で \(10^{15}\) に達します。これは通常の32ビット整数型（C++の int など）の最大値（約 \(2 \times 10^9\)）を大きく超えるため、必ず64ビット整数型（C++では long long）を使用してください。

• 高速な入出力 \(N\) が最大 \(10^6\) と大きいため、C++では cin.tie(nullptr) や ios_base::sync_with_stdio(false) を用いて入出力を高速化しておくのが安全です。

  ソースコード

#include <iostream>

using namespace std;

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

    int n;
    long long m;
    if (!(cin >> n >> m)) return 0;

    long long sum_d = 0;
    for (int i = 0; i < n; ++i) {
        long long d;
        cin >> d;
        sum_d += d;
    }

    long long ans = (sum_d + m - 1) / m;
    cout << ans << "\n";

    return 0;
}

---

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