AtCoder Beginner Contest 236 F 問題 Spices
問題
提出解答
問題の概要
を
以下の正の整数の集合とする.
の部分集合で以下を満たすような
全体の集合を
とする.
として,
を適当に選ぶことで,
とできる.
このとき, を求めよ.
制約
解法
xor 演算は有限体 を係数体するベクトル空間
上の和とみなせる. よって, この問題は以下と同じである.
が与えられる. このとき,
このことから, 線形代数の知識が役に立つ.
線形代数の知識
以降では, を体
上のベクトル空間とする. このとき, 以下のことが成り立つ (証明は省略).
定理1
有限次元ベクトル空間における基底の数はその取り方に依らない.
定理2
は一次独立とする.
に対して, 以下は同値である.
は一次独立である.
解答
よって, 以下のアルゴリズムによって正解を導くことができる.
となるように
の並び替え
を求める.
とする.
の順に以下を実行する.
ならば,
とする.
が答えである.
このアルゴリズムの肝は である.
ならば,
であるから,
から1元を取り除いてもよい. 今,
は
であり,
より, 取り除くべきは
であることがわかる. 詳しくは
マトロイドという線形空間のベクトルにおける一次独立, 一次従属を拡張した概念があるので, 調べること.