ZONe-Fを考えた（備忘録）

 昨日Atcoderにて行われたZONeコンテストにて、F問題がどうにも理解できず、うんうん考えてやっと理解したので、備忘録です。たぶん、自分で書いておかないと来週には忘れる…。

問題は、$N=2^n$、$\mathcal{N} = \{0,...,N-1\}$ と、$A = \{A_1,...,A_M\} \subset \mathcal{N}\setminus \{0\}$（但し $M < N$）について、$\mathcal{N}$ の数字の全てを $B = \{1,...,N-1\} \setminus A$ の元の XOR で繋いだ木で表せ、というもの。

例えば $N = 8, A = \{2,3,5,6\}$ だとすると、XOR に使っていいのは $\{1,4,7\}$で、

\begin{array}{ccccccc}
7 &\xleftarrow{7} &0 &\xrightarrow{1} &1 &\xrightarrow{4} &5 \\
  & &\downarrow^4 & &\downarrow^7 & &\downarrow^7 \\
3 &\xleftarrow{7} &4 & &6 & &2
\end{array}

と、$\{1,4,7\}$ だけを XOR することで $\{0,...,7\}$ の数字を作ることができ、かつ、それが連結な木になっています。問題は、そもそも $\mathcal{N}$ をすべて繋げるかどうかを判定することと、もし連結ならば実際に木を構成することの二段階で、解説では(1)まず $B$ から $(\mathbb{Z}/2\mathbb{Z})^n$ の基底を構成できれば連結、(2)次にその基底を使ってグラフを作成する、という流れになっていました。

さて、ではまずはそのまま作ってみようとすると、基底はなんとなく作ることができるのだけれど（上のビットから一つずつ残していけばいい）、そこからグラフを作成するのが大変で、どうするのが美しいのかよくわからない。ともかく、めちゃめちゃメモリと計算時間を使えば、(3)基底を作成するときにあらかじめどの$b\in B$を使ってその基底を作ったかをメモしておく、(4)基底の全組み合わせについて、$B$ の元の列＝$B$ の元の部分集合を構成し、その順にlinkを張ったグラフを作る。（例えば $2$ が基底だったとすると、 $2 = 1 \oplus 4 \oplus 7$ より $\{1,4,7\}$ が記録されているので、$0 \rightarrow 1$、$1 \rightarrow 5$、$5 \rightarrow 2$ を繋ぐ。または、$3,6$ が基底に取られていたとしたら、$3$ と $6$ との組み合わせでできる $5$ は、$3\oplus 6 = 4 \oplus 7 \oplus 1 \oplus 7 = 1 \oplus 4 = 5$ なので、$0 \rightarrow 1$、$1 \rightarrow 5$ を繋ぐ、など。）しかしこの構成方法だと繋ぎすぎてループができてしまうので（$B=\{1,4,7\}$ の例だと基底数と$\# B$が一致していてループができませんが、$n < \# B$ だとパスが$N-1$より多くなってしまう可能性がある気がします）、最後にダイクストラなどをやって、木に戻してあげると、めでたく回答になります。

ただ、この方法だとコードがえらい冗長になってしまう。TLEにこそならないけれど、なんかエレガントでないので、巧い人らはどうしてるのかなと思って拝見したところ、めちゃめちゃ平易に書いてあってびっくりしました。最初はなんでそれでOKなのかわからず、二、三時間ほど格闘してやっと腑に落ちました。以下はその概説備忘録。

まず、$S$ で$0$ を含む連結成分の元を管理する。最初は $0$ を入れておく。

次に、$B$ の元を順に取ってくる。まず一つ目を $b_1$ とすると、$B$ の元は $A$ に入らないからXORで遷移するのに使える。特に、今 $S$ に入っている $0$ に対して、 $0\oplus b_1 = b_1$ なので、$0 \xrightarrow{b_1} b_1$ のlinkを張れば $0$ と $b_1$ が繋がることから、このlinkを張って $S$ に $b_1$ を入れる。

次に $b_2$ を取ってきて、同じことを繰り返すのだが、$S$ には現在 $0$ と $b_1$ が入っているので、まず $0\oplus b_2 = b_2$ に向かって $0 \xrightarrow{b_2} b_2$ を張り、次に $S$ に入っていた $b_1$ を使って、$b_1 \oplus b_2$ を作れば、$b_1 \xrightarrow{b_2} b_1 \oplus b_2$ の link を張って、$b_1 \oplus b_2$ を $S$ に入れることができる。但し、もし既に $b_1 \oplus b_2$ が $S$ に入っていたら、この作業は実施せず、linkも張らない。

以下同様に、$B$ の元を順に取ってきて、それと $S$ のすべての元とを連結する作業を、$B$ の元が無くなるまで繰り返す。それが終わったら、もし張ったlinkの数が $N-1$ と一致すれば連結で、これがそのまま求める木になっているのでそれを出力して終了、もし $N-1$ より小さければ連結で無いので、$-1$ を出力して終了すればよい。

 

・・・が、なぜこれで十分なのかが全くわからない。

(1) まず、この操作で $A$ の元は明示的には作っていない。よって、作られているとすれば必ずどこかの $b_i$ と、それより以前に作成された $S$ の元 $t \in S$ とのXORで作られているはずなのだけれど、なぜそう巧い具合に $A$ の元に飛んで行ってくれるのか。重複して作成された場合は入れなければいいんだけれど、十分 $A$ の元を構成できるのが不思議。

(2) また、linkも、なぜちょうど $N-1$ 本だけ作られて木になるのか。

(3) 最後に、なぜこれが時間内に終わるのか。$N$ は最大で$2^{18} ≒ 10^5$ くらいになるので、$\mathcal{O}(N^2)$ だとアウトなんだけれど、$B$ の元を回して $\mathcal{O}(N)$、その中で $S$ の元をまわしていたら、$S$ も最大 $N$ 個くらいになるとすれば、$\mathcal{O}(N^2)$ になっちゃわない？

と、三つの疑問を以下で考えます。 

まず、一番簡単な(2)から。

これは、$S$ に新しい元が挿入されたとき、かつ、そのときにのみ、linkが追加されるので、$S$ が $\mathcal{N}$ と一致していれば自ずと、linkは $N-1$ 本。で、linkの作り方から、$S$ の元は必ず $0$ から伸びるlinkで繋がっているので、連結。 $N$ 元 $N-1$ 本連結だから、一本の木になっています。

次に、(1)。 

話を簡単にするために、$S_i$ を、$b_i$ に対する処理が終わったあとの $S$ のことととします。つまり、$S_0 = \{0\}$ で、$S_1 = S_0 \cup S_0\oplus b1$、...、$S_i = S_{i-1} \cup S_{i-1}\oplus b_i$ です。$S_{i-1} \oplus b_i$ は、$S_{i-1}$ の元と $b_i$ とのXORの元の集合とします。

さて、この作業の最初の方を観察すると、次のようになります。

\begin{array}{ccccc}
S_0    &     &     &    & \\
0    &    &     &     & \\
    &     &     &    & \\
S_1    &     &     &    & \\
0    & b_1    &     &     & \\
    &     &     &    & \\
S_2    &     &     &    & \\
0    & b_1    & b_1 \oplus b_2    &     & \\
    & b_2    &     &     & \\
    &     &     &    & \\
S_3    &     &     &    & \\
0    & b_1    & b_1 \oplus b_2    & b_1 \oplus b_2 \oplus b_3    & \\
    &         & b_1 \oplus b_3    &     & \\
    & b_2    & b_2 \oplus b_3    &     & \\
    & b_3    &     &    & \\
    &     &     &    & \\
S_4    &     &     &    & \\
0    & b_1    & b_1 \oplus b_2    & b_1 \oplus b_2 \oplus b_3    & b_1 \oplus b_2 \oplus b_3 \oplus b_4    \\
    &        & b_1 \oplus b_4    & b_1 \oplus b_2 \oplus b_4    & \\
    &         & b_1 \oplus b_3    & b_1 \oplus b_3 \oplus b_4    & \\
    & b_2    & b_2 \oplus b_3    & b_2 \oplus b_3 \oplus b_4    & \\
    &        & b_2 \oplus b_4    &                            & \\
    & b_3    & b_3 \oplus b_4    &                            & \\
    & b_4    &                    &                            &
\end{array}

すると、各回の組み合わせ総数は $1, 2, 4, 8, 16, ...$ と、新しい元を入れるたびに$2$ 倍になっていき、最後には $B$ の元のすべての組み合わせが $S$ に入ることがわかります。ですから、この方法で「$B$ の元のすべての組み合わせのXOR」は網羅できることになります。 この操作は、愚直に全組み合わせを実施すると $2^{\#B}$ 個の組み合わせができるのですが、至る所で重複が発生しています。重複した場合はlinkを張らないので、例えば、$b_8$ のターンにて挿入しようとした $b_3 \oplus b_5 \oplus b_8$ が $b_1 \oplus b_2$ と同じだったとすれば、この元は入れません。また、その次に入る予定だった $b_3 \oplus b_5 \oplus b_8 \oplus b_9$ は別の場所で $b_1 \oplus b_2 \oplus b_9$ として挿入されるので、全組み合わせから失われるわけではありません。

つまり、最終的にできあがった $S$ には、$B$ の元の全組み合わせが入っているので、これが求めたいものの全てです。これに$A$ の元が全て入っていれば連結ですし、入っていなければ $-1$ を出力します。

ということで、(2)もOKでした。

最後に (3) です。いくら至る所重複によって $\# S$ が $2^{\# B}$ よりは少なくなるとはいえ、$\# B \times \# S$ は $N^2$に近づく可能性があります。

そこで、上のアルゴリズムに一つ、$b_i \in S_{i-1}$ ならば、$S_i = S_{i-1}$ とする、つまり、$S_{i-1}\oplus b_i$ の計算をしない、という仕組みを入れます。実装上は、$S$ を使い回すようにしていれば、何もしなくていいです。

では、なぜこの仕組みを入れてもいいのか。

例えば $b_i$ を取った時点で $b_i \in S_{i-1}$ だったとすると、$i$ より小さい数列 $i_1 < ... < i_k < i$ があって、$b_ i = b_{i_1} \oplus ... \oplus b_{i_k}$ と書けているので、その先の任意の $S_{i-1}$ の元 $t$ に対し、$t \oplus b_i = t \oplus b_{i_1} \oplus ... \oplus b_{i_k}$ は $S_{i-1}$ の中に既に存在します（思い出すと、$b_i$ を処理している時点で、インデックスが $i$ より小さい $B$ の元のすべての組み合わせが $S_{i-1}$ に入っているのでした）。ですから、$b_i$ を取り出したらまずそれが $S_{i-1}$ にあるかどうか確認し、もしなければ $S_i$ を作る作業をしますが、既にあれば何もせずに次の $b_{i+1}$ に移ることができます。

また、$b_i$ が $S_{i-1}$ に入っていない、という事態が起こった場合、そのあとの $S_{i-1}$ の元との掛け合わせは、すべてが $S_{i-1}$ にとって新しい元になっていきます。これは、$S_{i-1}$ が、XOR演算において $\{b_1,...,b_{i-1}\}$ の組み合わせのすべてが入っていることから、$(\mathbb{Z}/2\mathbb{Z})^n$ の中での閉じた部分空間になっていること、そこに $b_i$ が入っていないということは、$b_i$ は $(\mathbb{Z}/2\mathbb{Z})^n$ 内での新しい基底になっていて、その結果、部分空間の次元が一つ上がる。つまり、$S_{i-1} \oplus b_i$ は全てが $S_{i-1}$ からはみ出していて、 $S_i$ は$S_{i-1}$ と $S_{i-1} \oplus b_i$ との、重複のない和集合になります。ところで、$(\mathbb{Z}/2\mathbb{Z})^n$ は$n$ 次元だったので、部分空間が拡大するのは $n$ 回だけ。つまり、 $b_i$ が $S_{i-1}$ に入っていないという事態は $n$ 回しか発生しないので、$S_{i-1} \oplus b_i$ の処理をする回数も $n$ 回だけであり、その回毎に $S_i$ の大きさが $2$ 倍になるのだから、結局追加処理は $b_i$ が $S_{i-1}$ に入っているかどうかを確認する $\#B$ 回と、$S$ に元を追加する $2^n = N$ 回しか発生しないことになります。

代数っぽくない書き方をすると、$b_i$ が入ってくるまでの $S$ は、$n$ 個ある bit のうち一部がすべて止まっているか、もしくはいくつかがすべて同期してON/OFFしているなどしています。例えば、$b_1 = 1, b_2 = 2, b_3 = 4$ だったとすると、最初の $3$ bitだけが動き、残りの $n-3$ bitは止まっています。また、例えば $b_1 = 5, b_2 = 6$ だったとすると、この二つから作られる $S$ は、$\{0, 3, 5, 6\}$、二進数で書くと $\{000,011,101,110\}$ で、最上位bitは下位 $2$ つの bit の和（mod 2）になっている、つまり、独立して動いていない。そこに、これらとは独立した新しい元 $7$ が入ってくると（$7 = \mathrm{0b}111$ は、最上位bitが下二つの和になっていない）、最上位bitがこれまでと異なる元が生まれます。具体的には、$0\oplus 7 = 7$, $3\oplus 7 = 4$, $5\oplus 7 = 2$, $6\oplus 7 = 1$ の四つの元が生まれ、かつ、これらは全て元の $S$ に入っておらず、新しく $S$ に追加されます。二進数で見てみると、 $\{7,4,2,1\}$ $=$ $\{111, 100, 010, 001\}$ で、全て最上位bitが下二つの和になっていません。この例ではたまたま、元の $S$ の性質が「最上位bitが下二つの和になっている」というものでしたが、$B$ がどのような集合だったとしても、新しい次元が生まれる前はどれかのbitが他のbitに従属して動いており、新しい世界が広がるとその瞬間、$S$ に一次元分のすべての元が一気に投入されることになります。で、そのような回数は $n$ 回だけ、次元が一つずつ拡大して $n$ になるまで、ということになります。

ということで、(3)もクリアしました。

と、ここまで考えてきてやっと、ユーザー解説にさらっと「基底は高々 $n≤18$ 個であることから、このような頂点 a は余裕をもって全探索出来ます」と書いてあることの意味が理解できました。なるほど確かに。

以上、備忘録でした。

最後にSさん、コード見せて頂きました。勉強になりました。ありがとうございます！

参考（Sさんのコードを元に改変）： https://atcoder.jp/contests/zone2021/submissions/22264498