概要

各木から複数回収穫できる条件下で、合計収穫回数が\(M\)回以下という制約のもと、収穫量の合計を最大化する問題です。

考察

各木\(i\)について、\(k\)回目の収穫量は\(\max(F_i - (k-1) \times D_i, 0)\)で計算されます。素朴なアプローチとしては、全ての木から得られる収穫量を降順に並べて上位\(M\)個を選ぶことが考えられます。しかし、各木から最大\(M\)回まで収穫可能で、木の数\(N\)も最大\(2 \times 10^5\)であるため、全ての収穫量を列挙すると最大\(N \times M = 4 \times 10^{10}\)個もの候補が発生し、計算量的に不可能です。

そこで、以下の2つの観察が重要になります： 1. 各木からの収穫量は等差数列的に減少する 2. 収穫量が大きいものから優先的に選ぶべき

これらの観察から、収穫量が大きい候補を効率的に管理するために、ヒープ（優先度付きキュー）を使用するアプローチが有効です。

アルゴリズム

1. 木を初回収穫量\(F_i\)の降順にソートする
2. 最小ヒープを用意し、現在の収穫量の合計とヒープのサイズ（収穫回数）を管理する
3. 各木について、収穫量が0より大きい間、収穫回数\(k\)を増やしながら以下の処理を行う：
   • 現在の収穫量を計算
   • ヒープのサイズが\(M\)未満なら、その収穫量をヒープに追加し合計に加算
   • ヒープが満杯（サイズ\(M\)）なら、ヒープの最小値と現在の収穫量を比較し、現在の値が大きい場合に最小値を置き換え
4. 最終的な合計収穫量を出力

このアプローチでは、各木からの収穫量を必要な分だけ生成しつつ、常に上位\(M\)個の最大収穫量を維持することができます。

計算量

• 時間計算量: \(O(N \log M + M \log M)\)
  • 木のソート: \(O(N \log N)\)
  • 各木の処理: 最悪ケースで\(O(M \log M)\)
  • 全体として\(O(N \log N + M \log M)\)ですが、\(N\)と\(M\)が同程度なので\(O(N \log N)\)と見なせます
• 空間計算量: \(O(M)\)
  • ヒープのサイズが最大\(M\)までとなるため

実装のポイント

• ヒープは最小ヒープを使用し、常に現在の最小収穫量を\(O(1)\)で参照可能にする
• heapreplace操作を用いることで、ヒープの最小値を効率的に置き換えられる
• 各木について、収穫量が0以下になった時点で処理を打ち切ることで無駄な計算を回避する
• 木を初回収穫量の降順にソートすることで、大きい収穫量から優先的に処理できる

ソースコード

import heapq

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    M = int(data[1])
    trees = []
    for i in range(n):
        F = int(data[2 + 2*i])
        D = int(data[3 + 2*i])
        trees.append((F, D))
    
    trees.sort(key=lambda x: x[0], reverse=True)
    
    heap = []
    total = 0
    for F, D in trees:
        k = 1
        while F > 0 and k <= M:
            current = F - (k-1)*D
            if current <= 0:
                break
            if len(heap) < M:
                heapq.heappush(heap, current)
                total += current
            else:
                if heap[0] < current:
                    total += current - heap[0]
                    heapq.heapreplace(heap, current)
                else:
                    break
            k += 1
    
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。