アフィン部分空間の共通部分の計算

2022/05/02 記事中の記号の使い方やその他の軽微な修正をしました。

概要

$\mathbb{F} _ p ^ d$ のアフィン部分空間が $\mathrm{span}\lbrace a _ 1, a _ 2, \dots, a _ n \rbrace + b$ の形で与えられるとき、 $2$ つのアフィン部分空間の共通部分を時間計算量 $\Theta( (n + d) d ^ 2 + d \log(p) )$ で計算する。

アフィン部分空間

ベクトル空間 $V$ の部分集合 $S$ は、部分空間 $U \subseteq V$ と $b \in V$ によって $S = \lbrace u + b \mid u \in U \rbrace$ と表現できるとき、アフィン部分空間であると言う。アフィン部分空間は部分空間の一般化になっており、後述するが競プロでも出現する概念である。 $S$ に対して $U$ は一意だが $b$ は一般には一意でない。

アフィン部分空間の $2$ 通りの表現

$\mathbb{K}$ を体として、 $S$ を $\mathbb{K} ^ d$ のアフィン部分空間とする。定義から明らかに、 $A \in \mathbb{K} ^ {d \times n}, b \in \mathbb{K} ^ d$ によって $S = \lbrace Ax + b \mid x \in \mathbb{K} ^ n \rbrace$ と表現できる。ここで $n$ は $S = \lbrace u + b \mid u \in U \rbrace$ としたときの $U \subseteq \mathbb{K} ^ d$ の次元である。

(ドット積についての) 直交補空間を考えると、 $\lbrace Ax \mid x \in \mathbb{K} ^ n \rbrace = \lbrace y \mid y \in \mathbb{K} ^ d , Cy = 0 \rbrace$ となる $C \in \mathbb{K} ^ {(d - n) \times d}$ が存在する。すると、 $S = \lbrace y + b \mid y \in \mathbb{K} ^ d, Cy = 0 \rbrace = \lbrace y + b \mid (y + b) \in \mathbb{K} ^ d, C(y + b) = Cb \rbrace$ であり、諸々の記号を置きなおすと結局 $S = \lbrace y \in \mathbb{K} ^ d \mid Cy = d \rbrace$ という表現を得る*1。逆に、 $\lbrace y \in \mathbb{K} ^ d \mid Cy = d \rbrace$ と表現される集合は、空であるかアフィン部分空間であることもすぐに確かめられる。

アフィン部分空間の共通部分の計算

$S _ 1, S _ 2$ をアフィン部分空間として、 $S _ 1 = \lbrace y \in \mathbb{K} ^ d \mid C _ 1 y = d _ 1 \rbrace, S _ 2 = \lbrace y \in \mathbb{K} ^ d \mid C _ 2 y = d _ 2 \rbrace$ と表現できるとする。すると $\displaystyle S _ 1 \cap S _ 2 = \left \lbrace y \in \mathbb{K} ^ d ~ \middle | \pmatrix{C _ 1 \cr C _ 2} y = \pmatrix{d _ 1 \cr d _ 2} \right \rbrace$ であり、容易に共通部分の表現が得られる。この式から分かるように、これらのアフィン部分空間の共通部分は空であるかアフィン部分空間となる。 $\lbrace Ax + b \mid x \in \mathbb{K} ^ n \rbrace$ と $\lbrace y \in \mathbb{K} ^ d \mid Cy = d \rbrace$ の表現の相互の変換は、直交補空間の計算と同様に行うことができる (参考: Parity-check matrix - Wikipedia)。

実用例

注意: cp-unspoiler この問題のネタバレを含みます。

G - Xor Cards

$C _ i$ を、 $A _ i, B _ i$ を $\mathbb {F} _ 2 ^ {30}$ の元として見てこの順に連結したベクトルと定義する。問題は以下のように整理される。

長さ $N$ の非負整数列 $(C _ i)$ と、非負整数 $K$ が与えられる。 $C$ から $1$ つ以上選んで xor を計算し、前半 $30$ bit が $K$ 以下になるようにしつつ、後半 $30$ bit を最大化せよ。

$K$ 以下の非負整数全体は、「下位 $t$ bit は自由で、残りは決まっている」という形の集合の高々 $\log _ 2(K) + 1$ 個の直和に分解される。この分解のそれぞれについて独立に計算し、最後に最大値を取ればよい。

$1$ つ以上選ぶという条件を一旦 $0$ 個以上に緩和すると、「 $C$ から $0$ 個以上選んで xor を取ることで得られる数全体」と「下位 $t$ bit は自由で、残りは決まっている数全体」はいずれも ( $\mathbb{F} _ 2 ^ {60}$ の) アフィン部分空間になっている。したがって、これらの共通部分 $S$ を計算した後、 $S$ の元で後半 $30$ bit が最大となるものを計算すればよい。実際には、 $C _ i$ の定義を $B _ i, A _ i$ の順に連結することにして、単に $\max S$ を求めるのが簡単だろう。 $\max S = 0$ かつ $(C _ i)$ が線形独立である場合に限り最大値を $-1$ に修正することで、 $1$ つ以上選ぶ条件をカバーする。