G - Degree Harmony 2 Editorial
by 
Nyaan
この問題は 線形マトロイドパリティ の練習問題です。
AtCoder Beginner Contest ではこれまで
を扱いました。マトロイドパリティ はこの 2 個を同時に一般化した組合せ最適化問題であり、いわば組合せ最適化界における 1 つのラスボスとも言える存在です。
一般のマトロイドパリティは NP 困難であることが証明されていますが、マトロイドを線形マトロイドに限定した線形マトロイドパリティには簡単な多項式時間の乱択解法が存在します。
本解説ではマトロイドパリティ問題およびその解法を簡単に紹介します。
(復習) 線形マトロイド
行列 \(A\) があります。\(E\) を行列 \(A\) の列集合とします。
\[I = \lbrace X \subseteq E \mid X に含まれる列は線形独立 \rbrace\]
と定義すると、\((E, I)\) はマトロイドになり、これを 線形マトロイド と呼びます。
線形マトロイドパリティ
列ベクトルの組の列 \((a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)\) が与えられます。
集合 \(S \subseteq \lbrace 1,2,\dots,M \rbrace\) について \(2|S|\) 個のベクトル \((a_i, b_i)_{i \in S}\) が線形独立である時、\(S\) を 独立パリティ集合 と呼びます。
最大サイズの独立パリティ集合を求める問題を 線形マトロイドパリティ と呼びます。
線形マトロイドパリティの解法
線形マトロイドパリティ問題は、解の要素数だけを計算するのであれば容易な乱択解法が存在することが知られています。
具体的には、列ベクトルのサイズを \(N\) として、次の \(N\) 行 \(N\) 列の行列 \(A\) を考えます。(\(x_i\) は不定元です)
\[A = \sum_{i=1}^M x_i \left( a_i b_i^{\mathrm{T}} - b_i a_i^{\mathrm{T}}\right)\]
この時、解の要素数は \(\mathrm{rank}(A)/2\) と一致します。証明は L. Lovász, “On determinants, matchings, and random algorithms,” をご参照ください。
よって、十分大きい素数 \(p\) を取り、行列を \(\mathbb{F}_p\) 上の行列とみなして \(x_i\) にランダムな値を代入して rank を計算することで高確率で正しい答えを計算することが出来ます。 乱択が失敗する確率は Schwarz-Zippel lemma を利用すれば \(\mathrm{O}(N/p)\) で抑えられます。
練習問題
線形マトロイドパリティが線形マトロイド交差を一般化した問題であることを確認しましょう。
具体的には、線形マトロイド交差問題を上で説明した線形マトロイドパリティを解くアルゴリズムで解いた時の結果が、ABC399-G 解説で紹介した乱択アルゴリズムの結果と一致することを確認しましょう。線形マトロイドパリティが一般グラフマッチングを一般化した問題であることを確認しましょう。
具体的には、辺重み無しの一般グラフのマッチングを上で説明した線形マトロイドパリティを解くアルゴリズムで解く過程で得られる行列が、ABC412-G 解説で紹介した Tutte 行列 と一致することを確認しましょう。(難しいです) 上記のアルゴリズムを応用すると線形マトロイドパリティの解の復元もまた多項式時間で行えることが知られています。どのような方法か考えてみましょう。(愚直な方法でも多項式時間に落ちますが、効率の良い方法があります。答えは hitonanode さんのライブラリ を参照してください。)
問題の解説
簡単に解説します。1 個の辺をマトロイドの組に対応させることで、今回の問題は分割マトロイドパリティに帰着されます。(分割マトロイドについては ABC399-G 解説をご参照ください。)
ところで、分割マトロイドは線形マトロイドに変換できることが知られています。(詳しくは ABC399-G で既に解説しています。)よってこの問題は線形マトロイドパリティに帰着されたため高速に解くことが出来ます。適切な実装の元、計算量は \(\mathrm{O}\left(\left(\sum_{i}A_i\right)^3\right)\) 程度で十分高速です。
- 実装例(C++)
- 実装例では ABC399-G で解説した方法とは異なる方法で分割マトロイドを線形マトロイドに帰着させています。なぜこの方法が正当なのか考えてみましょう。
#include <bits/stdc++.h>
using namespace std;
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
int main() {
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
int N, M;
cin >> N >> M;
vector<int> A(N), r(N + 1);
for (int i = 0; i < N; i++) cin >> A[i], r[i + 1] = r[i] + A[i];
int K = r[N];
vector m(K, vector<mint>(K));
mt19937_64 rng(58);
for (int _ = 0; _ < M; _++) {
int u, v;
cin >> u >> v;
--u, --v;
vector<mint> a(A[u]), b(A[v]);
for (auto& x : a) x = rng();
for (auto& x : b) x = rng();
for (int i = 0; i < A[u]; i++) {
for (int j = 0; j < A[v]; j++) {
m[r[u] + i][r[v] + j] += a[i] * b[j];
m[r[v] + j][r[u] + i] -= a[i] * b[j];
}
}
}
vector<pair<vector<mint>, int>> basis;
for (auto& v : m) {
for (auto& [w, top] : basis) {
if (v[top] != 0) {
mint c = v[top] / w[top];
for (int i = 0; i < K; i++) v[i] -= w[i] * c;
}
}
int top = 0;
while (top < K and v[top] == 0) top++;
if (top != K) basis.emplace_back(v, top);
}
cout << basis.size() / 2 << "\n";
}
}