AGC045-A Xor Battleを復習中。

解説に書いてある原理としては簡単で、iラウンド目の時点でxがその値なら人0が勝つ、ようなiラウンド目の時点でのxの値の集合をDPで考えて後ろから埋めていくというものだ。自然な発想ではある。

人0にしても人1にしても$x \to x$と$x \to x \oplus A_i$という2つの選択肢がある。

選ぶ人が人0の場合は$x$か$x\oplus A_i$がどっちかしら$DP_{i+1}$に含まれていれば、そこに向かえば勝利できる。つまり

\[DP_{i} = \{ x | x \in DP_{i+1} \lor x \oplus A_i \in DP_{i+1} \} = DP_{i+1} \cup \{ v \oplus A_i | v \in DP_{i+1} \} \]

となる。

選ぶ人が人1の場合は、$x$か$x\oplus A_i$がどっちかしら$DP_{i+1}$に無ければそのようにすることで人0の敗北が確定する。逆にどっちも$DP_{i+1}$に含まれていれば人0が勝利が確定する。つまり、

\[DP_{i} = \{ x | x \in DP_{i+1} \land x \oplus A_i \in DP_{i+1} \} = DP_{i+1} \cap \{ v \oplus A_i | v \in DP_{i+1} \} \]

となる。

解説で$A_i \in DP_{i+1}$かどうかで場合分けしておりそこの理由を考えて悩んだのだが、ここで線形代数の知識が生きてくる。まず、今までの所$A_i$をXorするか否か、という選択肢で集合が大きくなってきている訳なので、集合$DP_{i+1}$は加法をXorとする線形空間として見なすことができる。(乗法は良く分からんけど01の2値と普通の掛け算とかで適当に定義できるはず)

$DP_{i+1} $と$ \{ v \oplus A_i | v \in DP_{i+1} \}$の共通部分を求めたい訳なのでその両方が線形空間なら話がしやすいのだが、$A_i \notin DP_{i+1}$の場合$\{ v \oplus A_i | v \in DP_{i+1} \}$の空間は切片が付いたような感じになり線形空間でなくなる。なんてこった！

$A_i \in DP_{i+1}$でさえあれば$\{ v \oplus A_i | v \in DP_{i+1} \}$は線形空間となり、そしてそれはそもそも$DP_{i+1}$と一致する。(この辺も初学者には非自明かもしれない気もするがどうだろう？)こういう訳で$A_i$が$DP_{i+1}$という線形空間に含まれるのなら$DP_i=DP_{i+1}$として良い。その判定計算に掃き出し法とかが使える訳だ。

さて、解説に書いてあるが$A_i \notin DP_{i+1}$ならばなぜ$x$と$x \oplus A_i$の少なくとも一方が$DP_{i+1}$に含まれないと言えるのだろうか？つまり、なぜ$DP_{i+1} \cap \{ v \oplus A_i | v \in DP_{i+1} \} = \emptyset$なのだろうか？これも線形代数の語彙で考えると分かりやすい。

$V=DP_{i+1} \cup \{ v \oplus A_i | v \in DP_{i+1} \}$という線形空間を考えると、$A_i \notin DP_{i+1}$という前提を踏まえれば$\{ 0, A_i \}$は$DP_{i+1}$の補空間となることが分かる。これでは$DP_{i+1}$と$\{ v \oplus A_i | v \in DP_{i+1} \}$は交わろうはずもない。ということで$DP_{i+1} \cap \{ v \oplus A_i | v \in DP_{i+1} \} = \emptyset$だと言い切れるのだ。

途中まで「$U,V$を線形空間、$a$を何らかの数として、$U \cap \{a + v | v \in V\}$だったら交わることもあるよね？」という風なところでドツボにはまっていたのだが、この場合は$U=V$なのでその可能性はない。

---

ハクメイとミコチ7巻、幼年期の終わり(光文社古典新訳文庫)を購入した。本屋には来たが金欠なので何買うか迷った末。

マルセル・モースの贈与論、シェイクスピアのリア王、ホメロスのイーリアスあたりもその内買いたい。が、それはある程度積読を消化してからにしよう…

あと最近オイディプス王を読んで中々楽しめたのだが、たまたま置いてあったアンティゴネーをパラパラめくったらこれもヤバい面白いやつだとなったので危険だった。後日談まであるの供給完璧かよ…12.1話かよ…

---

基底Aと目指す値bを与えればAのXOR結合でbを表す方法を脳死で求められるライブラリを作った。

template<auto MAX_BIT>
struct BitMatrix {
	int H, W;
	vect<bitset<MAX_BIT>> val;
	BitMatrix(int m = 1, int n = 1) : H(m), W(n), val(m) {}
	inline auto& operator [] (int i) { return val[i]; }
};

template<auto MAX_BIT>
int GaussJordan(BitMatrix<MAX_BIT>& A, bool is_extended = false) {
	int rank = 0;
	for (int col = 0; col < A.W; ++col) {
		if (is_extended && col == A.W - 1) break;
		int pivot = -1;
		for (int row = rank; row < A.H; ++row) {
			if (A[row][col]) {
				pivot = row;
				break;
			}
		}
		if (pivot == -1) continue;
		swap(A[pivot], A[rank]);
		for (int row = 0; row < A.H; ++row) {
			if (row != rank && A[row][col]) A[row] ^= A[rank];
		}
		++rank;
	}
	return rank;
}

template<auto MAX_NUM, auto MAX_BIT>
int linear_equation(const vect<bitset<MAX_BIT>>& A, const bitset<MAX_BIT> b, vec& res) {
	//int m = A.H, n = A.W;
	int m = MAX_BIT, n = A.size();
	BitMatrix<MAX_NUM + 1> M(m, n + 1);
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) M[i][j] = A[j][i];
		M[i][n] = b[i];
	}
	int rank = GaussJordan(M, true);

	// check if it has no solution
	for (int row = rank; row < m; ++row) if (M[row][n]) return -1;

	// answer
	res.assign(n, 0);
	for (int i = 0; i < rank; ++i) res[i] = M[i][n];
	return rank;
}

template<auto MAX_NUM, auto MAX_BIT>
lint keq_xor(const vect<bitset<MAX_BIT>>& a, vec& x, const bitset<MAX_BIT> b) {
	return linear_equation<MAX_NUM>(a, b, x);
}

template<auto MAX_NUM>
lint keq_xor(const vec& a, vec& x, const lint b) {
	const auto BIT_NUM = CHAR_BIT * sizeof(lint);
	vect<bitset<BIT_NUM>> a2(a.size());
	rep(i, a.size())
		a2[i] = a[i];
	return keq_xor<MAX_NUM>(a2, x, bitset<BIT_NUM>(b));
}

ガウスジョルダンのアルゴリズムの実装などはけんちょんブログからありがたくパクらせていただいた。

---

Codeforces Global Round 14に出た。やっぱりAtcoderよりもCodeforcesの方で苦戦しやすい気がする。言語の問題ではなく出題傾向で。

Aはとりあえずソートした上で、xの条件に引っかかっていないか確認し、引っかかっていれば数列をシフトする(先頭をとって後ろに詰める)。同じ数値の$w_i$が並んでいたり、$\Sum w_i = x$だったりしない限りは必ず境界線がずれるので、条件を満たすことが可能ならばこのやり方で見つかる。

Bは全部2ピースの正方形にして並べる場合と全部4ピースの正方形にして並べる場合を考えればいい。平方数かを判定して終わり。サンプルがなかったら4ピースのケースに気付けなかったかも…

Cは大分悩んだ。要するに最小と最大の差を最小化したいので、ブロックを高さで降順にソートし、優先度付きキューで低い塔を選んで詰んでいく。こうすれば後になるにつれて微調整されていくのでどうにかなるだろうという直感だが、未証明。

Dはアドホックな実装を色々やるやつだった。とりあえずそのままマッチングできる左右の対はそのままマッチングして損はないのでそうする。そうするとそのままマッチングできないやつらが余る。左右の数が均等なら片方の色を変えればいいのだが、左右の数が偏っている場合、その偏りの分は靴の左右を変えなければならない。色まで変えるコストを負いたくないので、偏っている側を見て同じ色が複数あればそれは左右を変えてマッチングするのに回す。

E以降は不明。負け！