HackerRank May World CodeSprint: Travel in HackerLand
https://www.hackerrank.com/contests/may-world-codesprint/challenges/davaro-and-travelling
以前書いた永続union-findが使いづらかったので永続配列で書きなおした。
問題
n 頂点 m 辺のグラフが与えられる。各頂点には T[i] という値が割り振られている。各辺には u[i] という値が割り振られている。
このとき、以下のクエリを Q 個処理せよ。
- 頂点 x と頂点 y を連結にし、かつ頂点 x の連結成分に属する distinct な T[i] の数が k 個以上になるように辺を選んでグラフを作る。このとき必要な辺のラベルの最小値を求める。
解法
永続union-find + 永続set。
- uf[i] := i以下の辺を用いて構成したグラフのunion-find。
が i=0..N-1 で得られていれば、どのタイミングで連結 & distinct数がk以上になるのかを二分探索できる。
union-find を永続化するのに永続配列を作った。
永続配列を完全二分木で表現すると、アクセスに O(log n) 掛かる。これだと root, merge 操作に O(log2 n) 掛かってしまい間に合わない。
二分探索内で merge は呼び出されないため、rootを O(log n) ぐらいに落としたい。そこで永続配列を完全16分木に変える。こうすることで木の高さが O(loglogN) になり、rootがO(logN loglogN) になる。
RBST の insert の正しいやり方が分からなかったので適当に書いたけど、速いから大丈夫なのかな…?
(追記 2016/06/21)
ソート済みの列を insert したら木の高さが 500 ぐらいになってしまったので少し修正した。今度は高さ 40 ぐらいなので大丈夫かな。
永続n分木はバージョン管理しやすくて良い。