公式

X - XOR Bag 解説 by sounansya

tatyam さんの解説 のほうが見通しが良いと思います。

この解説では多重集合のことを単に集合と呼びます。

\(A_1,A_2,\ldots,A_N,X\) を \(\mathbb{F}_2^{60}\) 上のベクトルとして見做し、これらのベクトルの加算を \(\mathrm{XOR}\) で定義した線型空間とします。Alice の獲得した整数の集合を \(S\) とすると、Alice が勝つ条件は \(X \in \text{span}(S)\) となります。

\(\mathbb{F}_2^{60}\) 上の要素からなる集合 \(E\) に対し、\(r_2(E)\) を以下の条件を全て満たす集合の組 \((I_0,I_1)\) 全てに対する \(|I_0|+|I_1|\) の最大値とします：

  • \(I_0,I_1 \subset E\)
  • \(I_0 \cap I_1 = \empty\)
  • \(I_0,I_1\) はそれぞれ線型独立である

実は、本問題で Alice が勝つ必要十分条件は \(E_1=A \cup \lbrace X\rbrace,E_2=A \cup \lbrace X,X\rbrace\) として \(r_2(E_1)=r_2(E_2)\) と表すことができます。以降はこれを証明します。

Matroid Union Theorem より、\(\displaystyle r_2(E)=\min_{U\le \mathbb{F}_2^{60}} (2\dim U+|E\ \backslash \ U|)\) が成り立ちます。ここで、\(U\le \mathbb{F}_2^{60}\) は \(U\) が \(\mathbb{F}_2^{60}\) 上の線型空間であることを意味し、 \(|E\ \backslash \ U|\) は \(E\) の中で値が \(U\) に属さない要素の個数を重複込みで数えた個数です。

[1] \(r_2(E_1)=r_2(E_2)\) のとき

\(r_2(E_2)=2\dim U+|E_2\ \backslash \ U|\) を満たす \(U\le \mathbb{F}_2^{60}\) を取ります。

もし \(X\not \in U\) なら \(r_2(E_1) \le 2\dim U+|E_2\ \backslash \ U| < 2\dim U+|E_1\ \backslash \ U|=r_2(E_2)\) より矛盾が生じるので \(X\in U\) です。

したがって、\(r_2(E_1)=r_2(E_2)=2\dim U+|E_1\ \backslash \ U|\) となるので、\(E_1\) には \(X\) を含む空間 \(U\) の互いに素な \(2\) つの基底 \(C_0,C_1\) が存在します。

さらに、基底をうまく取ることで \(X \in C_0\) とすることができます。これは、もし \(X \in C_1\) なら \(C_0\) と \(C_1\) を入れ替えればよく、\(X\not \in C_0,X\not \in C_1\) なら \(X\) を \(C_0\) で表したときに現れる要素のうちどれか \(1\) つと \(X\) を入れ替えれば良いからです。

\(H=\text{span} (C_0\ \backslash\ \lbrace X\rbrace)\) とすると、\(\dim H=\dim U-1\) より \(a \not \in H\) を満たす \(a \in C_1\) が存在します。Alice は初手でこの \(a\) を取ることにします。

Alice は \(a\) を初手で取ったので、以降は商空間 \(U'=U/\langle a \rangle\) を考えます。この空間で \(C_0 \ \backslash\ \lbrace X\rbrace\) と\(C_1 \ \backslash\ \lbrace a\rbrace\) は互いに素は \(2\) つの \(U'\) の基底となります。したがって、Bob の手番では黒板に \(U'\) の互いに素はな基底が \(2\) 組残っている状態となります。

したがって、以下の補題を示せば良いです：

Bob を先手として、ある線型空間 \(W\) の互いに素な \(2\) つの基底が大きな黒板に書かれている場合、Alice は必ず小さな黒板で \(W\) 全体を張ることができる。

\(2\) つの基底を \(D_0,D_1\) とします。

Bob が初手で \(b\in D_0\) を消したとします。このとき、\(c \not \in \text{span} (D_0 \ \backslash \ \lbrace b\rbrace)\) を満たす \(c \in D_1\) が存在します。Alice はこの \(c\) を取ることにします。すると、\(D_0 \ \backslash \lbrace b\rbrace,\ D_1 \ \backslash \lbrace c\rbrace\) は商空間 \(W /\langle c \rangle\) の \(2\) つの基底になります。

Bob が \(D_1\) の要素を消した場合も同様の議論ができます。\(D_0,D_1\) どちらにも属さない要素を消した場合、\(b\in D_0\) を任意に取り同じ議論をすれば良いです。

以上より、帰納法から補題が従うため、\(r_2(E_1)=r_2(E_2)\) が成り立つならば Alice が勝つことが分かります。

[2] \(r_2(E_1)\neq r_2(E_2)\) のとき

この場合 \(r_2(E_2)=r_2(E_1)+1\) です。

\(r_2(E_1)=2\dim U+|E_1\ \backslash \ U|\) を満たす \(U\le \mathbb{F}_2^{60}\) を取ります。

\(r_2(E_1)=2\dim U+|E_1\ \backslash\ U|\) を満たす \(U\) に対し、もし \(X \in U\) ならば \(r_2(E_2) \le 2\dim U+|E_2\ \backslash\ U|=2\dim U+|E_1\ \backslash\ U|=r_2(E_1)\) となり矛盾します。したがって \(X\not \in U\) であり、\(r_2(E_2)=r_2(E_1)+1=2\dim U+|E_2\ \backslash\ U|\) が成り立ちます。

ここで、\(r_2(E_2)\) を達成する互いに素な線型独立集合 \(I_0,I_1\) を取ります。この \(I_0,I_1\) に対し、

  • \(I_0 \cap U\) 、\(I_1\cap U\) はそれぞれ \(U\) の基底
  • \(E_2\ \backslash \ U\) の全ての要素が \(I_0\cup I_1\) に含まれる

ことが分かります。よって、商空間 \(\mathbb{F}_2^{60}/U\) において \(I_0\ \backslash\ U,I_1\ \backslash\ U\) はそれぞれ線型独立です。

小さい黒板に書かれた整数の集合を \(S\) として、Bob は自分の手番の終了時に商空間 \(W=\mathbb{F}_2^{60}/(U+\text{span}(S))\) 上で以下の条件を維持することを考えます：

  • 大きい黒板に残っている要素は、ゼロベクトルと互いに素な \(2\) つの集合 \(C_0,C_1\) に分け。さらに、その上で \(C_0\cup \lbrace X\rbrace,C_1\cup \lbrace X\rbrace\) を共に線型独立にできる。

この条件が満たされると、 \(X\not \in U+\text{span}(S)\) から \(X\not \in \text{span}(S)\) が言えるため、Bob が必ず勝つことが証明できます。

証明：

この条件が満たされている状態から Alice がどのように操作しても Bob が適切に操作することで再度この条件が満たされるようにできることを証明します。

Alice が現在の商空間でゼロベクトルとなる要素を取った場合、商空間は変化しません。したがって、Bob は（残っているならば）任意の \(1\) 要素を消せば良いです。

次に、Alice が \(a\in C_0\) を取った場合を考えます。Alice が \(a\) を取った後の商空間は \(W'=W/\langle a \rangle\) です。\(C_0\cup \lbrace X\rbrace\) が \(W\) 上で線型独立なので、\((C_0\ \backslash \ \lbrace a\rbrace)\cup \lbrace X\rbrace\) も \(W'\) 上で線型独立です。特に、\(W'\) 上でも \(X\) はゼロベクトルではないです。

あとは \(C_1\cup \lbrace X\rbrace\) の独立性を維持できれば良いです。

[1] \(a\not \in \text{span}(C_1\cup \lbrace X\rbrace)\) のとき

\(C_1\cup \lbrace X\rbrace\) は \(W'\) 上で線形独立なので、Bob は残りの任意の要素を消して良いです。

[2] \(a \in \text{span}(C_1\cup \lbrace X\rbrace)\) のとき

\(C_1\cup \lbrace X\rbrace\) は \(W\) 上で線形独立なので、\(\displaystyle a=\lambda_XX+\sum_{b\in C_1}\lambda_bb\) \((\lambda_X,\lambda_b\in \mathbb F_2)\) と一意に表示できます。

\(a,X\) は線形独立なので、\(\lambda_b=1\) となる \(b\in C_1\) が少なくとも \(1\) つ存在します。Bob はそのような \(b\) を消す操作を行うことにします。

すると、表示の一意性から \(a\not \in \text{span}((C_1\ \backslash\ \lbrace b\rbrace)\cup \lbrace X\rbrace)\) となります。よって、\((C_1\ \backslash \ \lbrace b \rbrace)\cup \lbrace X\rbrace\) は \(W'\) 上で線形独立となり、条件が保たれます。

以上を繰り返すことで Alice がどのように操作しても Bob が勝つことができます。

以上より、Alice が勝つ必要十分条件は \(r_2(E_1)=r_2(E_2)\) であることが証明できました。

あとは \(r_2(E_1),r_2(E_2)\) を高速に計算すれば良いです。

これは線型マトロイドと分割マトロイドの最大共通独立集合問題です。適切に実装することで \(O(N\log^2\max A)\) や \(O(N\log\max A)\) 時間になります。