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