ACPC2020 Day2
コンテストサイト
Aizu Online Judge Arena
A
計算するだけ
B
O(NQ) で十分間に合う。問題タイトルがひっかけ
C
出次数0の頂点が2つ以上あると、どちらかが壊れたときに a の値が等しくて区別できない。
v < w より、とりあえず 1 -> 2 -> 3 -> ... -> n を繋ぐ。すべての機械の元の値が変わるとよさそうなので 1->3, 1->4, 1->5 ... を追加する
D
要復習
E
bの和は大きくなりすぎても問題ない。wの和をインデックスにして、bの和の最大値を持つDP
F
上向きの三角形を複数加算するようなグラフになる。
max(0, H(1-2|x-X|/R)) より、
X - R/2 <= x <= X の区間では右上がりの1次関数が加算される。
X <= x <= X + R/2 の区間では右下がりの1次関数が加算される。
X-R/2, X, X+R/2 のタイミングにイベントを発生させて、1次関数の合計を求める
G
まず連結成分を作る。連結成分の四角（bounding box）を作ると、その中のどのx座標にも点を追加できる。つまり、x座標だけでも交差するような連結成分同士は点の追加で接続できる。その交差する範囲に片方だけ点が存在する座標も含まれているので1点追加でよい。（y座標についても同様）
あとは点1の連結成分から点Nの連結成分までの最短距離を求める必要があるが、辺の数が爆発しないようにデータ構造が必要。
セグメントツリーをX座標、Y座標の2通り作る。
一つのセグメントは四角の集合
四角i = (x0, y0) * (x1, y1) について、x0 <= x <= x ならばセグメント x は四角iを含む。
点1の四角からスタートして、[x0, x1]の範囲の四角を全て列挙し、BFSの1辺とする。その四角はセグメントツリーから取り除く。
どの四角もセグメントツリーの中の O(log |x|) 個のノードにしか含まれない。また、各x座標を1回ずつしか検索しない。
セグメントの融合の計算量が悪いので融合をしないタイプのセグメントツリーになっている。
J
クエリ毎に差分を求める。必要な情報は頂点の次数d(v)と、
隣接点の次数和 nd(w) := sum_{w in N(v)} d(w)。
次数はクエリ毎に±1する。
隣接点次数 nd(v) は、次数の小さい頂点vの場合、クエリ時に愚直に計算する O(d(v))
次数の大きい頂点は工夫が必要。
- 頂点vの次数が600以上になったら vは「次数の大きい頂点」に昇格する。この時の nd(v) は愚直に計算する
- 辺(a, b)が追加されたとき、次数の大きい頂点 v について「a が v の隣接点ならば nd(v) += 1」（bについても同様）
- 辺(v, w)が追加されたとき、nd(v) += d(w)
600は適当に決めた sqrt(N) 程度の値。
クエリ先読みして最大次数が 600 以上になる頂点を最初から次数の大きい頂点として固定してもよかったかも。
次数が小さくなったら「次数の小さい頂点」に降格させるコードを書いたが必要なかったかも。
K
x zor y == x ⊕ P(y) と書くことにする。またP(P(x))をP2(x) P(P(P(x)))をP3(x)などと書く
まず0を生成できることを示す。
x_0 := x
x_1 := x ⊕ P(x_0) = x ⊕ P(x)
x_2 := x ⊕ P(x_1) = x ⊕ P(x) ⊕ P2(x)
x_k := x ⊕ P(x) ⊕ P2(x) ⊕ ... ⊕ Pk(x)
Pの周期がmの時、Pm(x) = x である。x_{2m-1} は x ⊕ P(x) ⊕ ... ⊕ Pm(x) ⊕ P(m+1)(x) ⊕ ... == 0
0が存在するのでP(k+1)(x) = 0 ⊕ Pk(x) と任意のPi(x)を生成することができる。
結局本題はバイナリ列の集合 A1, P(A1), P2(A1) ..., A2, P(A2), ... のxorから生成できる要素を数えればよい。これはバイナリ列が張る空間のサイズ == pow(2, バイナリ列を並べた行列のランク) である。
バイナリ列 Ai を追加しても空間が大きくならないときは「すでにAi が含まれている」=> 「すでに P(Ai) が含まれている」ので P(Ai), P2(Ai)... を追加する必要はない。空間が大きくなったときは P(Ai) も追加する、また大きくなったらP2(Ai)も追加、以下同様。
ランクの上限はビット数Kなのでそれだけしか空間は大きくならない
