Day 146-Q4 — Efraimidis-Spirakis法（重み付きReservoir Sampling / A-Res）

2026-09-07 赤色 Master / Phase 8+ ★★★★★★★★★ キーr_i=u_i^(1/w_i)の上位K個が重み比例の非復元抽出と等価になることを実測

問題

$N$個のアイテムがあり、それぞれ正の重み$w_i$と一様乱数$u_i\in(0,1)$が与えられる。キー関数

$r_i = u_i^{1/w_i}$

を計算し、$r_i$の値が大きい方から$K$個のアイテムの番号（1-indexed）を昇順に出力せよ。

背景: 重み$w_i$が大きいアイテムほど$r_i=u_i^{1/w_i}$は1に近づきやすい（指数$1/w_i$が小さいほど$u_i^{1/w_i}$は1に近づく）ため上位$K$個に入りやすくなる。この性質により単純な降順ソート＋上位$K$個抽出が、重み比例の優先度付き非復元抽出を正しく実現することがEfraimidis-Spirakisにより証明されている。

入力形式

N K
w_1 u_1
:
w_N u_N

制約

$1 \le K \le N \le 12$
$1 \le w_i \le 10$（整数）
$0.01 \le u_i \le 0.99$（小数第2位まで）
キーの同値（タイ）は生じない

入出力例

入力例1

6 3
2 0.50
5 0.10
1 0.90
3 0.40
4 0.20
1 0.95

出力例1

3 4 6

r6=0.95, r3=0.9, r4≈0.737, r1≈0.707, r5≈0.669, r2≈0.631。上位3個は{6,3,4}→昇順で「3 4 6」。

概念図：キーによる優先度付き抽出

キー r_i = u_i^(1/w_i) の降順ランキング（K=3採用） item6 r=0.950 ← 採用 item3 r=0.900 ← 採用 item4 r=0.737 ← 採用 K=3の境界 item1 r=0.707 item5 r=0.669 item2 r=0.631

ヒント（段階的開示）

ヒント1（方向性）

等確率Reservoir Samplingは重みを考慮しない。重み比例の抽出確率を実現するには、各要素の「採用されやすさ」を1つのスカラー値（キー）に落とし込み、そのキーで比較するだけで正しい確率分布が実現できるキー関数の設計が核心。

ヒント2（アプローチ）

$u_i^{1/w_i}$の累積分布関数は$P(r_i\le x)=x^{w_i}$であり、これは$w_i$個の独立な$U(0,1)$の最大値の分布と一致する。重みが大きいほど「複数回のくじ引きの最大値」に近い性質を持ちキーが1に近づきやすくなる。

ヒント3（誘導） 
def compute_keys(weights, randoms):
    keys = []
    for i in range(len(weights)):
        r = randoms[i] ** (1.0 / weights[i])
        keys.append(r)
    return keys

indices = sorted(range(N), key=lambda i: -keys[i])
selected = sorted(indices[:K])

$N\le12$と極めて小さいため計算量は問題にならない。

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1

    keys = []
    for i in range(N):
        w = int(data[idx]); idx += 1
        u = float(data[idx]); idx += 1
        r = u ** (1.0 / w)
        keys.append(r)

    order = sorted(range(N), key=lambda i: keys[i], reverse=True)
    selected = sorted(order[:K])

    print(' '.join(str(i + 1) for i in selected))

main()

Step-by-Step 解説

1キーの計算
各アイテム$i$について$r_i=u_i^{1/w_i}$を計算する。
2キーによる降順ソート
全アイテムをキー降順にソートし上位$K$個のインデックスを取得する。オンライン実装ではサイズ$K$の最小ヒープで同じ結果を得られる。
3出力形式の整形
選ばれた$K$個を1-indexed・昇順に整形する。
4正当性の背景（発展）
$P(r_i\le x)=x^{w_i}$は$w_i$個の$U(0,1)$の最大値の分布と一致し、これが重み比例抽出の正しさを保証する。
5入力例の検証
r6=0.95,r3=0.9,r4≈0.737,r1≈0.707,r5≈0.669,r2≈0.631。上位3個{6,3,4}→「3 4 6」。

よくあるミス

ミス原因正しい書き方
重みの逆数を取らず$u_i^{w_i}$を計算指数の向きを取り違える正しくは$u_i^{1/w_i}$（指数は重みの逆数）
出力をキー降順のまま出力「昇順に出力」の指定を見落とす選ばれたインデックスを`sorted()`で昇順に並べ直す
0-indexedのまま出力内部インデックスと出力仕様を混同出力時に`i+1`で1-indexedに変換
浮動小数点誤差を心配して丸め処理を入れる「タイは生じない」という制約を見落とすそのまま`**`でべき乗しソートするだけでよい
到着順序に依存すると誤解する等確率版Algorithm Rのイメージを引きずる重み付き版はキーの大小だけで決まり到着順序に依存しない

次のステップ

  • 発展: サイズ$K$の最小ヒープを使った1パスのオンライン実装を書き、オフライン全ソート版と同じ結果になることを確認せよ。
  • 次回予告: van Emde Boas Layout（キャッシュオブリビアスな二分探索木の再帰的メモリレイアウト）

自己評価

自分の回答

気づき・メモ