概要

\(N\) 種類の果物の木から合計 \(M\) 回以下の収穫を行い、得られる果物の総数を最大化する問題です。各木は収穫するたびに収穫量が減少するため、毎回「最も多く収穫できる木」から貪欲に収穫するのが最適です。

考察

重要な気づき：貪欲法が最適

各収穫は独立に「今この瞬間、どの木から収穫すれば最も多くの果物が得られるか」を考えればよいです。なぜなら、ある木から \(k\) 回目に得られる果物の数は \(\max(F_i - (k-1) \times D_i, \ 0)\) と決まっており、収穫の順番を変えても各木から得られる量の列は変わらないからです。

例えば、木 A の収穫量が \([10, 7, 4, 1]\)、木 B の収穫量が \([8, 3]\) のとき、合計 \(M = 3\) 回収穫するなら、全候補 \(\{10, 8, 7, 4, 3, 1\}\) の中から大きい順に \(10, 8, 7\) を選ぶのが最適です。

素朴なアプローチの問題

全ての木の全収穫候補を列挙してソートする方法は、木ごとの収穫可能回数が非常に大きくなり得るため（\(F_i / D_i\) が最大 \(10^9\)）、メモリ・時間ともに不可能です。

解決策：優先度付きキュー（ヒープ）

全候補を列挙する代わりに、各木の「次に収穫したときの収穫量」だけをヒープで管理します。最大値を取り出したら、その木の次回の収穫量をヒープに戻す、という操作を最大 \(M\) 回繰り返します。これにより、必要な分だけ効率的に処理できます。

アルゴリズム

1. 初期化: 各木 \(i\) について、初回収穫量 \(F_i > 0\) ならば \(F_i\) を最大ヒープに挿入する（Python では最小ヒープなので \(-F_i\) を入れる）。
2. 貪欲に \(M\) 回収穫:
   • ヒープから最大値 \(v\) を取り出す。
   • \(v \leq 0\) ならこれ以上収穫しても意味がないので終了。
   • \(v\) を合計に加算する。
   • その木の次回収穫量 \(v - D_i\) が正なら、ヒープに戻す。
3. 合計値を出力する。

具体例

\(N=2, M=3\)、木1: \((F_1, D_1) = (10, 3)\)、木2: \((F_2, D_2) = (8, 5)\) の場合：

収穫回	ヒープの状態	選択	次回値
1回目	\(\{10, 8\}\)	10（木1）	\(10 - 3 = 7\)
2回目	\(\{8, 7\}\)	8（木2）	\(8 - 5 = 3\)
3回目	\(\{7, 3\}\)	7（木1）	\(7 - 3 = 4\)

合計: \(10 + 8 + 7 = 25\)

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 初期ヒープ構築に \(O(N \log N)\)、最大 \(M\) 回のヒープ操作に \(O(M \log N)\)。
• 空間計算量: \(O(N)\)
  • ヒープには各木の「次の収穫量」が高々 \(N\) 個入る。

実装のポイント

• Python のヒープは最小ヒープなので、値を負にして格納することで最大ヒープとして利用しています。
• 収穫量が \(0\) 以下になった木はヒープに戻さないことで、無駄な操作を省いています。
• ヒープが空になった場合（全ての木の収穫量が \(0\) になった場合）は \(M\) 回に達する前でもループを終了します。
• 入力を sys.stdin.buffer.read() でまとめて読み込むことで、大量入力時の速度を確保しています。

ソースコード

import heapq

def solve():
    import sys
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    # Use a max-heap (negate values for Python's min-heap)
    # Each entry: (-current_yield, F_i, D_i, k) where k is the next harvest number (1-indexed)
    # yield for k-th harvest = max(F_i - (k-1)*D_i, 0)
    
    heap = []
    for i in range(N):
        F = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        if F > 0:
            heapq.heappush(heap, (-F, F, D))
    
    total = 0
    for _ in range(M):
        if not heap:
            break
        neg_val, F, D = heapq.heappop(heap)
        val = -neg_val
        if val <= 0:
            break
        total += val
        # Next harvest from this tree: val - D
        next_val = val - D
        if next_val > 0:
            heapq.heappush(heap, (-next_val, F, D))
    
    print(total)

solve()

---

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