AtCoder Beginner Contest 236 F 問題 Spices

問題

提出解答

問題の概要

$[\![M]\!]$ を $M$ 以下の正の整数の集合とする. $\mathcal{P}([\![2^N-1]\!])$ の部分集合で以下を満たすような $I \subset [\![N]\!]$ 全体の集合を $\mathcal{G}$ とする.

$x=1,2, \dots, 2^N-1$ として, $v_1, \dots, v_r \in \mathcal{V}$ を適当に選ぶことで, $v_1 \oplus \dots \oplus v_r=x$ とできる.

このとき, $\displaystyle \min_{G \in \mathcal{G}} \sum_{v \in G} c_v$ を求めよ.

制約

$2 \leq N \leq 16$
$1 \leq c_v \leq 10^9$

解法

xor 演算は有限体 $\mathbb{F}_2$ を係数体するベクトル空間 $\mathbb{F}_2^N$ 上の和とみなせる. よって, この問題は以下と同じである.

$c:\mathbb{F}_2^N \to \mathbb{Z}$ が与えられる. このとき,

$\displaystyle \min_{\substack{G \subset \mathbb{F}_2^N \setminus \{0_V\} \\ V=\operatorname{Span} G}} \sum_{v \in G} c(v)$

を求めよ.

このことから, 線形代数の知識が役に立つ.

線形代数の知識

以降では, $V$ を体 $F$ 上のベクトル空間とする. このとき, 以下のことが成り立つ (証明は省略).

定理1

有限次元ベクトル空間における基底の数はその取り方に依らない.

定理2

$v_1, \dots, v_r \in V$ は一次独立とする. $w \in V$ に対して, 以下は同値である.

$w \not \in \operatorname{Span} \{v_1, \dots, v_r \}$
$v_1, \dots, v_r,w$ は一次独立である.
$\operatorname{Span} \{v_1, \dots, v_r\} \subsetneq \operatorname{Span} \{v_1, \dots, v_r,w \}$

解答

よって, 以下のアルゴリズムによって正解を導くことができる.

$c_{p_1} \leq c_{p_2} \leq \dots \leq c_{p_{2^N-1}}$ となるように $(1,2, \dots, 2^N-1)$ の並び替え $p=(p_1, p_2, \dots, p_{2^N-1})$ を求める.
$G=\emptyset$ とする.
の順に以下を実行する.
- $p_i \not \in \operatorname{Span} G$ ならば, $G \gets G \cup \{p_i\}$ とする.
$\displaystyle \sum_{p_i \in G} c(p_i)$ が答えである.

このアルゴリズムの肝は $3.$ である. $p_i \in \operatorname{Span} G$ ならば, $\operatorname{Span} G=\operatorname{Span} (G \cup \{p_i\}$ であるから, $G \cup \{p_i\}$ から1元を取り除いてもよい. 今, $p_1, \dots, p_i$ は $c_{p_1} \leq \dots \leq c_{p_i}$ であり, $\operatorname{Span} G=\operatorname{Span} (G \cup \{p_i\}$ より, 取り除くべきは $p_i$ であることがわかる. 詳しくはマトロイドという線形空間のベクトルにおける一次独立, 一次従属を拡張した概念があるので, 調べること.