概要

\(N\) 個の果樹園から \(K\) 日間かけて果物を収穫するとき、収穫量の合計を最大化する問題です。各果樹園には1日あたりの収穫上限があるため、どの果樹園をどの順番で何回選ぶかを最適に決める必要があります。

考察

各果樹園の収穫構造を理解する

果樹園 \(i\) には \(A_i\) 個の果物があり、1日に最大 \(B_i\) 個収穫できます。この果樹園を繰り返し選ぶと、収穫できる量は以下のようになります。

例: \(A_i = 13, B_i = 5\) の場合 - 1回目: \(\min(13, 5) = 5\) 個収穫（残り8個） - 2回目: \(\min(8, 5) = 5\) 個収穫（残り3個） - 3回目: \(\min(3, 5) = 3\) 個収穫（残り0個）

つまり、果樹園 \(i\) からは \(B_i\) 個を \(\lfloor A_i / B_i \rfloor\) 回、そして端数 \(A_i \bmod B_i\) 個を1回（端数が0でなければ）収穫できます。

「収穫スロット」として考える

各果樹園の収穫を独立したスロットに分解できます。果樹園 \(i\) は以下のスロット群を生成します： - 値 \(B_i\) のスロットが \(\lfloor A_i / B_i \rfloor\) 個 - 値 \(A_i \bmod B_i\) のスロットが1個（0でなければ）

全果樹園のスロットを合わせると、各スロットは「1日使って得られる収穫量」を表します。\(K\) 日間の収穫を最大化するには、全スロットの中から値の大きい順に \(K\) 個選べばよいのです。

素朴なアプローチの問題点

スロットの総数は最大 \(\sum (A_i / B_i + 1)\) で、\(A_i\) が \(10^9\), \(B_i\) が \(1\) の場合、\(10^9\) 個にもなります。全スロットを列挙してソートするのは不可能です。

二分探索で解決する

「値が \(t\) 以上のスロットの個数」は \(t\) に対して単調減少です。そこで、\(t\) を二分探索して「値 \(\geq t\) のスロットがちょうど \(K\) 個以上ある最大の \(t\)」を求めます。

値 \(t\) を固定したとき、果樹園 \(i\) について値 \(\geq t\) のスロットは： - \(B_i \geq t\) のとき：値 \(B_i\) のスロット \(\lfloor A_i / B_i \rfloor\) 個（すべて \(\geq t\)）と、端数 \(A_i \bmod B_i\) が \(\geq t\) なら1個 - \(B_i < t\) のとき：0個

これにより、\(O(N)\) で個数と合計値を計算できます。

最終的な答えの計算

二分探索で求めた閾値 \(t\) に対して、値 \(\geq t\) のスロットが \(\text{cnt}\) 個、その合計が \(s\) とします。\(\text{cnt} \geq K\) なので、余分な \(\text{cnt} - K\) 個を除く必要があります。除くのは値がちょうど \(t\) のスロット（最も小さいもの）なので：

\[\text{ans} = s - (\text{cnt} - K) \times t\]

アルゴリズム

1. 各果樹園 \((A_i, B_i)\) を読み込む。
2. 二分探索で、値 \(\geq t\) のスロット数が \(K\) 以上となる最大の \(t\) を求める。
3. その \(t\) に対してスロット数 \(\text{cnt}\) と合計値 \(s\) を計算する。
4. \(t = 0\) なら全果物を収穫可能（\(K\) が十分大きい）なので \(\sum A_i\) を出力。
5. そうでなければ \(s - (\text{cnt} - K) \times t\) を出力。

計算量

• 時間計算量: \(O(N \log(\max B_i))\)（二分探索が \(O(\log(\max B_i))\) 回、各回 \(O(N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• 二分探索の範囲は \([0, 10^9 + 1]\) とし、\(t = 0\) の場合（全スロットを使い切っても \(K\) 日に満たない場合）を特別に処理します。

• \(K\) が最大 \(10^{18}\) と非常に大きいため、スロットを全列挙する方法は不可能です。二分探索で \(O(N)\) の判定関数に帰着させることが本質です。

• count_and_sum 関数内で、\(B_i < t\) の果樹園はスロットが一つも \(t\) 以上にならないため、すぐにスキップできます。

  ソースコード

import sys
from sys import stdin

def solve():
    input_data = stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    A = []
    B = []
    for i in range(N):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        A.append(a)
        B.append(b)
    
    def count_and_sum(t):
        # Count slots with value >= t, and their total sum
        cnt = 0
        s = 0
        for i in range(N):
            if B[i] >= t:
                f = A[i] // B[i]
                p = A[i] % B[i]
                cnt += f
                s += f * B[i]
                if p >= t:
                    cnt += 1
                    s += p
        return cnt, s
    
    # Binary search for largest t where count >= K
    lo, hi = 0, 10**9 + 1
    while lo < hi:
        mid = (lo + hi + 1) // 2
        cnt, _ = count_and_sum(mid)
        if cnt >= K:
            lo = mid
        else:
            hi = mid - 1
    
    t = lo
    if t == 0:
        # All fruits can be harvested
        print(sum(A))
        return
    
    cnt, s = count_and_sum(t)
    # We have cnt slots with value >= t, summing to s
    # We only need K of them; drop (cnt - K) slots of value exactly t
    ans = s - (cnt - K) * t
    print(ans)

solve()

---

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