AtCoder Grand Contest 045-A Xor Battle
問題へのリンク
状況
2020/08/15 のあさかつで出題されました． 他の問題で時間がかかって，この問題まで手が回りませんでした．
この問題自体は，コンテスト時に解けていましたが，実行時間がだいぶかかりました (1.3秒)． 解説 を斜め読みした感じでは，想定解と同じ方針だと思うのに， なぜこんなに時間がかかるのか不思議に思いましたが，それ以上追求していませんでした．
今回，他の人のソースを読んでみて，なるほどこれは良くなかった，とわかりました．
解法
$F_2$ を，集合 $\{0, 1\}$，和は XOR，積は AND の体とする． $V$を，$F_2$の長さ60のベクトルがつくる，係数体が $F_2$のベクトル空間とする． $A_i \leq 10^{18} < 2^{60}$ なので，各 $A_i$ は$V$の要素とみなせる． $\{ A_j \mid i < j \leq N \}$ の張る部分空間を $V_i$ と書くと，第 $i$ ラウンドにおける値が $x$ のとき， 人0 が勝つ必要十分条件が $ x \in V_i $ であることが，後ろからの帰納法でわかる．
実装
上の解法を，持っていた行列のライブラリを使って，そのまま実装したのがよろしくありませんでした． $i$ を後ろから見ていって，$A_i$ から $A_N$ までの (本当の) ベクトルをならべた行列を作って， 掃き出し法で rank を計算していく．人1 の手番のときに，rank が増えることがあれば人1の勝ち． そういうことがなければ，人0の勝ち，というように実装していました． もう少しは工夫したのですが，まあ本質的にはこういうコードでした．
改良
別に「上三角」などにする必要はないわけで，要は， 初めて出てくる非0成分のインデックスが重複しないようにしていれば，良かったのです．つまり:
0でないベクトル$v = (v_i)_i $ に対して，$\text{msb}(v) = \min\{ i \mid v_i \neq 0\}$ と書きます． ベクトルの集合 $X$ が，$v, w \in X$ ならば $\text{msb}(v) \neq \text{msb}(w)$ を満たすときに，$X$ を良い基底とか いうことにしますか．このとき， ベクトル $v$ が 良い基底$X$ の張る空間に属するかどうかを判断するには， $v$ の非0 成分を順に見て，そこが msb になっている $X$ の要素 $x$ があったら， $x$ の適当な定数倍を $v$ から引いて ($F_2$ なら単に $v$ に $x$を足して) いくことを繰り返して0になるか見れば良く， $v \not\in X$ だったときには，この計算の結果のベクトルを $X$ に加えれば，$X \cup \{v\}$の張る空間の良い基底になる， というわけです．
こう考えれば，今回の問題では，実装上，ベクトルにする必要はなく整数のままで扱え，上の msb は，実際に最上位ビットです．
コード
ということで，そういうふうにコードを書きました．実行時間は11msでした．
