概要

\(N\) 個の段ボール箱から、耐荷重制限を守りつつ積み上げられる最大個数を求める問題です。箱の選び方と積み上げ順の両方を最適化する必要があります。

考察

最適な積み上げ順序の発見

まず「箱の集合が決まったとき、どの順番で積めばよいか」を考えます。

ある箱 \(i\) が潰れない条件は「箱 \(i\) より上にある箱の重さの合計 \(\leq D_i\)」です。箱 \(i\) が位置する場所より上の重さを \(U_i\) とすると、\(U_i \leq D_i\) が必要です。

隣り合う2つの箱の交換議論（Exchange Argument） を行います。箱 \(A\)（重さ \(W_A\), 耐荷重 \(D_A\)）の上に箱 \(B\)（重さ \(W_B\), 耐荷重 \(D_B\)）が乗っている状況を考えます。箱 \(A\) の上の荷重は \(W_B + X\)（\(X\) は \(B\) より上の重さ）、箱 \(B\) の上の荷重は \(X\) です。

• この順（\(A\) が下）: \(W_B + X \leq D_A\) かつ \(X \leq D_B\)
• 逆順（\(B\) が下）: \(W_A + X \leq D_B\) かつ \(X \leq D_A\)

\(A\) を下にする方が有利な条件を整理すると、\(W_A + D_A \geq W_B + D_B\) のとき \(A\) を下に置くべきだと分かります。つまり \(W_i + D_i\) が大きい箱ほど下に置く（\(W_i + D_i\) の昇順で上から下へ＝昇順で上から並べる）のが最適です。

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

\(N\) 個から部分集合を全探索すると \(O(2^N)\) で、\(N \leq 2 \times 10^5\) では到底間に合いません。

貪欲法による解決

\(W_i + D_i\) の昇順にソートし、箱を順番に見ていきます。ソート順で \(k\) 番目の箱が「今選んでいる箱の中で最も \(W+D\) が大きい」ため、この箱が一番下に来ます。一番下の箱の制約は「選んだ箱の重さの合計 \(\leq W_k + D_k\)」（上に乗る重さ＝合計 \(- W_k \leq D_k\)、すなわち合計 \(\leq W_k + D_k\)）です。この制約さえ満たせば、\(W+D\) がより小さい箱はそれ以上の余裕があるので自動的に満たされます。

制約を超えた場合は、今まで選んだ箱の中で最も重い箱を取り除くことで、重さの合計を最大限減らし、個数のロスを最小限にできます。

アルゴリズム

1. 箱を \(W_i + D_i\) の昇順にソートする。
2. 最大ヒープ（選んだ箱の重さを管理）と、選んだ箱の重さの合計 \(\text{total\_w}\) を用意する。
3. ソート順に各箱 \((W_i, D_i)\) を処理する：
   • 箱をヒープに追加し、\(\text{total\_w}\) に \(W_i\) を加える。
   • もし \(\text{total\_w} > W_i + D_i\) なら、ヒープから最も重い箱を取り出し、\(\text{total\_w}\) から引く。
4. 最終的なヒープの要素数が答え。

具体例: 箱が \((W=3, D=1), (W=1, D=3), (W=2, D=2)\) の場合、\(W+D\) は \(4, 4, 4\)。順に追加していき、合計が \(W+D\) を超えたら最重の箱を除去します。

計算量

• 時間計算量: \(O(N \log N)\)（ソートとヒープ操作）
• 空間計算量: \(O(N)\)（ヒープの保持）

実装のポイント

• Python の heapq は最小ヒープなので、重さの符号を反転して格納することで最大ヒープとして使う。

• 箱を追加した直後に制約違反をチェックし、違反時は最重の箱を1つだけ除去すれば十分。追加した箱自身が最重なら、それが除去されることもある（その箱を選ばない方が良い場合に対応）。

• \(W+D\) の昇順ソートにより、現在処理中の箱が常にボトルネック（一番下）になるため、この箱の制約だけ確認すればよい点が鍵。

  ソースコード

import heapq

def solve():
    import sys
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    boxes = []
    for i in range(N):
        w = int(input_data[idx]); idx += 1
        d = int(input_data[idx]); idx += 1
        boxes.append((w, d))
    
    # Greedy approach:
    # Sort by W_i + D_i in ascending order.
    # This is the classic "scheduling" style greedy for stacking problems.
    # 
    # Key insight: If we place boxes in order of increasing (W_i + D_i) from bottom to top,
    # this is optimal. W_i + D_i represents the maximum total weight (including itself)
    # that can be at or below this box's position.
    #
    # We greedily pick boxes sorted by W+D ascending. We maintain a max-heap of weights
    # of selected boxes. For each box, we add it. If the current total weight minus
    # the top box's own weight exceeds its durability (i.e., the stack isn't feasible),
    # we check if removing the heaviest box helps - effectively we simulate and remove
    # the heaviest selected box if it improves things.
    #
    # Actually, let me think more carefully. The condition for a valid stacking when
    # sorted by W+D ascending (placed bottom to top) is:
    # For box at position k (0-indexed from bottom), the weight above it = sum of W of boxes above.
    # 
    # Greedy: sort by W+D ascending. Process in this order (bottom to top placement).
    # Maintain selected set. Add current box. If total weight of selected exceeds
    # current box's W+D (since current box is the one with largest W+D so far, and
    # the total weight on top of it is totalW - W_current, we need totalW - W_current <= D_current,
    # i.e., totalW <= W_current + D_current), then we need to remove some box to reduce total weight.
    # Remove the heaviest box from selected set.
    
    boxes.sort(key=lambda x: x[0] + x[1])
    
    max_heap = []  # max-heap using negative values
    total_w = 0
    
    for w, d in boxes:
        heapq.heappush(max_heap, -w)
        total_w += w
        
        # Check if current box (which has the largest W+D so far) is okay
        # All boxes below have W+D <= current W+D, so if current is satisfied, all are.
        # Condition: total_w <= w + d  (i.e., weight above current = total_w - w <= d)
        # But wait, current box is placed at bottom? No, sorted by W+D ascending means
        # the first processed box goes to bottom, last to top. So the current box is 
        # the topmost? No...
        # 
        # Actually when sorted by W+D ascending, the optimal arrangement places the 
        # box with smallest W+D at the top (it can bear the least total), and largest 
        # W+D at the bottom. Wait, let me reconsider.
        #
        # For the box with the largest W+D, it should be at the bottom because it can
        # handle the most weight above. So sort ascending = bottom to top means smallest
        # W+D at bottom, which seems wrong.
        #
        # The standard result: sort by W+D ascending, and the constraint for the i-th 
        # box in this sorted order (0-indexed) placed from bottom to top is that 
        # the sum of weights of boxes ABOVE it <= D_i. The critical constraint is 
        # actually on the last (topmost in terms of processing) = the box with largest W+D
        # being at the bottom. Hmm, I think the sort should give bottom = largest W+D.
        #
        # Let me just use the greedy: sort by W+D ascending, and for each box in order,
        # add it, and if total_w > (w+d) of current box, remove heaviest. This is a 
        # known correct greedy for this type of problem.
        
        if total_w > w + d:
            heaviest = -heapq.heappop(max_heap)
            total_w -= heaviest
    
    print(len(max_heap))

solve()

---

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