2019年5月31日金曜日

JAG 2013 Day 4 F - Graph Automata Player

JAG 2013 Day 4 F - Graph Automata Player

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

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

64倍高速化

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

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

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

2019年5月28日火曜日

ABC 128 F - Frog Jump

ABC 128 F - Frog Jump

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

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

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

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

0,N1(k1)C,C,N1(k2)C,2C,...,N1C,(k1)C,N10, N-1-(k-1)C, C, N-1-(k-2)C, 2C, ..., N-1-C, (k-1)C, N-1

であり、kkを1増やすと

0,N1kC,C,N1(k1)C,2C,...,N1C,kC,N10, N-1-kC, C, N-1-(k-1)C, 2C, ..., N-1-C, kC, N-1

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

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

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

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

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

2019年5月26日日曜日

ABC 127 F - Absolute Minima

ABC 127 F - Absolute Minima

更新クエリをkk回処理したあとの関数をfkf_kとすると、fkf_k

fk(x)=xa1+xa2+...+xak+Bf_k(x) = |x-a_1| + |x-a_2| + ... + |x-a_{k}| + B

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

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

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

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

xa1+xa2+...+xa2n=(ana1)+(ana2)+...+(anan)+(an+1an)+(an+2an)+...+(a2nan)=(a1+a2+...+an)+(an+1+an+2+...+a2n) \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+1k:=2n+1についてはx=an+1x=a_{n+1}のときに最小値を取り、

xa1+xa2+...+xa2n+1=(an+1a1)+(an+1a2)+...+(an+1an)+(an+2an+1)+(an+3an+1)+...+(a2n+1an+1)=(a1+a2+...+an)+(an+2+an+3+...+a2n+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}

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

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

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

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