概要

\(N\) 本の果樹に合計 \(K\) 袋の肥料を分配し、成長度の積を最大化する問題。固定された総和のもとで積を最大化するには、各値をできるだけ均等にすればよいという性質を利用し、二分探索で最適な分配を求める。

考察

重要な気づき：積の最大化は「均等化」

相加平均・相乗平均の不等式（AM-GM不等式）から、和が一定のとき、積は各値ができるだけ等しいときに最大化されます。

例えば、\(A = [1, 5]\), \(K = 2\) のとき： - \((1+2) \times 5 = 15\)（小さい方に全部与える） - \((1+1) \times (5+1) = 12\)（均等に分ける） - \(1 \times (5+2) = 7\)（大きい方に全部与える）

最も値が近くなる分配が最大積を与えます。つまり、常に最も小さい値の木に肥料を与えるのが最適です。

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

\(K\) が最大 \(10^{18}\) と非常に大きいため、1袋ずつ分配するシミュレーションは不可能です。

解決策：二分探索で「水位」を決める

全ての木を「水位 \(V\)」まで引き上げるイメージで考えます。\(A_i < V\) の木は \(V\) まで引き上げ、\(A_i \geq V\) の木はそのまま。引き上げコストが \(K\) 以下となる最大の \(V\) を二分探索で求めます。

アルゴリズム

1. 配列をソート: \(A\) を昇順にソートする。

2. 二分探索で水位 \(V\) を決定:

   • 水位 \(V\) まで引き上げるコスト: \(\text{cost}(V) = \sum_{A_i < V} (V - A_i)\)
   • \(\text{cost}(V) \leq K\) を満たす最大の \(V\) を求める。
   • ソート済み配列と累積和を使えば \(O(\log N)\) でコスト計算可能。

3. 余りの分配:

   • \(\text{remaining} = K - \text{cost}(V)\) を計算。
   • \(A_i \leq V\) だった木は全て値 \(V\) になっている（\(\text{idx\_v}\) 本）。
   • 残りの肥料 \(\text{remaining}\) 袋をこれらの木に1袋ずつ配る（\(V+1\) になる木が \(\text{remaining}\) 本）。

4. 積の計算（mod \(10^9+7\)）:

   • \(V+1\) の木が \(\text{remaining}\) 本 → \((V+1)^{\text{remaining}} \mod p\)
   • \(V\) の木が \((\text{idx\_v} - \text{remaining})\) 本 → \(V^{(\text{idx\_v} - \text{remaining})} \mod p\)
   • それ以上の木は元の値 \(A_i\) をそのまま掛ける。

計算量

• 時間計算量: \(O(N \log N + N \log(\max(A) + K))\)
  • ソートに \(O(N \log N)\)、二分探索に \(O(\log(\max(A)+K))\)（各ステップで二分探索 \(O(\log N)\)）、最終計算に \(O(N)\)
• 空間計算量: \(O(N)\)（累積和の配列）

実装のポイント

• 二分探索の上界: \(V\) の上界は \(A[0] + K\)（\(N=1\) なら全て1本に与える場合）だが、\(K\) が \(10^{18}\) と大きいので lo, hi の範囲に注意。

• コスト計算の効率化: ソート済み配列で bisect_left を使い、\(V\) 未満の要素数と累積和から \(O(\log N)\) でコストを求める。

• remaining ≤ idx_v の保証: \(\text{cost}(V+1) > K\) であることから、余りは必ず水位 \(V\) にある木の本数以下になる（でないと全部 \(V+1\) に引き上げられてしまう）。

• mod 演算: 繰り返し二乗法（pow(base, exp, MOD)）を使って大きなべき乗を高速に計算する。

  ソースコード

import sys
import heapq

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i+2]) for i in range(N)]
    
    MOD = 10**9 + 7
    
    # Key insight: To maximize the product, we should always add fertilizer to the tree
    # with the smallest current growth value. This is because for fixed sum, the product
    # is maximized when values are as equal as possible.
    
    # Optimal strategy: sort A, then distribute K fertilizer bags to make values as equal as possible.
    # After optimal distribution, all values will be either floor(target) or ceil(target) for some target,
    # or more precisely, we level up from the smallest.
    
    A.sort()
    
    # We want to find the final value V such that all trees have value >= V,
    # and some might have V+1.
    # 
    # Strategy: binary search on the final "base level" V.
    # If all trees are raised to at least V, the cost is sum(max(0, V - A[i]) for all i).
    # If cost <= K, then we have leftover = K - cost, and we distribute leftover among N trees
    # (each getting +1), so `leftover` trees get V+1 and (N - leftover) trees get V.
    # But some trees might already be above V, those stay as they are.
    
    # More carefully: after raising all trees below V to V, trees already >= V stay unchanged.
    # Wait, no. We can only ADD fertilizer, not remove. So trees with A[i] > V stay at A[i].
    
    # Let's think again. We raise trees with A[i] < V to V. Trees with A[i] >= V stay at A[i].
    # Cost = sum(max(0, V - A[i])).
    # Then leftover K - cost is distributed one per tree to maximize product.
    # Best to add to trees with smallest values first, but all trees at level V are equal,
    # so we add 1 to any of them. Actually trees with A[i] > V also exist.
    # Hmm, but since we want max product, we should add +1 to trees with smallest current value.
    # After leveling to V, the smallest values are V (for those that were raised), 
    # and some A[i] >= V. So we add +1 to trees at value V first.
    
    # Binary search: find largest V such that cost(V) <= K
    # cost(V) = sum(max(0, V - A[i]) for i in range(N))
    
    # prefix sums for sorted A
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + A[i]
    
    def cost_to_level(V):
        # Number of trees below V: binary search
        import bisect
        idx = bisect.bisect_left(A, V)
        # cost = V * idx - prefix[idx]
        return V * idx - prefix[idx]
    
    import bisect
    
    # Binary search for V
    lo, hi = A[0], A[0] + K  # V can be at most A[0] + K (if N=1, but generally)
    # Actually hi can be very large. Let's think: max V is when all K go to raise minimum.
    # V can be at most A[0] + K but also limited by distribution among multiple trees.
    # Safe upper bound: A[-1] + K (more than enough)
    # But K can be 1e18, so hi can be ~2e18. That's fine for binary search.
    
    hi = A[0] + K  # if N=1
    if N > 1:
        hi = A[-1] + K  # safe upper bound
    
    while lo < hi:
        mid = (lo + hi + 1) // 2
        c = cost_to_level(mid)
        if c <= K:
            lo = mid
        else:
            hi = mid - 1
    
    V = lo
    remaining = K - cost_to_level(V)
    
    # Now: trees with A[i] < V are raised to V. Trees with A[i] >= V stay at A[i].
    # remaining fertilizer bags are distributed as +1 each.
    # To maximize product, +1 should go to trees with smallest value, i.e., those at V.
    # Count trees at value V (after leveling): all trees with original A[i] <= V become V.
    
    idx_v = bisect.bisect_right(A, V)  # trees with A[i] <= V: indices 0..idx_v-1, all at V
    # Trees at value V: idx_v of them
    # remaining <= idx_v (since cost(V+1) > K)
    # `remaining` of them become V+1, rest stay at V
    
    # Compute product mod MOD
    result = 1
    at_v = idx_v  # number of trees at level V
    plus_one = remaining  # how many get V+1
    stay = at_v - plus_one  # how many stay at V
    
    result = pow(V + 1, plus_one, MOD) * pow(V, stay, MOD) % MOD
    for i in range(idx_v, N):
        result = result * (A[i] % MOD) % MOD
    
    print(result % MOD)

solve()

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