概要

\(N\) 個の果樹園から \(K\) 日間、毎日 1 つを選んで収穫し、合計収穫量を最大化する問題です。各果樹園 \(i\) では 1 日に最大 \(B_i\) 個まで収穫でき、残りが \(B_i\) 未満になればその残りすべてを収穫します。

考察

収穫パターンの分解

ある果樹園 \(i\) （果物数 \(A_i\)、1日の上限 \(B_i\)）に注目すると、毎日その果樹園を選び続けた場合の収穫量は以下のようになります。 - \(B_i\) 個を \(d = \lfloor A_i / B_i \rfloor\) 回（\(d\) 日間） - 余りの \(r = A_i \bmod B_i\) 個を \(1\) 回（\(1\) 日間） - その後は \(0\) 個

例えば \(A_i = 25, B_i = 10\) の場合、収穫量は \(10, 10, 5, 0, 0, \dots\) と変化します。

貪欲法の適用

高橋君は合計 \(K\) 日間作業をします。全体の収穫量を最大化するには、「その日に収穫できる個数が最も多い果樹園」を優先的に選べばよい（貪欲法）ことがわかります。

なぜなら、ある日に収穫量 \(X\) を選べるのにあえて \(Y < X\) を選んだとしても、後で \(X\) を選ぶチャンスが残るだけであり、合計日数が限られている以上、大きい値から順に \(K\) 個分（\(K\) 日分）選ぶのが最適だからです。

効率的な計算

\(K\) が最大 \(10^{18}\) と非常に大きいため、1日ずつシミュレーションすることはできません。しかし、各果樹園からの収穫を「（収穫量, その収穫ができる日数）」というペアに分解すると、データ数は高々 \(2N\) 個になります。これらを収穫量が多い順にソートして、まとめて処理することで高速に計算可能です。

アルゴリズム

1. 各果樹園 \(i=1 \dots N\) について、以下の「収穫アイテム」を作成します。
   • 収穫量が \(B_i\) である日が \(A_i // B_i\) 日
   • 収穫量が \(A_i \% B_i\) である日が \(1\) 日（余りが \(0\) でない場合）
2. 作成したすべてのアイテムを、収穫量（1日あたりの個数）が大きい順にソートします。
3. 残りの作業日数 \(K\) を管理しながら、ソートした順にアイテムを見ていきます。
   • そのアイテムの「日数」が \(K\) 以下なら、その分すべてを合計収穫量に加え、\(K\) から日数を引きます。
   • そのアイテムの「日数」が \(K\) より大きいなら、\(K\) 日分だけ収穫して終了します。
4. 最終的な合計収穫量を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 各果樹園から最大 2 つのアイテムを作るのに \(O(N)\)。
  • アイテムのソートに \(O(N \log N)\)。
  • アイテムの走査に \(O(N)\)。
• 空間計算量: \(O(N)\)
  • アイテムを格納するリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな \(K\) への対応: \(K\) は \(10^{18}\) に達するため、ループではなく「現在のアイテムで何日間作業するか」を min(count, days_left) のように計算して一気に加算する必要があります。

• 余りの処理: \(A_i\) が \(B_i\) で割り切れる場合、余り \(0\) のアイテムは追加する必要がありません（収穫量に寄与しないため）。

• 高速な入出力: \(N\) が \(2 \times 10^5\) と多いため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、空白で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 果樹園の数, K: 作業日数
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 各果樹園について、1日あたりの収穫量とその収穫が可能な日数を計算する
    # 果樹園iでは、B_i 個を A_i // B_i 回収穫でき、
    # その後、余りの A_i % B_i 個を 1 回収穫できる
    items = []
    for i in range(N):
        A = int(input_data[2 + 2 * i])
        B = int(input_data[3 + 2 * i])
        
        d = A // B
        r = A % B
        
        if d > 0:
            items.append((B, d))
        if r > 0:
            items.append((r, 1))
            
    # 1日あたりの収穫量(value)が大きい順にソートする（貪欲法）
    items.sort(key=lambda x: x[0], reverse=True)
    
    total_harvest = 0
    days_left = K
    
    # 収穫量が多いものから順に、可能な限り日数(K)を割り当てる
    for value, count in items:
        if days_left <= 0:
            break
        
        # 現在の収穫量で作業する日数を決定
        take_days = count if count < days_left else days_left
        total_harvest += take_days * value
        days_left -= take_days
        
    # 合計収穫量を出力
    print(total_harvest)

if __name__ == '__main__':
    solve()

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