まず、なぜF - Road ConstructionにDAG制約があったのかに気付くのかなりむずい。
で、一般の有向グラフ版がO(V(V+E) log V)で解けて驚き。
結構見たことない感じのアルゴリズムで面白かった。
ところで、TTPCの問題面白かった。
E,J,L,Nが特に好き。
まず、なぜF - Road ConstructionにDAG制約があったのかに気付くのかなりむずい。
で、一般の有向グラフ版がO(V(V+E) log V)で解けて驚き。
結構見たことない感じのアルゴリズムで面白かった。
ところで、TTPCの問題面白かった。
E,J,L,Nが特に好き。
BC2完で48位。
惜しかったような惜しくなかったような。
final行けなかったのは残念だけど、問題面白くて楽しかったので勝ち(とは)
opencupで二部マッチングを使う問題があって、自分のライブラリが遅くてTLEにハマりました。
そのときに得た知見をまとめておきます。
頂点は合計200,000個、辺は200,000本、TLは3秒で、writerや他の人は400msくらいで通ってたらしい。
雑な記事。
競プロテクをtweetしただけだといつか流れてどっか行くので、とりあえずまとめといた。
前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。
全方位木DPについて予習します。
全方位木DP、有向辺に関するDPだと思うのが分かりやすい。
— ꑄ꒖ꐇꌅꏂ🐾 (@snuke_) 2019年1月6日
1. 青い矢印は普通の木DPで下から順に求まる
2. 根から出る矢印は全部求まっているので、根に入る矢印も求められる(ここの計算量改善に総和とって引き算とか左右からの累積和とかが出てくる)
3. 同様に赤い矢印を上から順に求めていく pic.twitter.com/p4bl6rXzGn
補足として、以下の問題を解く具体的な実装も置いておきます。
N 頂点の木が与えられる。
頂点 v を含む部分木の個数を全ての v について求めよ。
制約:1 ≦ N ≦ 10^6
こういう、根を全部試して根付き木の問題を一括で計算する、的な状況で全方位木DPが活躍します。
pythonで実装するとこんな感じになります。
def dfs(v, p=-1): deg[v] = len(to[v]) res = 1 dp[v] = [0]*deg[v] for i in range(deg[v]): u = to[v][i] if u == p: pi[v] = i continue dp[v][i] = dfs(u, v) res *= dp[v][i]+1 res %= mod return res def bfs(v, res_p=0, p=-1): if p != -1: dp[v][pi[v]] = res_p dpl = [1]*(deg[v]+1) for i in range(deg[v]): dpl[i+1] = dpl[i]*(dp[v][i]+1)%mod dpr = [1]*(deg[v]+1) for i in range(deg[v]-1,-1,-1): dpr[i] = dpr[i+1]*(dp[v][i]+1)%mod ans[v] = dpr[0] for i in range(deg[v]): u = to[v][i] if u == p: continue bfs(u, dpl[i]*dpr[i+1]%mod, v) dfs(0) bfs(0)
本編と言いつつも、こちらは雑談みたいなものです。
全方位木DPには色んな流派があるみたいですね。
その中で、zerokugiさんの方法が計算量の視点から興味深かったので紹介します。
僕のオススメは上に書いた方法です。(定数倍、実装量、ロジックの簡潔さなどの点から)
あと、zerokugiさんの方法っぽくやる場合でも次数の降順より行きがけ順の方が定数倍が良いです。
全方位木DPをしたい時に
— zerokugi (@zerokugi) 2019年1月7日
・次数の降順で全ての頂点からdfsする
・各部分木についてメモ(普通の木DP)に加えて根だけ逆方向もメモ(累積積や逆元などを使って)する
というもので、一般にzerokugi法と呼ばれていません
さっきの問題をzerokugi法で実装すると以下のようになります。
def dfs(v, p=-1): res = 1 for i in range(deg[v]): u = to[v][i] if u == p: pi[v] = i continue if dp[v][i] is None: dp[v][i] = dfs(u, v) res *= dp[v][i]+1 res %= mod return res roots = [] for v in range(N): deg[v] = len(to[v]) dp[v] = [None]*deg[v] roots.append([deg[v], v]) roots.sort() roots.reverse() for _, v in roots: ans[v] = dfs(v) dpl = [1]*(deg[v]+1) for i in range(deg[v]): dpl[i+1] = dpl[i]*(dp[v][i]+1)%mod dpr = [1]*(deg[v]+1) for i in range(deg[v]-1,-1,-1): dpr[i] = dpr[i+1]*(dp[v][i]+1)%mod for i in range(deg[v]): u = to[v][i] dp[u][pi[v]] = dpl[i]*dpr[i+1]%mod print(ans)
実はこのアルゴリズムの計算量は O(N) なのです。
丁寧に書くと長くなるので、以下に示す本質部分だけを解析します。
for i in range(deg[v]):
dfs(v)を呼ぶ度にO(deg[v])がかかるという訳です。
根として呼ばれるのは各 v について1回ずつなので O(N) です。(Σ(deg[v]) =辺の本数*2)
問題はdfs内から呼ばれる場合です。
dfs(v)がdfs(u)内から呼ばれるのは、各辺 u-v について高々1回です。(結果がメモされるため)
で、実際に呼ばれる条件は以下の通りです。
別の言葉で言うと「v より先に根としてdfsを呼ばれる頂点が u 側の部分木内に存在する」です。
つまり、以下のことが言えれば計算量が O(N) であることが示せます。
頂点数 N のどんな木についても、Σ(「vを取り除いてできる部分木のうち、次数がdeg[v]以上の頂点が含まれるものの個数」* deg[v]) が O(N) である。
適当な頂点を根とした根付き木だとみなします。上記の式は以下のように言い換えられます。
Σ(「vの下に付く部分木のうち、次数がdeg[v]以上の頂点が含まれるものの個数」*「vの子の個数」)
実際には根方向の辺も考えないといけないので「vの下〜個数」には +1 が付くこともありますし、「vの子の個数」にも +1 は付きますが、Σ(deg[v]) が O(N) であることを思い出すと、この部分につく定数は無視できることが言えます。
さて、これの最大値の抑え方が分からなかったのでtwitterで助けを求めると、hosさんからエレガントな解答をいただいたので紹介します。(WA_TLEさんもありがとうございます)
頂点数 N 最大次数 K の根付き木についての最大値を f(N,K) とおくと、f(N,K) ≦ N-1-K。
これで、下に示すような帰納法が回るようになります。("次数"に親方向の辺は数えないものとします)
自分も帰納法が回せたら良いなぁとは思っていましたが、この式には辿り着けませんでした。すごい。
とりあえず、f(1,0) = 0
根の次数を d とすると、各 d に対して以下が成り立つ。
右辺のmaxの中身の f を外すと、
d = K の場合:そのまま N - 1 - K 以下だと言える。
d < K の場合: のいずれかは K なため であり、やはり N - 1 - K 以下だと言える。
min(k_i,d) の部分が少しテクニカルですが、k_i と d の大小で場合分けしてみると正しいことが確認できるかと思います。
次数の降順でやれば計算量が O(N) で抑えられるってかなり奇妙で面白い!
木は奥深いですね。
全方位木DPについて、普通のDPの場合はこれで良いのですが、データ構造で高速化するDPの場合などはまた別のアプローチをする必要があったりします。(前にHackerRankで使って以来、使う問題とは出会ってないけど。これの記事需要あります?)