概要

\(M\) 人の作業員を毎日各畑に最適に割り当てて、すべての畑を収穫可能にする最小日数を求める問題。答えは \(\lceil \sum D_i / M \rceil\)（全作業量を1日あたりの総作業力で割った切り上げ）。

考察

重要な気づき：1日あたりの作業力はちょうど \(M\)

毎日 \(M\) 人全員を必ずどこかの畑に割り当てるため、1日あたりの総作業量はちょうど \(M\) です。\(T\) 日間では、総作業量は \(T \times M\) となります。

下界の特定

すべての畑を収穫するのに必要な総作業量は \(\sum_{i=1}^{N} D_i\) です。1日に \(M\) ずつしか進まないので、最低でも次の日数が必要です：

\[T \geq \left\lceil \frac{\sum D_i}{M} \right\rceil\]

この下界は常に達成可能か？

もう一つ考えるべき制約は「1つの畑は1日に最大 \(M\) しか進まない」ため、最も重い畑には \(\lceil D_{\max} / M \rceil\) 日必要です。しかし：

\[\lceil D_{\max} / M \rceil \leq \lceil \sum D_i / M \rceil\]

が常に成立するため（\(D_{\max} \leq \sum D_i\)）、結局 \(\lceil \sum D_i / M \rceil\) だけが答えを決定します。

具体例で確認

• \(D = [5, 1]\), \(M = 100\): 合計 \(= 6\), 答え \(= \lceil 6/100 \rceil = 1\) 日。1日目に畑1に5人、畑2に1人、残り94人はどこかに配置（余剰作業は影響なし）。
• \(D = [3, 3, 3]\), \(M = 2\): 合計 \(= 9\), 答え \(= \lceil 9/2 \rceil = 5\) 日。例えば毎日2人ずつ割り振りを工夫すれば5日で全畑の作業量を満たせる。

なぜ下界が達成可能なのか

\(T\) 日間で各畑に必要な作業量を割り振る問題は、以下の条件が満たされれば必ず実行可能です：

1. 各畑 \(i\) は1日最大 \(M\) 作業を受けられる → \(D_i \leq T \times M\)（\(T = \lceil \sum D_i / M \rceil\) で保証）
2. 全畑の需要の合計が総容量以下 → \(\sum D_i \leq T \times M\)（定義より成立）

よって、\(M\) 人を毎日自由に配分できるため、この下界は常に達成できます。

アルゴリズム

1. \(D_1, D_2, \ldots, D_N\) の総和 \(S = \sum_{i=1}^{N} D_i\) を計算する
2. 答えは \(\lceil S / M \rceil = \lfloor (S + M - 1) / M \rfloor\) を出力する

計算量

• 時間計算量: \(O(N)\)（配列の総和を計算するだけ）
• 空間計算量: \(O(N)\)（入力配列の格納）

実装のポイント

• \(D_i\) と \(M\) が最大 \(10^9\)、\(N\) が最大 \(10^6\) のため、総和は最大 \(10^{15}\) 程度になる。Python では整数オーバーフローの心配はないが、C++ などでは long long が必要。

• 切り上げ除算は (S + M - 1) // M で正しく計算できる。

• ソートや二分探索は不要で、単純な合計計算のみで解ける。

  ソースコード

import math

def solve():
    N, M = map(int, input().split())
    D = list(map(int, input().split()))
    
    D.sort(reverse=True)
    
    # Binary search on the number of days
    lo, hi = 1, max(D)
    
    def check(days):
        # With `days` days and M workers per day, total work capacity = days * M
        # Each field i needs D[i] work, but also each field needs at least 1 day
        # (you can do at most D[i] work per day on field i... no, actually you can
        # assign all M workers to one field in one day)
        # 
        # The constraint is: each day, exactly M workers are distributed among fields.
        # A field i needs D[i] total work. In `days` days, each field can get at most
        # `days * M` work (if all workers go there every day), but the real constraint
        # is that the sum of workers assigned each day = M.
        #
        # Key insight: field i needs at least ceil(D[i] / M) days if we could assign
        # all M workers to it. But we need all fields done simultaneously.
        # 
        # Actually, the constraint is:
        # 1) days >= ceil(D_max / M) -- we can't finish the hardest field faster
        #    Wait no, we can assign fewer than M workers per day to a field.
        #    The hardest field needs D_max work. Even if we assign all M workers
        #    every day, it takes ceil(D_max / M) days.
        #    But we also need to handle other fields.
        #
        # With `days` days, total capacity = days * M.
        # We need sum(D) <= days * M (necessary condition).
        # Also, each field needs D[i] work done over `days` days where each day
        # it can receive between 0 and M workers.
        # So each field needs at most M work per day, meaning D[i] <= days * M 
        # for each field (but since days >= 1 and we binary search, this should hold).
        #
        # Actually the only constraint is:
        # - Total work needed: sum(D) <= days * M
        # - No single field requires more than days * M (i.e., D_max <= days * M)
        #   but since M >= 1, if days >= D_max this holds. 
        #
        # Wait, but each field needs D[i] work. We have days days. Each day we 
        # distribute M workers. The question is whether we can distribute M workers
        # across N fields over `days` days such that field i gets at least D[i] total.
        #
        # This is feasible if and only if:
        # 1) sum(D) <= days * M  (enough total capacity)
        # 2) max(D) <= days * M  (no single field needs more than total possible)
        #    But condition 2 is implied by condition 1 when N >= 1... no it's not.
        #    If N=1, both are the same. If N>1, condition 1 is stricter than condition 2
        #    only if sum > max, which is true when N>1 and all D>0.
        #
        # Hmm wait. Actually each day each field can get at most M workers.
        # So field i can get at most days * M over all days. But also, field i
        # can get at most M per day. The real constraint per field is D[i] <= days * M.
        # And the global constraint is sum(D[i]) <= days * M.
        # 
        # Since we can freely distribute M workers each day, as long as 
        # sum(D) <= days * M, we can achieve it. And D_max <= days * M is needed too,
        # but for N >= 1, if sum(D) <= days * M then D_max <= sum(D) <= days * M.
        #
        # So the answer is simply ceil(sum(D) / M).
        # But wait... what about D_max? If D_max > sum/N... no.
        # ceil(sum(D)/M) >= ceil(D_max/M) only if sum >= D_max, which is always true.
        # So the answer is ceil(sum(D) / M).
        
        total = sum(D)
        return days * M >= total
    
    # Actually, we also need days >= ceil(D_max / M)... no wait.
    # If D_max = 10^9, M = 1, N = 1, answer = 10^9 = ceil(10^9 / 1). Correct.
    # The answer is simply ceil(sum(D) / M).
    
    total = sum(D)
    ans = (total + M - 1) // M
    # But also need ans >= ceil(D_max / M) ... which is always <= ceil(sum/M).
    # Hmm, actually not. Consider D = [5, 1], M = 100. sum = 6, ceil(6/100)=1.
    # In 1 day, assign 5 to field 1, 1 to field 2, 94 wasted. Works! Answer = 1.
    print(ans)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。