Day 134-Q4 — 劣モジュラ関数の貪欲近似（Greedy Submodular Maximization）

2026-08-26 赤色 Master / Phase 8+ ★★★★★★★★★ 最大被覆問題の(1-1/e)近似 O(NK)

問題

$1$から$M$までの要素からなる全体集合に対し、$N$個の部分集合$S_1,\dots,S_N$が与えられる。この中からちょうど$K$個の集合を選び、和集合の要素数をできるだけ大きくしたい（最大被覆問題）。この問題は一般にNP困難なので、次の貪欲法で近似的に解け。

現在の被覆集合を$C$（初期状態は空集合）とする。$K$回、次を繰り返す：まだ選んでいない集合の中から、$C$に追加したときに新たにカバーされる要素数が最大になる$S_i$を選ぶ。複数候補が同点の場合は添字が最小のものを選ぶ。

選ばれる集合の添字を選んだ順に出力し、最後に得られる被覆の要素数を出力せよ。

入力形式

N M K
c_1 e_{1,1} ... e_{1,c_1}
...
c_N e_{N,1} ... e_{N,c_N}

制約

$1 \le K \le N \le 3000$
$1 \le M \le 60$
$0 \le c_i \le M$、$\sum c_i \le 2\times10^5$

入出力例

入力例1

5 8 3
3 1 2 3
4 3 4 5 6
4 1 5 6 7
2 2 8
2 7 8

出力例1

2 1 5
8

概念図

貪欲選択: 毎回「新規カバー数」最大の集合を選ぶ 全体集合 U = {1,...,8} Step1: S2選択 新規4個 {3,4,5,6} (S3も同点4だが添字小のS2) Step2: S1選択 新規2個 {1,2} (S3,S4,S5も同点2、添字最小のS1) Step3: S5選択 新規2個 {7,8} ⇒ 最終カバー数8（全体）

ヒント（段階的開示）

ヒント1（方向性）

「厳密な最大被覆」を全探索すると$\binom{N}{K}$通りあり非現実的。本問は厳密解を求めよとは言っていない。指定された貪欲手続きを一字一句そのままシミュレートすればよい。

ヒント2（アプローチ）

$M\le60$という制約がヒント。各集合を64ビット整数のビットマスクとして表現すれば、和集合は|（OR）、要素数はint.bit_count()（Python 3.10+）で高速に計算できる。$K$回×$N$候補の$O(NK)$シミュレーションで十分。

ヒント3（誘導） 
masks = [...]  # 各集合をビットマスク化
used = [False]*N
cur = 0
chosen = []
for _ in range(K):
    best_gain = -1
    best_i = -1
    for i in range(N):
        if used[i]:
            continue
        gain = (cur | masks[i]).bit_count() - cur.bit_count()
        if gain > best_gain:
            best_gain = gain
            best_i = i
    chosen.append(best_i)
    used[best_i] = True
    cur |= masks[best_i]

gain > best_gain（>=ではない）が「同点なら添字が小さい方」を自然に実現する。

模範解答 (Python)

import sys


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

    masks = [0] * N
    for i in range(N):
        c = int(data[idx]); idx += 1
        m = 0
        for _ in range(c):
            e = int(data[idx]); idx += 1
            m |= (1 << (e - 1))
        masks[i] = m

    used = [False] * N
    cur = 0
    chosen = []
    cur_pop = 0
    for _ in range(K):
        best_gain = -1
        best_i = -1
        for i in range(N):
            if used[i]:
                continue
            gain = (cur | masks[i]).bit_count() - cur_pop
            if gain > best_gain:
                best_gain = gain
                best_i = i
        chosen.append(best_i + 1)
        used[best_i] = True
        cur |= masks[best_i]
        cur_pop = cur.bit_count()

    print(*chosen)
    print(cur_pop)


main()

Step-by-Step 解説

1被覆関数の劣モジュラ性
$f(C)=|\bigcup_{i\in C}S_i|$は「限界効用逓減」の性質（劣モジュラ性）を満たす。
2貪欲法の近似保証
Nemhauser–Wolsey–Fisherの定理により、単調劣モジュラ関数への貪欲法は最適解の$(1-1/e)\approx63.2\%$以上を保証する。
3ビットマスクによる高速化
$M\le60$ならPythonの整数1個に全要素を詰め込め、ORとbit_count()で高速計算できる。
4タイブレーク
ループを添字昇順で回しgain > best_gainで更新することで「同点なら添字最小」が自然に実現される。
5計算量
$O(NK)$に整数演算の定数倍。$N,K\le3000$なら数秒程度で収まる。

よくあるミス

ミス原因正しい書き方
タイブレークの不等号を>=にしてしまう「最大値更新」で何となく>=を使う癖添字が小さい方を優先したいので厳密な>を使う
厳密最適解を実装しようとする「最大化」という言葉から厳密解法を連想問題文は貪欲手続きそのものを問うている
増分計算cur_popの更新を忘れるループ内で毎回全体を数え直すのは非効率かつミスの元選んだ後にまとめて1回cur_popを更新する
要素番号が1-indexedなのを忘れるビット位置は0始まり1 << (e - 1)のように必ずずらす
$K=N$で順序を無視してよいと誤解最終的な被覆自体は順不同で同じになると早合点出力仕様は「選んだ順」も求めているため、貪欲の実行順通りに出力する

次のステップ

  • 発展: $M$が大きい（$10^5$程度）場合、多倍長整数のビット演算がどこまで実用的か実験的に確認せよ。
  • 発展2: 「全要素をカバーするのに必要な最小集合数」を求める古典的な集合被覆問題に対する貪欲の$O(\log M)$近似との違いを整理せよ。
  • 次回予告: 次回のテーマは今後のセッションで選定

自己評価

自分の回答

気づき・メモ