概要

この問題は、果樹の成長度の積を最大化するために、合計 \(K\) 袋の肥料をどのように配分すればよいかを決定する問題です。

「全体の積を最大化するには、成長度の低い果樹を優先的に底上げし、全体の値をできるだけ均等に近づけるのが最適である」という性質（相加相乗平均の直感的な性質）を利用します。\(K\) が非常に大きいため、二分探索を用いて高速に最終的な成長度の下限値を求めます。

考察

1. 積を最大化するための最適な戦略

2つの変数 \(x, y\) の和が一定（\(x + y = S\)）のとき、その積 \(xy\) は \(x\) と \(y\) の差が小さいほど（つまり、できるだけ均等に近いほど）大きくなります。 この性質は変数が \(N\) 個になっても同様です。したがって、肥料を配分する際は「現在最も成長度が低い果樹に肥料を与えて、全体の底上げを図る」という貪欲法が最適になります。

2. 単純なシミュレーションの限界

「最も成長度が低い果樹に肥料を1袋ずつ与える」という操作を \(K\) 回繰り返せば最適解が得られますが、制約を見ると \(K \le 10^{18}\) です。1袋ずつシミュレーションしていては実行時間制限（TLE）に間に合いません。

3. 二分探索による高速化

そこで、「すべての果樹の成長度を \(X\) 以上にすることができるか？」という判定問題を考えます。

成長度が \(X\) 未満の果樹をすべて \(X\) にするために必要な肥料の総数は、 $\( \sum_{A_i < X} (X - A_i) \)\( となります。この必要な肥料の総数が \)K\( 以下であれば、すべての果樹の成長度を \)X$ 以上にすることが可能です。

この必要量は \(X\) に対して単調に増加するため、二分探索を用いて「すべての果樹の成長度を \(X\) 以上にできる最大の \(X\)」を高速に求めることができます。

アルゴリズム

1. ソートと累積和の準備 果樹の初期の成長度 \(A\) を昇順にソートします。 また、ある値 \(X\) 未満の要素の総和を高速に求めるために、累積和配列 pref を作成しておきます。

2. 二分探索による下限値 \(X\) の決定 「すべての果樹の成長度を \(X\) 以上にできるか」を判定する関数 check(X) を実装します。

   • 二分探索（bisect_left）を使い、\(A_i < X\) となる果樹の個数 idx を求めます。
   • それらの果樹をすべて \(X\) にするために必要な肥料の量は idx * X - pref[idx] と計算できます。
   • これが \(K\) 以下であれば True、そうでなければ False を返します。

この判定関数を用いて、二分探索により実現可能な最大の \(X\) を求めます。

1. 余った肥料の分配と最終的な積の計算 すべての果樹を \(X\) 以上にした後、まだ肥料が rem = K - (必要な肥料) 袋残っている可能性があります。 この残った rem 袋は、成長度が \(X\) になった果樹たちに1袋ずつ配分することで、それらの成長度を \(X+1\) に引き上げます。

最終的な果樹の成長度は以下のようになります： - もともと \(X\) 以下だった果樹（\(C\) 本とする）のうち、rem 本は \(X+1\) になり、残りの \(C - rem\) 本は \(X\) になる。 - もともと \(X\) より大きかった果樹は、初期値のまま変化しない。

これらすべての積を \(10^9 + 7\) で割った余りを累積的に計算して出力します。

計算量

• 時間計算量: \(O(N \log N + \log N \log(\max A_i + K))\)

  • 初期配列のソートに \(O(N \log N)\) かかります。
  • 二分探索の判定回数は \(O(\log(\max A_i + K))\) 回であり、各判定において bisect_left を行うため \(O(\log N)\) かかります。
  • 最後の積の計算は \(O(N + \log K)\) です。
  • 全体として、制限時間内に余裕で間に合います。

• 空間計算量: \(O(N)\)

  • ソートされた配列 \(A\) と累積和配列 pref を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 真の値での判定: 最大化の判定は \(10^9+7\) で割る前の真の値で行う必要があります。そのため、二分探索の最中は MOD による余りを取らずに計算を行います。

• bisect_left と bisect_right の使い分け:

  • bisect_left(A, X): \(X\) 未満の要素の個数（底上げが必要な果樹の数）を求めるために使用します。

  • bisect_right(A, X): \(X\) 以下の要素の個数（底上げされて成長度が \(X\) になった果樹の総数 \(C\)）を求めるために使用します。

    ソースコード

import sys
from bisect import bisect_left, bisect_right

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]
    A.sort()
    
    pref = [0] * (N + 1)
    for i in range(N):
        pref[i+1] = pref[i] + A[i]
        
    def check(X):
        idx = bisect_left(A, X)
        cost = idx * X - pref[idx]
        return cost <= K

    ok = 1
    ng = 10**9 + K + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
            
    X = ok
    idx = bisect_left(A, X)
    cost = idx * X - pref[idx]
    rem = K - cost
    
    C = bisect_right(A, X)
    
    MOD = 10**9 + 7
    
    ans = pow(X + 1, rem, MOD) * pow(X, C - rem, MOD) % MOD
    
    for i in range(C, N):
        ans = ans * A[i] % MOD
        
    print(ans)

if __name__ == '__main__':
    solve()

---

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