概要

\(N\) 個の段ボール箱から、耐荷重の制限（その箱より上にある箱の重さの合計 \(\leq\) 耐荷重）を守りつつ、できるだけ多くの箱を積み上げる問題です。 箱を積む最適な順番を考えた上で、優先度付きキュー（ヒープ）を用いた強欲法（Greedy）で解くことができます。

考察

1. 箱を積む順番の最適化

まず、ある選ばれた箱の集合 \(S\) を積むとき、どのような順番で積むのが最も有利かを考えます。 2つの箱 \(i\) と \(j\) が隣り合って積まれている状況を想定します（\(i\) が上、\(j\) が下）。 このとき、成立条件は以下のようになります。 - 箱 \(i\) について：(箱 \(i\) より上の重さ合計) \(\leq D_i\) - 箱 \(j\) について：(箱 \(i\) より上の重さ合計) \(+ W_i \leq D_j\)

ここで、\(i\) と \(j\) を入れ替えたときに条件がより厳しくならない（＝入れ替えるメリットがない）条件を求めると、\(W_i + D_i \leq W_j + D_j\) という関係が導き出せます。 つまり、「重さ \(W\) と耐荷重 \(D\) の和」が小さいものほど上に、大きいものほど下に置くのが、最も崩れにくい積み方になります。

2. どの箱を選ぶか（強欲法）

箱を \(W_i + D_i\) の昇順にソートし、上から順に積んでいくことを検討します。 しかし、単純に「積めるなら積む」だけでは、後の重い箱のせいでそれ以降の箱が積めなくなる可能性があります。

そこで、以下の戦略をとります。 - 現在の合計重さを current_total_weight とします。 - 箱 \(i\) を一番下に置けるか判定します（current_total_weight <= D_i）。 - 置ける場合： そのまま積み上げます。 - 置けない場合： これまでに積み上げた箱の中で最も重い箱と、現在の箱 \(i\) を比較します。もし現在の箱の方が軽ければ、最も重い箱を捨てて現在の箱に入れ替えます。

この入れ替えを行っても、箱の総数は変わりませんが、合計重さが減少するため、将来的に他の箱を積み上げられる可能性が高まります。また、ソート順によりこの入れ替えは常に安全に行えます。

アルゴリズム

1. 各段ボール箱を \(W_i + D_i\) の昇順にソートします。
2. 現在積み上げている箱の重さを管理する最大ヒープ（Pythonでは heapq を使い、値を負にして管理）を用意します。
3. ソートした箱を一つずつ確認します：
   • 現在の合計重さ <= D_i ならば：
     • 箱 \(i\) をヒープに追加し、合計重さに \(W_i\) を加える。
   • そうでない（積めない）が、ヒープ内の最大重さ > W_i ならば：
     • 最大重さの箱を取り除き、代わりに \(W_i\) をヒープに追加する。
     • 合計重さを更新する（-最大重さ + W_i）。
4. 最終的なヒープのサイズが、積み上げられた箱の最大個数となります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 箱のソートに \(O(N \log N)\) かかります。
  • 各箱についてヒープの操作（挿入・削除）を最大1回行うため、全体で \(O(N \log N)\) です。
• 空間計算量: \(O(N)\)
  • 入力データとヒープを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• Pythonの heapq は最小ヒープ（一番小さい値を取り出す）であるため、最大ヒープとして使うには重さを負の値にして格納する必要があります。

• \(N\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.read().split() を使って高速に入力を読み込むのが効率的です。

  ソースコード

import sys
import heapq

def solve():
    # 高速な入出力のために、すべての入力を一度に読み込みます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 段ボール箱の個数 N
    N = int(input_data[0])
    
    # 各段ボール箱の重さ W と耐荷重 D を取得します。
    # 重さ W と耐荷重 D の和 (W + D) を「期限」と見なすことができます。
    boxes = []
    for i in range(N):
        w = int(input_data[2*i + 1])
        d = int(input_data[2*i + 2])
        boxes.append((w, d))
    
    # 段ボール箱を (W + D) の昇順でソートします。
    # これは、ある集合の箱を積むとき、(W + D) が小さい箱ほど上に、
    # 大きい箱ほど下に配置するのが最適（条件を満たしやすい）だからです。
    boxes.sort(key=lambda x: x[0] + x[1])
    
    # 現在選んでいる段ボール箱の重さのリストを保持するための最大ヒープ。
    # Pythonのheapqは最小ヒープなので、重さを負の値にして格納します。
    pq = []
    # 現在積み上げている段ボール箱の重さの合計。
    current_total_weight = 0
    
    for w, d in boxes:
        # 現在の合計重さが、新しく追加しようとしている段ボール箱の耐荷重以下であれば、
        # その箱を一番下に置くことができます。
        if current_total_weight <= d:
            heapq.heappush(pq, -w)
            current_total_weight += w
        # もし追加できない場合でも、現在選んでいる箱の中に、
        # 今見ている箱よりも重いものがあれば、それを差し替えることで
        # 合計重さを減らすことができます（箱の数は変わりません）。
        # (W + D) の昇順で処理しているため、差し替えても条件は維持されます。
        elif pq and -pq[0] > w:
            # ヒープの最小値（負の重さの最小値 ＝ 実際の最大重さ）を取り出し、
            # 新しい箱の重さと入れ替えます。
            heaviest_w_neg = heapq.heapreplace(pq, -w)
            current_total_weight += heaviest_w_neg + w
            
    # 選ばれた段ボール箱の個数（ヒープのサイズ）を出力します。
    print(len(pq))

if __name__ == '__main__':
    solve()

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