読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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分木はバージョン管理しやすくて良い。