Day 096-Q3 | セグメント木で高速化した First-Fit-Decreasing

問題

$N$ 個の荷物があり、$i$ 番目の荷物のサイズは $w_i$ である。容量 $C$ のビン（箱）を必要なだけ用意し、すべての荷物をどれかのビンに詰める。1つのビンに詰めた荷物のサイズの合計はビンの容量 $C$ を超えてはならない。

このビンパッキング問題は NP困難であるため、厳密な最小ビン数の代わりにFirst-Fit-Decreasing（FFD）法による近似解を求めよ。手順: (1) 荷物をサイズの降順に並べ替える。(2) 既に開いているビンのうち最も早く作られたものでその荷物が収まるものがあれば詰める。(3) どのビンにも収まらなければ新しいビンを開けて詰める。

$N$ が大きい場合に各荷物ごとに全ビンを線形走査すると悪化するため、セグメント木上の二分探索で「残容量が $w_i$ 以上であるような最も先頭のビン」を $O(\log N)$ で見つけて処理せよ。使用したビンの総数を出力せよ。

入力形式

N C
w_1 w_2 ... w_N

制約

$1 \le N \le 2\times10^5$

$1 \le C \le 10^9$

$1 \le w_i \le C$

入出力例

入力例1

6 10
6 5 4 3 2 2

出力例1

降順ソート後 `6 5 4 3 2 2`。ビン1(容量10)に6→残4。5はビン1不可、新規ビン2へ→残5。4はビン1(残4)へ→残0。3はビン2(残5)へ→残2。2はビン2(残2)へ→残0。最後の2はどちらも不可なので新規ビン3へ。合計3個。

概念図

ヒント（段階的開示）

ヒント1: 方向性

「先頭から見て最初に収まるビン」を毎回全ビン走査で探すと最悪 $O(N^2)$ になる。ビンをインデックス付きの配列とみなし、「区間内の最大値」を管理するデータ構造でこの探索を高速化できないか考えよ。

ヒント2: アプローチ

各ビンのスロットに「現在の残容量」を持たせ、最大値セグメント木を構築する。まだ開いていないビンの残容量は $0$ として扱えば、$w_i\ge1$ である限り自然に「使えないビン」として扱われる。クエリは「区間 $[0,N)$ の中で値が $w_i$ 以上となる最も左のインデックス」で、セグメント木を根から子の最大値を見て降りていく二分探索で $O(\log N)$ に落とせる。

ヒント3: 誘導（コード骨格）

def query_leftmost(need):
    if tree[1] < need:
        return -1
    p = 1
    while p < size:
        if tree[2 * p] >= need:   # 左の子に条件を満たす候補がある
            p = 2 * p
        else:
            p = 2 * p + 1
    pos = p - size
    return pos if pos < n else -1

見つからなければ新しいビン（`next_free` 番目）を容量 $C$ で開いて詰め、見つかればそのビンの残容量を更新する。

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    c = int(data[idx]); idx += 1
    w = [int(data[idx + i]) for i in range(n)]
    idx += n

    w.sort(reverse=True)

    size = 1
    while size < n:
        size *= 2
    tree = [0] * (2 * size)

    def update(i, val):
        i += size
        tree[i] = val
        i //= 2
        while i >= 1:
            tree[i] = max(tree[2 * i], tree[2 * i + 1])
            i //= 2

    def query_leftmost(need):
        if tree[1] < need:
            return -1
        p = 1
        while p < size:
            if tree[2 * p] >= need:
                p = 2 * p
            else:
                p = 2 * p + 1
        pos = p - size
        return pos if pos < n else -1

    next_free = 0
    bins_used = 0
    for item in w:
        pos = query_leftmost(item)
        if pos == -1:
            pos = next_free
            next_free += 1
            bins_used += 1
            update(pos, c - item)
        else:
            update(pos, tree[pos + size] - item)

    print(bins_used)


solve()

計算量: ソート $O(N\log N)$、各荷物ごとにクエリ・更新それぞれ $O(\log N)$。全体で $O(N\log N)$。FFD法は $OPT$ に対し使用ビン数が $\frac{11}{9}OPT+\frac{6}{9}$ 以下という近似比 $\frac{11}{9}$ の保証を持つ。

Step-by-Step 解説

1降順ソート
大きい荷物から詰めることで、小さい荷物が隙間を埋めやすくなり無駄なビン開封が減る。

2セグメント木の初期化
ビンスロットの最大数は荷物数 $N$（最悪ケース）。すべて残容量 $0$（未開封）で初期化。

3最も先頭の「入るビン」を探す
根から子の最大値を見比べながら降り、常に左を優先することで最左の条件を満たすリーフを $O(\log N)$ で見つける。

4開封 or 詰め込みの更新
見つからなければ次の未使用スロットを容量 $C-w_i$ で開封。見つかれば既存の残容量から $w_i$ を引く。

よくあるミス

ミス	原因	正しい書き方
未開封ビンの初期値を負値にしてしまう	「未使用」を明示しようとする	$w_i\ge1$ なので初期値 $0$ で自然に表現できる
クエリで右の子を優先してしまう	二分探索の方向を誤る	「最も先頭」を求めるため常に左の子を優先
降順ソートを忘れる	FFDは降順が前提	`w.sort(reverse=True)` を必ず行う
ビンの最大必要数を過小に見積もる	最悪ケース（全荷物が別ビン）を考慮していない	セグメント木サイズは荷物数 $N$ ぶん確保

次のステップ

発展: Best-Fit-Decreasing（最も余裕が少なく収まるビンを選ぶ）との近似比の違いを比較する
発展: オンライン版（事前ソート不可）のビンパッキング近似アルゴリズムとの比較
次回予告: Persistent Array（関数型配列・永続セグメント木によるバージョン管理）

自己評価

完全理解おおむね理解要復習

Day 096-Q3 — セグメント木で高速化した First-Fit-Decreasing（ビンパッキング近似）

問題