問題
$N$ 変数の MAX-SAT 問題を近似的に解く。$M$ 個の節（clause）が与えられ、各節はリテラルの論理和（OR）である。各節には重み $w_j > 0$ がある。
満たされる節の重みの総和 を最大化する変数割り当て $x_1, \ldots, x_N \in \{0, 1\}$ を求めよ。
以下の近似アルゴリズムを実装し最大スコアを出力せよ：
- 乱択丸め（均等割り当て $\hat{x}_i = 0.5$ から各変数を確率 $0.5$ で 0/1 に決定）を $T$ 回試行
- $N \le 20$ の場合は全探索で厳密最適解
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 20$ |
| $M$ | $1 \le M \le 100$ |
| $T$ | $1 \le T \le 1000$ |
| $w_j$ | $1 \le w_j \le 100$ |
| $k_j$ | $1 \le k_j \le N$（節のリテラル数） |
入出力例
入力例 1
3 3 100
2 2 1 -2
3 2 -1 3
1 3 1 2 3出力例 1
6節1: (x1 ∨ ¬x2) 重み2, 節2: (¬x1 ∨ x3) 重み3, 節3: (x1 ∨ x2 ∨ x3) 重み1。x1=1,x2=0,x3=1 で全節満足、スコア=6。
概念図: 乱択丸め近似の理論保証
ヒント（段階的開示）
ヒント1: 方向性
LP 緩和解として「全変数 $\hat{x}_i = 0.5$」を使う。乱択丸め = 各変数を確率 $0.5$ で $1$ に設定するランダム割り当てと等価。節のリテラル数 $k$ に対し満足確率 = $1 - 2^{-k} \ge 0.5$。$T$ 回試行で高品質解が得られる。
ヒント2: アプローチ
- $N \le 20$ なので全探索 $O(2^N \cdot M)$ も可能
- 乱択丸め $T$ 回で失敗確率は指数減少（$T=1000$ で十分）
- 条件付き期待値法: 変数を 1 つずつ決め、残り変数の期待スコアが大きい方を選ぶ
ヒント3: 評価関数
def evaluate(assignment, clauses):
"""assignment: list[bool] 1-indexed"""
score = 0
for w, literals in clauses:
for l in literals:
val = assignment[abs(l)]
satisfied = val if l > 0 else not val
if satisfied:
score += w
break # 節が満たされたら次へ
return score
# ランダム割り当て T 回
import random
best = 0
for _ in range(T):
asgn = [False] + [random.random() < 0.5 for _ in range(N)]
best = max(best, evaluate(asgn, clauses))模範解答 (Python)
import sys
import random
input = sys.stdin.readline
def solve():
N, M, T = map(int, input().split())
clauses = []
for _ in range(M):
line = list(map(int, input().split()))
w, k = line[0], line[1]
clauses.append((w, line[2:2+k]))
def evaluate(assignment):
score = 0
for w, lits in clauses:
for l in lits:
val = assignment[abs(l)]
if (val if l > 0 else not val):
score += w; break
return score
# 乱択丸め T 回
best = 0
for _ in range(T):
asgn = [False] + [random.random() < 0.5 for _ in range(N)]
s = evaluate(asgn)
if s > best: best = s
# 全探索（N<=20）
for mask in range(1 << N):
asgn = [False] + [bool((mask >> i) & 1) for i in range(N)]
s = evaluate(asgn)
if s > best: best = s
print(best)
solve()
Step-by-Step 解説
1MAX-SAT の LP 緩和
MAX-SAT は NP 困難。LP 緩和では $x_i \in [0, 1]$ を許す。均等割り当て $\hat{x}_i = 0.5$ は最もシンプルな実行可能 LP 解。この LP 解から乱択丸めを行う。
MAX-SAT は NP 困難。LP 緩和では $x_i \in [0, 1]$ を許す。均等割り当て $\hat{x}_i = 0.5$ は最もシンプルな実行可能 LP 解。この LP 解から乱択丸めを行う。
2乱択丸めの理論保証
節のリテラル数 $k$ に対し、節が満たされる確率 = $1 - (1/2)^k$。$k=1$ で $1/2$（最悪）、$k \ge 3$ で $7/8$ 以上（MAX-3SAT の $7/8$ 近似保証の根拠）。
節のリテラル数 $k$ に対し、節が満たされる確率 = $1 - (1/2)^k$。$k=1$ で $1/2$（最悪）、$k \ge 3$ で $7/8$ 以上（MAX-3SAT の $7/8$ 近似保証の根拠）。
3条件付き期待値法（決定論的）
各変数を順に決める際、「残り変数をランダムにしたときの期待スコア」が高い方を選択。これにより乱択アルゴリズムの期待値以上のスコアを決定論的に出力できる。$O(2^{N-i} M)$ で $i$ 番目を決める。
各変数を順に決める際、「残り変数をランダムにしたときの期待スコア」が高い方を選択。これにより乱択アルゴリズムの期待値以上のスコアを決定論的に出力できる。$O(2^{N-i} M)$ で $i$ 番目を決める。
4全探索による厳密解（N≤20）
$2^{20} = 1048576$ 通り × $M=100$ 節 = $10^8$ 演算。Python では TLE の場合があるが、理論上は正確。$N$ が大きい場合は meet-in-the-middle（$N=40$ まで）を検討。
$2^{20} = 1048576$ 通り × $M=100$ 節 = $10^8$ 演算。Python では TLE の場合があるが、理論上は正確。$N$ が大きい場合は meet-in-the-middle（$N=40$ まで）を検討。
計算量
乱択丸め: $O(T \cdot M \cdot \max k)$ — $T=1000$, $M=100$ で $O(10^5)$
全探索: $O(2^N \cdot M)$ — $N=20, M=100$ で $O(10^8)$（注意: Python は遅い）
条件付き期待値法: $O(2^N \cdot M)$ — 全探索と同等
全探索: $O(2^N \cdot M)$ — $N=20, M=100$ で $O(10^8)$（注意: Python は遅い）
条件付き期待値法: $O(2^N \cdot M)$ — 全探索と同等
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 否定リテラルの符号ミス | l < 0 を見逃す | val if l > 0 else not val |
| 節が満たされた後もチェック継続 | 無駄な計算 | break で早期終了 |
| assignment の 0 番インデックス | 1-indexed 変数番号を 0-indexed で使う | assignment[abs(l)]（1-indexed） |
| T=1 で試行 | 乱択は失敗しうる | T=1000 以上で高確率保証 |
次のステップ
- 発展問題: MAX-3SAT の $7/8$ 近似を厳密に実装（Johnson's Algorithm）
- 関連: MAX-CUT の Goemans-Williamson $0.878$ 近似（SDP 緩和 + 乱択丸め）
- 応用: Weighted MAX-SAT の PTAS（多項式時間近似スキーム）