概要

\(N\) 種類の果物の木から、合計 \(M\) 回以内の収穫で得られる果物の合計量を最大化する問題です。各木は収穫するたびに収穫量が \(D_i\) ずつ減少するため、常に「その時点で最も収穫量が多い木」を選んで収穫するのが最適です。

考察

貪欲な選択

収穫量を最大化するためには、全 \(N\) 種類の木から得られる「各回の収穫量」をすべて並べ、その中から値が大きい順に最大 \(M\) 個選ぶのが最適です。

素朴なアプローチとその限界

優先度付きキュー（Heap）を用いて、常に現在の最大収穫量を持つ木から収穫し、収穫量を更新して再びキューに入れるという操作を \(M\) 回繰り返す方法が考えられます。 しかし、この方法の計算量は \(O(M \log N)\) となります。本問題の制約では \(M\) が最大 \(2 \times 10^5\) であるため、Pythonなどの言語では実行時間制限に間に合わない可能性があります（また、もし \(M\) がさらに大きい場合には通用しません）。

境界値（しきい値）の二分探索

「収穫量が \(X\) 以上のものはすべて収穫する」という戦略を考えます。 ある値 \(X\) を決めたとき、木 \(i\) から収穫量が \(X\) 以上となる回数 \(k_i\) は、以下のように \(O(1)\) で計算できます。

• \(F_i - (k_i - 1) \times D_i \geq X\)
• \((k_i - 1) \times D_i \leq F_i - X\)
• \(k_i \leq \frac{F_i - X}{D_i} + 1\)
• よって、\(k_i = \max(0, \lfloor \frac{F_i - X}{D_i} \rfloor + 1)\) です（ただし \(F_i \geq X\) の場合）。

\(X\) が大きければ収穫回数の合計は減り、\(X\) が小さければ収穫回数は増えます。この単調性を利用して、「収穫回数の合計が \(M\) 回以下となる最小のしきい値 \(X\)」を二分探索で求めることができます。

アルゴリズム

1. 二分探索による \(X\) の特定

   • 収穫量のしきい値 \(X\) を \([1, 10^9+7]\) の範囲で二分探索します。
   • 各 \(X\) について、全種類の木での「収穫量が \(X\) 以上となる収穫回数」の合計 \(cnt\) を計算します。
   • \(cnt \leq M\) ならば、その \(X\) は条件を満たすため、さらに小さい \(X\) を探索します。

2. 合計収穫量の計算

   • 求めた \(X\) を用いて、各木から収穫量が \(X\) 以上となる分をすべて合計します。
   • 木 \(i\) から \(k_i\) 回収穫する場合、その合計は初項 \(F_i\)、公差 \(-D_i\)、項数 \(k_i\) の等差数列の和として計算できます。
     • \(Sum_i = \frac{k_i}{2} \times \{2F_i - (k_i - 1)D_i\}\)

3. 端数の処理

   • 全ての「収穫量 \(\geq X\)」のものを合計しても、収穫回数の合計が \(M\) に満たない場合があります。
   • このとき、残りの収穫回数分だけ、収穫量 \(X-1\) の果物を得ることができます（\(X-1 > 0\) の場合のみ）。

計算量

• 時間計算量: \(O(N \log (\max F_i))\)
  • 二分探索の反復回数は \(\log(10^9) \approx 30\) 回です。
  • 各反復で \(N\) 種類の木を走査するため、全体で \(O(N \log (\max F_i))\) となります。
• 空間計算量: \(O(N)\)
  • 木の情報を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 等差数列の和: 収穫量が \(0\) 未満にならないよう、計算前に \(k_i\) の値を適切に制限する必要があります（今回の二分探索では \(X \geq 1\) としているため、自然に \(0\) 以上の収穫のみがカウントされます）。
• 高速な入出力: \(N\) が大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。
• オーバーフロー: 合計値は非常に大きな値になる可能性がありますが、Pythonは標準で多倍長整数を扱うため、特段のケアは不要です。

ソースコード

import sys

def solve():
    # Use fast I/O to read all data at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of tree types, M: maximum total harvests
    N = int(input_data[0])
    M = int(input_data[1])
    
    # Efficiently extract F (initial yield) and D (decrease rate)
    F = list(map(int, input_data[2::2]))
    D = list(map(int, input_data[3::2]))
    FD = list(zip(F, D))
    
    # Binary search for the threshold value X.
    # We want the smallest yield value X >= 1 such that the total number of
    # harvests with yield >= X is at most M.
    # If the total number of harvests with yield >= 1 is less than or equal to M,
    # then X will be 1.
    ng = 0
    ok = 10**9 + 7 # A value larger than any possible initial yield
    
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for f, d in FD:
            if f >= mid:
                # Number of harvests with yield >= mid for this tree
                cnt += (f - mid) // d + 1
                # Early break if we already exceeded M
                if cnt > M:
                    break
        if cnt <= M:
            ok = mid
        else:
            ng = mid
    
    # X is the threshold yield. We take all harvests with yield >= X.
    X = ok
    total_cnt = 0
    total_sum = 0
    
    for f, d in FD:
        if f >= X:
            # Number of harvests for this tree with yield >= X
            k = (f - X) // d + 1
            total_cnt += k
            # Sum of an arithmetic progression: (k/2) * (2*first_term - (k-1)*common_difference)
            total_sum += k * (2 * f - (k - 1) * d) // 2
            
    # If the number of harvests with yield >= X is less than M,
    # we fill the remaining harvests using the next best yield value (X-1).
    # We only care if X-1 is greater than 0.
    if X > 1:
        remaining = M - total_cnt
        # There are enough harvests with yield X-1 because count(X-1) > M
        # (due to the binary search property).
        total_sum += remaining * (X - 1)
        
    # Output the maximum possible total fruits
    sys.stdout.write(str(total_sum) + '\n')

if __name__ == '__main__':
    solve()

---

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