概要

\(M\) 回の収穫チャンスそれぞれで脚立の高さ以下にある果物を最大1つ収穫できるとき、おいしさの合計を最大化する問題です。貪欲法とヒープを用いて効率的に解けます。

考察

重要な気づき：収穫チャンスの順番は本質的でない

一見すると、チャンスが \(j = 1, 2, \ldots, M\) の順に行われるため順序が重要に思えますが、実は どの果物をどの脚立で収穫するかという「割り当て」だけが重要 です。

例えば、\(L = [3, 5, 2]\) の場合を考えます。高さ2の果物を3回目のチャンス（脚立高さ2）で取り、高さ4の果物を2回目のチャンス（脚立高さ5）で取る、という割り当ては有効です。つまり、各脚立に対して「高さが脚立以下の果物を高々1つ割り当てる」という条件を満たせばよいのです。

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

全ての割り当てを試すと組合せ爆発します。\(N, M\) が最大 \(2 \times 10^5\) なので、\(O(NM)\) でも間に合わない可能性があります。

解決策：ソート＋貪欲法

脚立の高さを 昇順にソート して、小さい脚立から順に処理します。各脚立について、手が届く果物の中から 最もおいしいもの を選びます。

なぜこれが最適か（交換論法）： - 小さい脚立で届く果物は、大きい脚立でも必ず届く - したがって、小さい脚立で「もったいないから取らない」という判断は不要で、取れる中で一番おいしいものを取るのが最善 - もし最適解が別の割り当てだとしても、交換によってこの貪欲解と同じかそれ以下の値になることが示せる

アルゴリズム

1. 果物を高さ \(D_i\) の昇順にソートする
2. 脚立の高さ \(L_j\) を昇順にソートする
3. 最大ヒープ（優先度付きキュー）を用意する
4. ソート済みの脚立を小さい方から順に処理する：
   • その脚立の高さ以下にある未追加の果物をすべてヒープに追加する
   • ヒープが空でなければ、最もおいしさが大きい果物を取り出し、合計に加算する
5. 合計を出力する

具体例

果物: (高さ2, おいしさ10), (高さ3, おいしさ5), (高さ5, おいしさ8) 脚立（ソート済み）: [2, 4, 5]

• 脚立2: 高さ≤2の果物 → {おいしさ10} をヒープに追加 → 10を取得
• 脚立4: 高さ≤4の果物 → {おいしさ5} を追加 → 5を取得
• 脚立5: 高さ≤5の果物 → {おいしさ8} を追加 → 8を取得

合計: \(10 + 5 + 8 = 23\)

計算量

• 時間計算量: \(O(N \log N + M \log M + (N + M) \log N)\)
  • 果物のソート: \(O(N \log N)\)
  • 脚立のソート: \(O(M \log M)\)
  • ヒープ操作: 各果物は高々1回 push/pop されるので \(O(N \log N)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• Python では最大ヒープがないため、値を負にして heapq（最小ヒープ）を使う

• 果物のポインタ fruit_idx を使い、ソート済み果物を先頭から順にヒープへ追加することで、各脚立に対して届く果物を効率的に管理する

• sys.stdin.buffer.read() で入力を一括読み込みし、高速化している

  ソースコード

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    fruits = []
    for i in range(N):
        D = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        fruits.append((D, V))
    
    L = []
    for j in range(M):
        L.append(int(input_data[idx])); idx += 1
    
    # Sort fruits by height
    fruits.sort(key=lambda x: x[0])
    
    # Sort chances by L value
    sorted_L = sorted(L)
    
    # Greedy: process chances from smallest L to largest
    # For each chance, add all fruits with D <= L to max-heap, pick the best
    max_heap = []  # store negative values for max-heap
    fruit_idx = 0
    total = 0
    
    for l in sorted_L:
        # Add all fruits reachable with this ladder height
        while fruit_idx < N and fruits[fruit_idx][0] <= l:
            heapq.heappush(max_heap, -fruits[fruit_idx][1])
            fruit_idx += 1
        
        # Pick the most valuable fruit if available
        if max_heap:
            total += -heapq.heappop(max_heap)
    
    print(total)

main()

---

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