概要

各箱の「重さ \(W_i\)」と「耐荷重 \(D_i\)」から、潰れないように縦に積める箱の個数の最大値を求めます。
結論として、ある順で箱を見ていき「入れる／無理なら一番重い箱を捨てる」を繰り返す貪欲法で最大個数を求められます。

考察

重要な観察：条件は「上にある総重量」で決まる

箱を下から順に並べたとき、ある箱 \(i\) が潰れない条件は

• 「その箱より上にある箱の重さ合計」\(\le D_i\)

です。これを少し見方を変えると、箱 \(i\) 自身の重さも含めた「その箱より上＋自分」までの総重量を \(T\) とすると

• \(T \le W_i + D_i\)

となります。ここで \(W_i + D_i\) は「その箱が支えられる最大の総重量（自分込み）」なので、これを 強さ（strength） と呼びます。

つまり、下から順に見たとき「ここまでに積んだ総重量 \(T\) が、各箱の強さ \(S_i=W_i+D_i\) を超えない」ようにできればOKです。

素朴な方法が難しい理由

• どの箱を選ぶか（部分集合）と、どの順で積むか（順列）の両方を最適化する必要があります。
• 全探索は当然不可能で、DPも「総重量」が \(10^9\) なので重さDPは使えません。
• \(N \le 2\times 10^5\) のため、\(O(N^2)\) のような方法も間に合いません。

解決の方針：並べる順を固定して貪欲に「個数最大」を狙う

箱を 強さ \(S_i=W_i+D_i\) の昇順 に並べて考えます。この順で見ていくと、

• いままで選んだ箱たちの総重量を \(T\) とする
• 新しい箱（強さ \(S\)、重さ \(W\)）を追加して \(T+W \le S\) なら安全に「どこかに」積める可能性が保たれる

もし \(T+W > S\) となってしまったら、「今の集合の中から何かを捨てないと、この強さ \(S\) の箱を最下層側に含むような積み方は不可能」です。
個数を最大化したいので、捨てるなら総重量を一番減らせる 最も重い箱 を捨てるのが得です。

この「追加してダメなら最重箱を捨てる」を繰り返すと、各時点で - その時点までに見た箱だけで作れる「最大個数の集合」 を保ちながら進められます。

アルゴリズム

1. 各箱について強さ \(S_i = W_i + D_i\) を計算し、ペア \((S_i, W_i)\) を作る。
2. \((S_i)\) の昇順にソートする。
3. いま選んでいる箱の総重量 total と、選んでいる箱の重さを管理するヒープを用意する。
   • 「最も重い箱」をすぐ取り出したいので 最大ヒープ が欲しい（Pythonは最小ヒープなので負の値で代用）。
4. ソート順に箱を1つずつ処理：
   • とりあえず箱を採用：total += w、ヒープに -w を追加
   • もし total > S なら条件違反なので、ヒープから「最も重い箱」を1つ捨てる（total からその重さ分を引く）
5. 最後にヒープに残った個数が答え。

直感的な例

強さの小さい箱（\(W+D\) が小さい箱）は「上にあまり載せられない」ので下に置きにくく、先に処理して条件を守る必要があります。
途中で総重量がオーバーしたら、重い箱を捨てると総重量が一番減り、残せる箱数が増えやすい、という発想です。

計算量

• 時間計算量: \(O(N \log N)\)（ソート \(O(N\log N)\) ＋ 各箱でヒープ操作 \(O(\log N)\)）
• 空間計算量: \(O(N)\)（箱配列とヒープ）

実装のポイント

• 強さは \(S_i = W_i + D_i\)。この値で昇順ソートするのが核心です。

• Pythonの heapq は最小ヒープなので、最大値（最重箱）を取り出すために -w を入れます。

• total > S になったときに捨てるのは「必ず1個でよい」ことに注意：
  今回は「1個追加したことで超えた」状態なので、最大の重さを1つ捨てれば total は最も大きく減り、以後の処理に最適です。

  ソースコード

import sys
import heapq

def main():
    input = sys.stdin.readline
    N = int(input())
    boxes = []
    for _ in range(N):
        w, d = map(int, input().split())
        boxes.append((w + d, w))  # (strength, weight)

    boxes.sort()  # by strength ascending

    total = 0
    heap = []  # max-heap by weight via negative
    for s, w in boxes:
        total += w
        heapq.heappush(heap, -w)
        if total > s:
            total += heapq.heappop(heap)  # subtract largest weight

    print(len(heap))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。