ABC141 バチャメモ - tinumu's reminder

atcoder.jp
Fめっちゃムズいじゃん

A

バグらないように書く

B

まあstringでfindすると楽に書けそう

C

Qを全要素引いておいて、正解したら1ptあげれば答えが出る

D

消したら一番お得なのは明らかに一番大きい要素
priority_queueに入れてQ回回します

E

LCSのDPに対して $i \lt j$ のとき、 $j-i$ までの長さにしかならないという制約を課すと解ける
dpを観察すると実はlenを決め打ちしてn回程度dpをしているのと変わらない。
$j-i$ は固定であるため、dpは壊れてない(よくわからない説明だけど)。

各接頭辞に対してz_algorithmを用いても解ける。

F

Fは大事なので大きく見出しをつけます

赤の全xorを $A$ , 青の全xorを $B$ とすると、
$A+B=A \oplus B + (A \cdot B) \times 2$ となる(ここではand を $\cdot$ としている)。

$A \oplus B = S$ , すなわち全ての要素の xor を取った値 $S$ について考える。
ここから桁 $i$ について述べる時、 $i$ の添え字をつける。
$S_i=1$ の時は、 $2^{S_i}$ を無条件に答えに足すことが出来る。
なぜなら $A_i=0$ のとき、 $B_i=1$ であり、 $A_i=1$ のとき、 $B_i=0$ であるため、この桁の和は必ず $1$ になるからである。

$S_i=0$ の時は、 $A_i=1$ に調整できれば、 $B_i=1$ に出来る。
そのため、 $A$ を最大化する問題となる。
まず、左側の桁から $1$ できるか判断して $1$ にしていくと、最適であることがわかる。
ただ、 $1$ を作れるかどうかがすぐにはわからない。

ここで、配列に対して掃き出し法を利用する。
そうすると、各桁について $1$ 要素だけに出来る部分が出来る。これを自由度のある桁と呼ぶことにする。
左側から自由度のある桁について、 $1$ を入れていけば、 $A$ の最大化すなわち $A \cdot B$ の最大化が出来、これを $2$ 倍した値を $S_i=1$ の時の解に足してあげればこの問題は解くことが出来る。

F のソース

void gaussJordan(vll &A, ll size) {
	int s = 0;
	for (ll b = size-1; b >= 0; b--) {
		//探す
		ll pos = -1;
		for (int i = s; i < A.size(); i++) {
			if ((A[i]>>b) & 1) { pos = i; break; }
		}
		if (pos == -1) continue;
		if (pos != s) swap(A[pos], A[s]);
		//消す
		for (int i = 0; i < A.size(); i++) {
			if (i != s && ((A[i]>>b) & 1)) A[i] ^= A[s];
		}
		s++;
	}
}

void Main() {
	ll N; cin >> N;
	vll A(N); cin >> A;
	ll xd = 0;
	ll size = 60;
	ll ans = 0;
	for (auto &v : A) xd ^= v;

	for (int i = 0; i < size; i++) {
		if ((xd>>i) & 1) {
			ans += (1ll<<i);
			for (auto &v : A) v &= (~(1ll<<i));
		}
	}
	gaussJordan(A, size);
	
	ll xd2 = 0;
	for (auto &v : A) xd2 ^= v;
	cout << ans + xd2 * 2 << endl;	
}

感想

なんかEまでは早解きができたな
Fみたいなのは、すごい典型感があるので、ちゃんと抑えたい
特に掃き出しするところとか、やっとかんと、やばいだろ