A - I Love MST Problem Editorial
by 
harurun4635
前提
議論を簡単にするために、少し言葉遣いを変えて以下のような問題とします。
辺 \((u_k, v_k)\) を張り、その辺に数字 \(k\) を書き込む。このとき閉路ができないようにする。
\(1 \le k \le N-1\) を \(1\) 回ずつ書き込んだとき \(\displaystyle \sum_{1 \le k \le N-1} \left( (u_k + v_k) \times k \bmod N \right)\) を最小化してください。
また、以下では「 \((u_k, v_k)\) に辺を張って \(k\) を書き込む」ことを単に「 \(k\) を書き込む」とよぶことがあります。また \(\displaystyle g_k = \gcd(k, N)\) とします。
まず、いくつかの命題を以下で示します。
命題 1
\(g_k \ne 1\) である \(k\) をすべてコスト \(0\) で書き込む方法が存在する。
証明
$g_k \ne 1$ である、すべての $k$ について $q_k \mid g_k$ であるような最小の素数 $q_k$ をとってきます。また $\displaystyle N = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_l^{e_l} ~ (p_1 \lt p_2 \lt \cdots \lt p_l)$ と素因数分解します。ここで、$q_k$ の頻度列がどのようになっているか考えます。
- $q_k = p_1$ である $k$ は $\displaystyle \frac{N}{p_1} - 1$ 個（$k = N$ がないため $-1$ がつきます）
- $q_k = p_i ~ (2 \le i \le l)$ である $k$ は $\displaystyle \frac{N}{p_i} \prod_{1\le j \lt i} \frac{p_j - 1}{p_j}$ 個
$i$ の昇順に、「 $q_k = p_i$ である $k$ 」を書き込む事を考えます。それぞれの $i$ について最後に書き込む $k$ が（閉路を作らず）書き込めることを示せばよいです。ここで、連結成分数が $\displaystyle \Big \lfloor \frac{\frac{N}{p_i}}{2} \Big \rfloor + 1$ より多ければ $k$ を必ず書き込めます。
簡単に証明します。和が $\displaystyle \frac{N}{p_i}$ の倍数となる $2$ つの数が、異なる連結成分に属するのであれば、それらを結んで $k$ を書き込めばよいです。連結成分数は「 $N-$ 書き込んだ辺の数 $=$ 書き込んでいない辺の数 $+ 1$ 」となるはずなので、全ての $i$ について $$ \displaystyle N \prod_{1\le j \le i} \frac{p_j - 1}{p_j} + 1 \ge \Big \lfloor \frac{\frac{N}{p_i}}{2} \Big \rfloor + 1 $$ が成り立つのであれば、コスト $0$ にできます。（各 $i$ の最後の $k$ を書き終わったときの連結成分数が左辺です。これが右辺以上であれば、書き込む前は「より多い」を満たします）
もし結べないのだとしたら、それらがすべて同じ連結成分にあるということです。このとき、連結成分数は高々 $\displaystyle \Big \lfloor \frac{\frac{N}{p_i}}{2} \Big \rfloor + 1$ となります。よって、それより多いのであれば必ず結ぶことができます。
$p_0 = 1$ として、$p_{j-1} \le p_{j} - 1$ を用いると、 $$\displaystyle N \prod_{1\le j \le i} \frac{p_j - 1}{p_j} + 1 \ge N \prod_{1\le j \le i} \frac{p_{j-1}}{p_j} + 1= \frac{N}{p_i} + 1 \ge \Big \lfloor \frac{\frac{N}{p_i}}{2} \Big \rfloor + 1 $$ より示されました。
命題 2
（いくつかの数字を書き込んでいて）閉路が存在しないかつ連結成分数が \(2\) 以上とする。
このとき \(g_k = 1\) である \(k\) は必ずコスト \(1\) 以下で書き込める。
証明
まず次のような数列 $A = (A_0, A_1, \dots A_{N-1})$ を考えます。 $$A_i = \begin{cases} \displaystyle \frac{i + 1}{2} & (\text{if } i \text{ is odd}) \\ \displaystyle N - \frac{i}{2} & (\text{if } i \text{ is even}) \end{cases}$$ たとえば $N = 8$ なら $A = (8, 1, 7, 2, 6, 3, 5, 4)$、 $N = 9$ なら $A = (9, 1, 8, 2, 7, 3, 6, 4, 5)$ となります。そして $g_k = 1$ のとき $k \times k^{-1} \equiv 1 \pmod N$ なる $k^{-1}$ が存在するので、これを用いて $$B_i = A_i \times k^{-1} \bmod N$$ とします。このとき、$B$ の各要素は相異なりかつ $(B_i + B_{i+1}) \times k \bmod N \le 1$ です。
この数列で隣り合うような要素であって、異なる連結成分に属するものが少なくとも $1$ つ存在するはずなので、それらを選んで結べばよいです。
命題 3
「 \(M =\) コスト \(0\) で書き込んだ \(k\) の数としてありうる最大値」とする。すると、本問題の答えは \(N - 1 - M\) となる。
証明
まず「 $M =$ コスト $0$ で書き込んだ $k$ の数」を達成するような書き込み方であって「 $g_k \ne 1$ である $k$ を全てコスト $0$ で書き込んだ」ものが存在することを示します。$M$ を達成するような書き込み方を適当に $1$ つ取ります。
ここで $g_s \ne 1$ でコスト $0$ でない辺 $(u_s, v_s)$ があると仮定します。このとき $g_t = 1$ でコスト $0$ の辺 $(u_t, v_t)$ が存在するはずです。（そうでないならば $M \lt$「 $g_k \ne 1$ である $k$ の個数」ということになり、命題 1 に矛盾します）
そして、それぞれに書かれている数字を swap して書き換えます。$N \mid u_t + v_t$ であるはずですから、書き換えてもコスト $0$ の個数が悪化することはありません。
これを「 $g_k \ne 1$ でコスト $0$ でない辺」がなくなるまで繰り返します。
これが終わったとき「コストが $0$ でない辺」はすべて $g_k = 1$ であるはずです。よって「コストが $0$ でない辺」を一度すべて取り除き、命題 $2$ にしたがって結び直せば、上の答えが達成可能です。
また、この値よりも小さくすることはできないので、これが答えです。
これまでの命題から、この問題は「コスト \(0\) で書き込んだ \(k\) の数としてありうる最大値はいくつか？」を求めればよいことがわかります。
これは簡単には「閉路マトロイド」と「横断マトロイド」のマトロイド交叉として表現できます。たとえば ABC399G Colorful Spanning Tree で紹介されているような方法で \(O(N^3)\) で解くことができます。この問題ではさらなる高速化を要求します。
命題 4 （Rado の定理）
Rado の定理とよばれる定理があります。これは Hall の結婚定理のマトロイドに対する自然な拡張として知られています。主張は以下のとおりです。
マトロイド \(M = (E, \mathcal{I})\) とそのランク関数 \(\rho\) および \(E\) の部分集合族 \(\mathcal{A} = (A_1, \dots, A_m)\) が与えられる。
\(\mathcal{A}\) が独立な代表系をもつための必要十分条件は以下のとおりである。任意の添字集合 \(J \subseteq \{1, \dots, m\}\) に対して
\[ \rho\left( \bigcup_{j \in J} A_j \right) \ge |J|\]
が成り立つ。
ただし、「独立な代表系をもつ」とは、各 \(i\) に対して \(x_i \in A_i\) を選んで \(x_i \ne x_j ~(i \ne j)\) かつ \(\{x_1, \dots, x_m\} \in \mathcal{I}\) とできることを指す。
次のような証明が簡単な証明として知られているようです。 Generalized versions of Hall’s theorem (Welsh, 1971)
それとは異なる証明を以下では与えます。
証明
必要性は明らかなので十分性を考えます。集合族のサイズ $m$ に対する帰納法で証明します。基本的には Hall の結婚定理を帰納法で証明する手法と同じです。
$m = 0$ では明らかに成立します。サイズ $m-1$ の以下の集合族について成立するとき $m$ についても成立することを示します。 $K \subsetneq \{1, \dots, m\} ~ ( K \ne \empty)$ であるような添字集合であって、$\displaystyle \rho\left( \bigcup_{j \in K} A_j \right) = |K|$ を満たすものがあるかどうかで場合分けをします。
- そのような $K$ が存在するとき
$|K| \le m-1$ ですから、帰納法の仮定より $K$ に対する独立な代表系 $X_K = \{ x_k \mid k \in K\}$ が存在します。
ここで、縮約マトロイド $\mathcal{I} / X_K$ について考えます。（ 離散最適化基礎論 第 8回 マトロイドに対する操作 に詳細をまかせます）縮約マトロイドのランク関数は $\rho ' (S) = \rho (S \cup X_K) - |X_K|$ となります。
任意の $J \subseteq \{1, \dots, m\} \setminus K$ について Rado の条件が満たされれば、帰納法の仮定から $\{1, \dots, m\} \setminus K$ に対する独立な代表系を選ぶことができ、全体に対する独立な代表系を構築できます。
$$\displaystyle \rho'\left( \bigcup_{j \in J} A_j \right) = \rho \left( \bigcup_{j \in J \cup K} A_j \right) - |K| \ge |J \cup K| - |K| = |J|$$ ですから、 Rado の条件が満たされることが示されました。
- そのような $K$ が存在しないとき
$$\displaystyle \rho\left( \bigcup_{j \in J} A_j \right) \ge |J| + 1$$
が $J \subsetneq \{1, \dots, m\} ~ ( J \ne \empty)$ である $J$ について成り立ちます。
このとき、適当に $x_1 \in A_1$ を決め、同様に縮約マトロイド $\mathcal{I} / \{x_1\}$ を考えます。縮約マトロイドにしたとしても、高々 $1$ しかランクは下がらないため、Rado の条件が縮約マトロイドでも成り立ちます。
Rado の定理を用います。閉路マトロイドを \(M = (E, \mathcal{I})\) とそのランク関数を \(\rho\) とします。 \(A_k = \{(u, ~ v) : N \mid (u + v) \times k \}\) として
\[\displaystyle \max_{J \subseteq \{1, \dots, N-1\}} \left( |J| - \rho\left( \bigcup_{k \in J} A_k \right) \right)\]
が答えとなります。
これは Hall の結婚定理などと同様に、どの \(A_i\) にも含まれ、必ず独立となるような「オールマイティ」な要素を考え、それをいくつ追加すれば Rado の条件が満たされるかを考えればよいです。
ところで \(J\) として考えなければいけない集合はそこまで多くありません。具体的には \(N\) の約数 \(d\) を用いて \(J_d = \{ k : g_k \mid d\}\) とかけるもののみを考えればよいです。
証明
$g_k$ が同じものについては $A_k$ が等しいので、以下代表元として $k = g_k$ を満たす $k$ のみを考えます。（すべての $g_k$ について、この $k$ は必ず存在し $N$ の約数です）また、以下 $d_k = N/k$ とします。このとき $(u + v) \times k \equiv 0 \Leftrightarrow d_k \mid (u + v)$ となります。
$2$ つの命題を証明します。
- ある $a \in J$ のとき $c \mid a$ を追加してよい。 $d_c \mid (u + v) \Rightarrow d_a \mid (u + v)$ よりランクはふえず、集合のサイズのみ大きくするため、従います。
- ある $a$ と $b$ が $J$ に含まれているとき $c = \text{lcm}(a, b)$ である $c$ を追加してもよい。 $d_c \mid (u + v)$ を満たす、任意の $(u, v)$ について $A_a, A_b$ を用いれば連結にできることを示せばよいです。
まず $2$ 回の移動を用いれば $(s, d_a-s), (d_a-s, d_a + s)$ などと結ぶことで、$d_a$ だけ離れた頂点を連結にできます。 同様に $d_b$ だけ離れた頂点も連結にできますから、$d_c = \gcd(d_a, d_b)$ だけ離れた頂点も連結にすることができます。
次のように構築をします。 $(u, d_a-u)$ をはじめに結びます。このとき $d_c \mid v - (d_a - u)$ です。よって $(d_a-u, v)$ は上を繰り返すことで連結にできます。よって示されました。
上の命題を繰り返し用いることで、任意の部分集合 $J$ について、それよりも集合のサイズが大きくランクが変化しない $J_d = \{ k : g_k \mid d\}$ が存在することがわかります。
\(\displaystyle \rho\left(\bigcup_{k \in J_d}A_k\right) =\rho(A_d)= N - \left( \left \lfloor \frac{\frac{N}{d}}{2} \right \rfloor + 1 \right)\) です。\(|J_d|\) についてもすべての \(d\) について \(O (\tau(N) ^2)\) や \(O(\tau(N)\omega(N))\) などで求める事ができます。（ただし \(\tau\) は約数の個数、 \(\omega\) は重複なし素因数の個数です）
よって、約数を求めるパートと合わせて \(O(\sqrt N + \tau(N) ^2)\) で求めることができます。
posted:
last update: