JAG 2013 Day 4 F - Graph Automata Player

• 問題
• AC

${\mathbb F}_2$上の行列積と掃き出し法を実装して通した。

掃き出し法の計算量をちゃんと考えたことがなかったけど、行列$A \in {\mathbb R}^{m \times n}$について${\mathcal O}(mn\operatorname{rank}A) \subseteq {\mathcal O}(mn \min(m, n))$ってことでいいんだろうか。

64倍高速化

64倍高速化した掃き出し法を$4096 \times 4096$の正則行列に適用すると800msくらいで、行列積は同サイズで2200msくらいだった。この辺を限界として覚えておく。SSE使うともう少しいけるのかな。

「ワード長w>=lg(データサイズn)」という仮定、なるほどなあという感じ
この立場だと例えばstd::bitsetを用いたbit並列化は1/64の定数倍高速化ではなく1/(lg n)のオーダー改善ということになる

— 自朗 (@risujiroh) April 17, 2019

いわゆるbitset高速化が$\log^{-1} n$の改善という見解を見つけて、なるほどとなった。→ というかword-RAMモデルだとそうなるのか。

参考:
http://drken1215.hatenablog.com/entry/2019/03/20/202800

ABC 128 F - Frog Jump

• 問題
• AC

$A, B \in {\mathbb N}$が与えられたときの経路は（$N-1$にたどりつくなら）

$0, A, A-B, 2A-B, ..., kA-(k-1)B \: (=N-1)$

のようになっている。$C:=A-B$とすると$B+kC=N-1$が成り立つので、逆に$k, C$が与えられると$B = N-1-kC$, $A= N-1-(k-1)C$となって経路が決まることになる。$f(k, C)$をこの経路の最終得点とする。$A, B > 0 \Leftrightarrow kC < N-1$だから、$kC < N-1$を満たすような${\mathcal O}(N\log N)$通りの$k, C$について$f(k, C)$を求めればよい。

$f$の漸化式について考える。$k, C$が与えられたときの経路は

$0, N-1-(k-1)C, C, N-1-(k-2)C, 2C, ..., N-1-C, (k-1)C, N-1$

であり、$k$を1増やすと

$0, N-1-kC, C, N-1-(k-1)C, 2C, ..., N-1-C, kC, N-1$

となる。差分を見ると$f$の漸化式は

$f(k+1, C) = f(k, C) + S_{N-1-kC}+S_{kC}$

と書けるので、これに従ってDPすればよい。

ただし、同じ位置を2回通ってしまうパターンを除く必要がある。上の経路を観察すると、同じ位置を2回通るのは$x, y \in \{1, ..., k-1\}$が存在して$N-1-xC = yC$となる場合であり、これは$z \in \{2, 3, ..., 2(k-1)\}$が存在して$N-1 = zC$が成り立つのと同値である。つまり、$C$が$N-1$を割り切り、かつ $2 \le (N-1)/C \le 2(k-1)$である場合を除けばよい。

超えるべきハードルがいくつかあるので、コンテスト中に解けるようになるのは大変そう。

ABC 127 F - Absolute Minima

• 問題
• AC

更新クエリを$k$回処理したあとの関数を$f_k$とすると、$f_k$は

$f_k(x) = |x-a_1| + |x-a_2| + ... + |x-a_{k}| + B$

という形に書ける。$B$はクエリの定数項$b$の総和である。

以下、$(a_i)$はソート済み($a_1 \le a_2 \le ... \le a_{k}$)として考える。$x$が$a_1, a_2, ..., a_{k}$で区切られた数直線を右に進んでいくとき、$f_k(x)$の最初の傾きは$-k$であり、$a_i$を通過するたびに2ずつ増えていくので、中央値のあたりで最小値を取ることがわかる。

（ただし、この辺の理解はコンテスト後に整理したもので、コンテスト中はDesmosでグラフを描いて、真ん中あたりで最小になるというイメージを得てすぐに先に進んだ。競プロ的には常識の性質らしい。）

具体的には、偶数$k:=2n$については$x \in [a_{n}, a_{n+1}]$のときに最小値を取り、代表値として$x=a_{n}$を選ぶと

$\begin{aligned} & |x-a_1| + |x-a_2| + ... + |x-a_{2n}| \\ = & (a_{n}-a_1)+(a_{n}-a_2)+ ... + (a_{n}-a_{n}) + \\ & (a_{n+1}-a_{n})+(a_{n+2}-a_{n})+ ... +(a_{2n}-a_{n}) \\ = & -(a_1+a_2+ ... +a_{n})+(a_{n+1}+a_{n+2}+ ... +a_{2n}) \end{aligned}$

となる。奇数$k:=2n+1$については$x=a_{n+1}$のときに最小値を取り、

$\begin{aligned} & |x-a_1| + |x-a_2| + ... + |x-a_{2n+1}| \\ = & (a_{n+1}-a_1)+(a_{n+1}-a_2)+ ... + (a_{n+1}-a_{n}) + \\ & (a_{n+2}-a_{n+1})+(a_{n+3}-a_{n+1})+ ... +(a_{2n+1}-a_{n+1}) \\ = & -(a_1+a_2+ ... +a_{n})+(a_{n+2}+a_{n+3}+ ... +a_{2n+1}) \end{aligned}$

これに上の定数$B$を足せば求値クエリへの答えになる。

実装について。更新クエリ$(a, b)$を処理するにはソートされた列に（順序を保って）挿入する操作が必要になり、また求値クエリではその列の区間の和を計算しなければならない。平衡二分木ならどちらも${\mathcal O}(\log Q)$でできる。

コンテスト中にはImplicit Treapを使ったのだが、二分探索を用意するのを忘れていたのでその場で実装することになった。準備不足とも言えるけど、コンテスト中にデータ構造を多少いじること自体は避けられないと感じているので、構造に習熟しつつテスト環境を充実させる方向のほうが筋がよい気がする。

ただ、この用途で平衡二分木はややリッチすぎる気もした。真ん中で分割した2つの列にしか興味がないので、優先度付きキューを２つ使うくらいでもできるらしい。オーダーは変わらないけど……