概要

すべての畑を収穫可能にするために必要な作業量の総和を求め、1日あたりに作業員全員がこなせる作業量 \(M\) から、必要な最小日数を計算する問題です。

考察

一見すると「どの日にどの畑に何人の作業員を割り当てるか」という複雑なスケジュールを立てる必要があるように見えますが、問題の条件を整理すると非常にシンプルに考えることができます。

1. 必要な総作業量 すべての畑 \(i\) を収穫可能にするためには、畑 \(i\) に少なくとも \(D_i\) の作業量を割り当てる必要があります。したがって、農場全体で必要な総作業量は、各畑の必要作業量の総和 \(S = \sum_{i=1}^N D_i\) となります。

2. 1日あたりの作業量 作業員は \(M\) 人おり、全員を必ずいずれかの畑に割り当てる必要があります。また、1人が1日にこなす作業量は \(1\) なので、農場全体では毎日ちょうど \(M\) の作業量が発生します。

3. 日数の下限 必要な日数を \(X\) 日とすると、 \(X\) 日間でこなせる作業量の合計は \(X \times M\) となります。これが全体の必要作業量 \(S\) 以上でなければならないため、以下の不等式が成り立ちます。 $\(X \times M \geq S \implies X \geq \frac{S}{M}\)\( 日数 \)X\( は整数であるため、必要な最小日数は \)\frac{S}{M}\( を切り上げた値、すなわち \)\lceil \frac{S}{M} \rceil$ 日となります。

4. この下限が常に達成可能である理由 問題文より、以下の柔軟なルールが認められています。

   • 1つの畑に何人でも（最大 \(M\) 人まで）同時に割り当ててよい。
   • すでに収穫可能になった畑にさらに作業員を割り当ててもよい（余剰な作業が発生してもよい）。
   • 日ごとに割り当てを自由に変えてよい。

このため、例えば「畑1に \(D_1\)、畑2に \(D_2\)、……と順番に作業量を割り当てていき、1日の上限 \(M\) を超えた分は翌日に回す」というように貪欲に割り振ることで、途中で作業が無駄になることなく、総作業量 \(S\) を \(X\) 日間で過不足なく分配することができます。

したがって、個々の \(D_i\) の値に細かくこだわる必要はなく、「総作業量 \(S\) を、1日あたり \(M\) ずつ進めたときに何日かかるか」を計算するだけで正解を導くことができます。

アルゴリズム

1. 与えられた \(D_1, D_2, \ldots, D_N\) の総和 \(S\) を計算します。
2. 最小日数 \(X = \lceil S / M \rceil\) を計算します。
   • 整数型のみで切り上げ除算を行うため、多くのプログラミング言語では (S + M - 1) // M という式を用いて計算します。
3. 計算した \(X\) を出力します。

計算量

• 時間計算量: \(O(N)\) \(D_i\) の総和を求めるために、入力された配列を1回走査する時間がボトルネックとなります。\(N \leq 10^6\) であるため、十分高速に動作します。
• 空間計算量: \(O(N)\) 入力をすべて配列として保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローへの注意 \(N \leq 10^6\)、 \(D_i \leq 10^9\) であるため、総和 \(S\) は最大で \(10^{15}\) に達します。C++ などの 32bit 整数型（int）を使用する言語ではオーバーフローが発生するため、必ず 64bit 整数型（long long など）を使用してください（Pythonでは自動的に多倍長整数として扱われるため心配ありません）。

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

  ソースコード

import sys

def main():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # D_i の総和を計算
    total_D = sum(map(int, input_data[2:]))
    
    # 最小日数を計算
    ans = (total_D + M - 1) // M
    print(ans)

if __name__ == '__main__':
    main()

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