人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

AtCoder Regular Contest 102:D - All Your Paths are Different Lengths

問題

beta.atcoder.jp

解法

0 ~ L - 1 の長さのパスを作りたいのだから,とりあえず長さ 2^0, 2^1, 2^2, ... , 2^20 の辺を張っておきたいと考える(2^20 までなのは,2^20 > 10^6 であるから)(log2(10^6) が大体 20 なので制約から察することも出来そう).

ある頂点 v から頂点 N に辺を張ると,新しくパスが 2^(v - 1) 本出来る.ここで,L - (2^(N - 1)) = T と置く.追加で長さが L - T ~ L の T 本だけ新しくパスを作ればよい.頂点 v を N - 1 ~ 1 の順に見ていき,2^(v - 1) <= T であれば,頂点 v から頂点 N に長さ L - 2^(v - 1) の辺を追加する.この長さを S と置くと,これによって,長さ S, S + 1, S + 2, ... , S + 2^(v - 1) - 1 のパスが増えたことになる.解説をかなり見た.

合計で計算量は O(logL) になる(と思う).

解答

beta.atcoder.jp

嘘解法で 2 WA した.

f:id:babcs2035:20181019225228p:plain