Day 131-Q2 | パラメトリックサーチ（Dinkelbachの算法による分数計画）

問題

$N$個のアイテムがあり、アイテム$i$は価値$a_i$、コスト$b_i$（$b_i>0$）を持つ。この中からちょうど$K$個を選び、選んだアイテムの価値の合計をコストの合計で割った比 $$R = \frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i} \quad (|S|=K)$$ を最小化したときの$R$を、既約分数 p/q の形で求めよ。

入力形式

N K
a_1 a_2 ... a_N
b_1 b_2 ... b_N

制約

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

$0 \le a_i \le 10^9$

$1 \le b_i \le 10^9$

入出力例

入力例1

8 3
3 1 4 1 5 9 2 6
1 1 2 3 1 4 1 3

出力例1

4/5

概念図

ヒント（段階的開示）

ヒント1（方向性）

比の最小化はそのままでは「和の比」なので貪欲やDPが効きにくい。答えを仮定して判定問題に落とすパラメトリックサーチ（Megiddoの一般手法）の具体化として、比の最適化にはDinkelbachの算法という反復法が知られている。

ヒント2（アプローチ）

$g(\lambda)=\min_{|S|=K}\sum_{i\in S}(a_i-\lambda b_i)$ は「$a_i-\lambda b_i$が小さい順にK個選ぶ」貪欲でO(N log N)計算できる。最適比$\lambda^*$は$g(\lambda^*)=0$を満たす一意な値で、$g$は単調減少・区分線形。Dinkelbach反復$\lambda_{t+1}=\frac{\sum_{i\in S_t}a_i}{\sum_{i\in S_t}b_i}$は有理数のまま有限回で厳密収束する。

ヒント3（誘導）

from fractions import Fraction

def min_ratio_select_k(a, b, K):
    n = len(a)
    lam = Fraction(0)
    while True:
        order = sorted(range(n), key=lambda i: a[i] - lam * b[i])
        chosen = order[:K]
        sa = sum(a[i] for i in chosen)
        sb = sum(b[i] for i in chosen)
        new_lam = Fraction(sa, sb)
        if new_lam == lam:
            return new_lam
        lam = new_lam

模範解答 (Python)

import sys
from fractions import Fraction


def min_ratio_select_k(a, b, K):
    n = len(a)
    lam = Fraction(0)
    chosen = list(range(K))
    for _ in range(200):  # 実際は数回〜十数回で収束する
        order = sorted(range(n), key=lambda i: a[i] - lam * b[i])
        chosen = order[:K]
        sa = sum(a[i] for i in chosen)
        sb = sum(b[i] for i in chosen)
        new_lam = Fraction(sa, sb)
        if new_lam == lam:
            return new_lam
        lam = new_lam
    return lam


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

    ans = min_ratio_select_k(a, b, k)
    print(f"{ans.numerator}/{ans.denominator}")


solve()

Step-by-Step 解説

1比の最小化を線形関数の最小化に変換
比 ≤ λ は選択集合Sについて Σ(a_i-λb_i) ≤ 0 に整理できる。非線形な目的関数をパラメータλ付きの判定しやすい線形問題にすり替える発想がパラメトリックサーチの核心。

2g(λ)の単調性
g(λ)は各Sごとの直線の下側包絡線なので上に凸で連続な区分線形関数。b_i>0より傾きは常に負なので単調減少。g(λ*)=0が最適比。

3有限回で収束する理由
λ_t+1はS_t自身の比なのでg(λ_t+1)≥0が常に成立し、λ_tは単調非増加列になる。選択集合の総数は有限(NCK通り)なので有限回で同じSが選ばれて収束する。

4実装上の要点
Fractionを使うことで浮動小数点の丸め誤差なしに厳密な最適値を得られる。ソートキーにFractionのlamを使っても内部で通分され正しく比較される。

5計算量
1回の反復はO(N log N)(ソート)。反復回数は理論上O(N)だが実務上ほぼ定数(数回〜十数回)。全体で十分高速。

よくあるミス

ミス	原因	正しい書き方
浮動小数点でλを更新し誤差が蓄積する	floatの比較で収束判定が振動する	Fractionを使い厳密な等号比較で収束判定する
ちょうどK個選ぶ制約を無視する	「a_i-λb_iが負なら選ぶ」という誤った判定を使う	常に小さい順にちょうどK個を選ぶ制約を守る
収束条件を近似判定にしてしまう	厳密解が要求される問題で誤差許容の二分探索を流用する	選択集合(=λ)が変化しなくなったことを厳密な収束条件にする
タイブレークで境界の選択がずれる	ソートの安定性やタイの処理を考慮していない	比の値自体はどのタイブレークでも一致するが、集合復元が必要な場合は注意する

次のステップ

発展: 木の中でK本の辺を選び平均コストを最小化するなど、選択構造がDPやMSTになる場合でも同じDinkelbachの枠組みが使える
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 131-Q2 — パラメトリックサーチ（Dinkelbachの算法による分数計画）

問題