AGC045 - A - Xor Battle - Senの競技プログラミング備忘録

atcoder.jp

概要

以下の問題がTケース与えられるので、それについてT回回答すること。

長さNの配列{A_i}が与えられる。そして、もう1つ長さNの文字列Sが与えられ、それは0と1のみに構成される。0さんと1さんの2人はこの数列を使って、次のようなルールでゲームを行う。

$x$ という変数を用意し、 $x=0$ で初期化する。
S[i]が0だったら0さんの手番、1だったら1さんの手番
自分の手番では、 $x \leftarrow x \otimes A_i$ を行うか、何もしない。

各々最善を尽くした時に誰が勝者になるのでしょう？

制約：
1 <= T <= 100, 1 <= N <= 200, 1 <= A[i] <= 10^18, |S| = Nで0か1で構成されている。

解法

以下は全部1-indexで解説する。

このようなゲーム問題では、詰んだ局面から逆算するのが常であるので、詰む=勝ち確定の局面をいくつか考察していく。

S="*1"(最後が1のような文字列)の場合

この場合は、明らかに1さんが勝つ。なぜならば、最後の手番が回ってきたとき

$x = 0$ ならXORをする。この時 $A_i \neq 0$ より必ず $x \neq 0$
$x = 0$ ならXORをしない。何もしなくても勝てるからである。

S="*10"(最後が10のような文字列の場合)

この場合は、1さんがN-1手目で $x=0$ か $x=A_{i-1}$ を作ってしまった or 作らざるを得なかった場合、0さんはXORをしない or することで必ず $x=0$ にすることができる。
逆に、1さんがN-1手目で $x\neq0, x\neq A_{i-1}$ を満たせれば1さんの勝ちが確定するのだ。

しかし、これだけではまだ難しい。なぜならばN-1手目にたどり着くまでには1さん以外にも0さんの手番が存在しているので、1さんが一意に $x$ の値を決められるとは限らないので、考えるのが難しいと思えるからだ。

では、逆に今 $i$ 手目を見ているとして、 $1からi-1手目$ に関係がなくいくつかの局面での勝ち負けを断定する方法はあるのだろうか。これについて掘り下げると、どうやら $A_i$ の値が重要らしい(情報量0の発言)。

ここで、 $i=N-1$ の時、 $A_{N-1}=A_N$ の時を考える。この時、最後の2手についてだけ言うのであれば、お互いに打ち消せる手であると認識できる。(XORは2回すると元に戻る。1さんがやる->0さんがやる or 1さんがやらない->0さんがやらない)

逆に、 $A_{N-1}\neq A_N$ の場合ではどうだろうか。実はこの時は1さんの勝利が確定するのである。 $A_{N-1}$ を $A_N$ では打ち消せないことを解釈すると以下のようになる。

$A_{N-1}$ にはどこかの桁などで $A_N$ と違っていて、その結果お互いに打ち消すことが不可能。その違う桁の位の集合をXとする。
$N-1$ 手までに、Xに入っている桁の位たちが、 $x$ ですべて立っていなかったら、1さんは $A_{N-1}$ をXORすることで立てることができる。
$N-1$ 手までに、Xに入っている桁の位たちが、 $x$ で1つでも立っていたら、1さんは手番をパスすれば、0さんは必ず $N$ 手目でそれを消すことができない。

よって、 $A_{N-1}\neq A_NかつS=(0+1)^*10$ の場合、1さんが勝利確定である。

逆に、 $A_{N-1}=A_N$ の時は、まだ勝負はわからない。これは最後の2手を削って再び考えることができる。

S="*100"、(最後が...100で終わる)の場合

この場合に先ほどの考えを適用させて考えてみる。この時、先ほどの $A_{N-1}=A_N$ であるか?という条件は、少し考えると、「 $A_{N-1}$ と $A_N$ を自由にXORして、 $A_{N-2}$ を作れるか？」というのにかわるとわかる。

つまり、 $A_{N-1}$ と $A_N$ をそれぞれ1回までXORに使用可能なときに、 $A_{N-2}$ を作れるか？という問題に対して、

作れる=まだ勝負はわからないとして、もう1つ前を見ていく。
作れない= $A_{N-2}$ を1さんがXORすれば勝ち確定。

と先ほどのS="*10"から拡張できる。

これをさらに拡張すると、以下のような事実が得られる。

$S=(0+1)^*10^+$ について、1が $i$ 手目だとして、 $A_i$ を $A_{i+1}からA_{N}$ まで各々最大1回まで使ってXORして、

作れる=勝敗決定できないので、 $i-1$ 手目を見ることになる。( $i-1$ 手目が0さんの手番なら、これより前の1さんの動作に対して使えるかもしれない切り札が1つ増えるだけである)
作れない=1さんがこれをXORすればいいので、1さんの勝ちである。

これで勝敗決定問題をかなり一般化できた。

ところで、理系大学生などの方は、これが線形代数の線形空間、基底という概念とこれは非常に似ていることに気づかないだろうか？

実は、XORという演算は各桁に分解すると、「mod 2の上で行われている演算」であると言い換えることができ、今回の場合 $A_i \leq 10^{18} \approx 2^{60}$ であることから、 $A_i$ と $x$ のXORは、60次元のmod 2上でのフィールドそのものであるとみなせる。

そして、いくつかのベクトルを好きな個数だけ、自由に足し引き出来るとき、指定したベクトルが作れるか？は明らかに線形空間に含まれるベクトル、ひいては基底で求められるベクトルが作れるか？と全く同じことである。

というわけで、後は線形代数の問題を解決できれば、この問題は解けたと言えるだろう。

線形空間と基底については以下の解説サイトなどで参考してください。

線形空間(ベクトル空間)を画像と具体例で解説 | 大学1年生もバッチリ分かる線形代数入門

【線形空間編】基底と次元と成分 | 大学1年生もバッチリ分かる線形代数入門

つまり、
$\vec{x} \in S$ の $\vec{x}$ を毎回たかだか1本まで足すことができるmod 2の60次元の線形空間で、 $\vec{y}$ を作れるか？という問題と全く同じである。

まず、 $\vec{x} \in S$ を基底にまとめ直そう。( $x_3=x_2 \otimes x_1 | x_1,x_2,x_3 \in S$ があるのならば、 $x_3$ は不要。)これは、すべての基底候補のベクトルを縦or横に並べた行列を作って、行列の基本変換を施すことで変形できる。

ちなみに、行列の基本変換といったが、これはmod 2の上なので数倍にする必要性はなく、結局のところある行 or 列を別のに足すことを繰り返すことである。(XORによる行列の特徴でもあり、これを利用して実装はスマートに書ける)
行列の基本変換を施すことで、逆三角行列という形に持っていくことができる。これは以下のような形で、

f:id:Sen_comp:20201120040748j:plain

対角線上にはすべて1が乗っており、それ以外は0であるという性質を持つ。(右端の対角線が切れている部分は無視する)この性質から、「 $\vec{y}$ でその桁に+1(mod 2)をしたいときには、決まった基底を選ぶとできる」という重要な性質が導ける。

今まででは、いくつかの候補のうちから総当たりで2の累乗回最悪見る必要があったが、基底に整理して逆三角行列の形で見れば、基底を上から見て、採用or不採用を一意に選べるので、計算量は大きく改善したことになる。
これで掃き出し法を行った結果、新しく加えたいベクトルの行 or 列が行列の基本変換によって $\vec{0}$ となっていたら、それは既存の基底で作れることを表していて、逆にならなかったら、既存のでは作れないということになる。(これが1さんの手番の時ならば1さんの勝利が確定し、0さんならばこれを基底として線形空間 $X$ に加えればよい)

ところで、もう1つ考慮するべき点がある。一般的には、行列の基本変換を施して、基底を1組作ったときには、「変換前で作れたすべてのベクトルと、各基底の任意の実数倍の和で作れるベクトルは全く同じ線形空間をなす」ということであるが、任意の実数倍というところと、今回の問題の各 $A_i$ はたかだか1回までしか使えないというところで少し違うのだ。

しかし、今回に関してはそれは安全である。なぜならば、mod 2の世界であるので、係数自体は整数である上に、0か1しか係数にありえないとわかる。これは、同じ数に対して、XORが2回したら0になることに起因する性質である。

なお、mod 2の上での線形代数は普通の線形代数と違って多くの便利な性質があり、計算もbit演算を用いて簡便と高速化ができるので、普通の線形代数計算ライブラリとは別個な実装がされていることが多い。

Gauss-Jordan の掃き出し法と、連立一次方程式の解き方 - けんちょんの競プロ精進記録

解法のまとめ

ここまでの話を整理すると以下のようになる。

後ろから見ていく。
$S_i=0$ ならば、線形空間 $X$ に $A_i$ をベクトル化したものを加える。加える際は、そのたびに基底を作る掃き出し法を行って逆三角行列を作る。
$S_i=1$ ならば、線形空間 $X$ に $A_i$ をベクトル化したものが含まれるか(つまり作れるか)を判定し、作れない->1さんの勝ち、作れる->未定
これを計N回行い、それでも1さんの勝利が確定しない場合は、0さんが勝つ。

実装

掃き出し法によって規定を作る部分はこのように実装した。

vector<ll> V;//この線形空間に新た加わるベクトルが含まれているか？を計算するために行列の基本変形で対角線の片側だけに並ぶあの形に掃き出し法を使う。
//掃き出し法自体はXORなのでmod2の上でできるbit演算を行う。
auto get_MSB = [](ll x) {return x & (-x); };
auto contain_in_V = [&](ll new_v) {
	for (int i = 0; i < V.size(); i++) {
		if ((get_MSB(V[i]) & new_v))
			new_v ^= V[i];
	}
	//0になったら、既存の基底で作れちゃうということなので追加する必要なし。
	return new_v;
};
auto insert_to_V = [&](ll new_v) {
	ll ret = contain_in_V(new_v);
	if(ret == 0)return;
	V.push_back(ret);
};