Day 027-Q4 — 線形空間・マトロイドランク（Vector Matroid + Greedy最適基底）

2026-05-10 赤色 Master / Phase 8+ ★★★★★★★★★ Vector Matroid / Linear Basis

問題

$N$ 本のベクトル $v_1, \ldots, v_N \in \mathbb{F}_2^{60}$（60 ビット非負整数で表現）と、重み $w_i$ が与えられる。

  1. 最大重み独立集合: ベクトルの集合のうち線形独立（XOR で 0 にならない）であり、重みの総和が最大のものを求めよ。
  2. $k$ 番目最大 XOR: $N$ 本のベクトル全体の線形生成空間において、$k$ 番目に大きい XOR 値を求めよ。

入力形式

N k
w_1 v_1
w_2 v_2
...
w_N v_N

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq k \leq 2^{60}$
$0 \leq v_i < 2^{60}$
$1 \leq w_i \leq 10^9$

入出力例

入力例 1

4 3
10 7
8 6
6 5
3 3

出力例 1

24
5

ヒント (段階的開示)

ヒント1: 方向性
問1: ガウス消去法（線形基底）を使ったグリーディ。重み降順でベクトルを処理し、現在の基底に追加できるなら追加する（マトロイド貪欲法）。問2: 線形基底を簡約化し、$k$ を 2進数と見て基底ベクトルの XOR を選択。
ヒント2: アプローチ
線形基底の構築: basis[bit] = そのビットをピボットとするベクトル。新ベクトル追加時はガウス消去。簡約基底: 各基底ベクトルから上位ビットの基底を使って対応ビットを消す。$k$ 番目: 簡約基底を小さい順に並べ、$k$ の各ビットが 1 なら対応する基底を XOR。
ヒント3: 誘導 
class LinearBasis:
    def __init__(self):
        self.basis = {}  # bit -> vector

    def add(self, v):
        for bit in range(59, -1, -1):
            if not (v >> bit & 1):
                continue
            if bit not in self.basis:
                self.basis[bit] = v
                return True
            v ^= self.basis[bit]
        return False  # 線形従属

    def reduce(self):
        for bit in sorted(self.basis):
            for bit2 in self.basis:
                if bit2 > bit and (self.basis[bit2] >> bit & 1):
                    self.basis[bit2] ^= self.basis[bit]

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, k = map(int, input().split())
    items = []
    for _ in range(N):
        line = list(map(int, input().split()))
        w, v = line[0], line[1]
        items.append((w, v))

    # ---- 問1: 最大重み独立集合 ----
    items.sort(key=lambda x: -x[0])
    basis1 = {}
    total_weight = 0
    for w, v in items:
        cur = v
        for bit in range(59, -1, -1):
            if not (cur >> bit & 1):
                continue
            if bit not in basis1:
                basis1[bit] = cur
                total_weight += w
                break
            cur ^= basis1[bit]

    print(total_weight)

    # ---- 問2: k番目最大 XOR ----
    basis2 = {}
    for _, v in items:
        cur = v
        for bit in range(59, -1, -1):
            if not (cur >> bit & 1):
                continue
            if bit not in basis2:
                basis2[bit] = cur
                break
            cur ^= basis2[bit]

    # 簡約基底に変換
    bits_sorted = sorted(basis2.keys())
    for i, bit in enumerate(bits_sorted):
        for j in range(i + 1, len(bits_sorted)):
            bit2 = bits_sorted[j]
            if basis2[bit2] >> bit & 1:
                basis2[bit2] ^= basis2[bit]

    r = len(bits_sorted)
    basis_list = [basis2[b] for b in bits_sorted]  # 昇順

    # 降順で k番目 = 昇順で (2^r - k) 番目 (0-indexed)
    idx = (1 << r) - k
    ans = 0
    for i in range(r):
        if idx >> i & 1:
            ans ^= basis_list[i]

    print(ans)

solve()

Step-by-Step 解説

1線形基底（Linear Basis）の構築
GF(2) 上のガウス消去法。basis[bit] はピボットが bit である基底ベクトル。新ベクトル $v$ の追加: 最上位ビット $b$ を見て、basis[b] が存在すれば XOR で消去。$v=0$ なら線形従属。
2マトロイドと貪欲法
Vector Matroid の独立集合族は「GF(2) 上で線形独立な部分集合」。マトロイドの貪欲定理: 重み最大の独立集合は重み降順でグリーディに選べば得られる。
3簡約基底と k 番目 XOR
完全ガウス消去で各基底ベクトルを「ピボットビット以外の成分を全て 0」にする。span の各要素は基底ベクトルの XOR 部分集合と 1 対 1 対応。
4降順での k 番目
昇順 0-indexed で $\text{idx} = 2^r - k$ 番目が、降順で $k$ 番目に大きい値。

よくあるミス

ミス原因正しい書き方
基底構築で v = 0 になった要素を追加線形従属を見逃すv == 0 なら break して追加しない
簡約化を上から下だけ行う上位基底のビットを消さないと完全消去にならない下位基底も用いて上位基底のビットを消す
k 番目を 0-indexed で計算問題は 1-indexedidx = (1 << r) - k で調整
ベクトルが 0 の場合の処理0 は常に線形従属0 は基底に追加しない

次のステップ

  • 発展問題: 動的にベクトルを追加しながら、各時点でのランク（基底サイズ）と span の $k$ 番目最大値をオンラインで答えよ

自己評価

自分の回答

気づき・メモ