/ 最近 .rdf 追記 編集 設定 本棚

脳log[20210617] 競プロ典型 90 問/035 - Preserve Connectivity(★7)



2021年06月17日 (木)

最終更新: 2021-06-17T19:54+0900

[AtCoder]競プロ典型 90 問035 - Preserve Connectivity(★7)

解説はこちら>解説1解説2解説3

 LCA とダブリング

実装したことはないけどダブリング(要は繰り返し二乗法でしょ?)で効率的に親を辿る?」と書いたのがつい先月のことだけど、とうとうダブリングを実装する機会が訪れた。

この問題がどうして、選ばれた複数の頂点を決まった順番で環状に並べて隣接する頂点ペアの LCA が辺の本数になって割る2が答え、になるのかは解説3を読む。今は LCA にだけ注目する。

LCA の取り扱いは「巨大企業」や「筆塗り」で経験があるけど、線形より効率的な LCA の検索が案外面倒くさい。「最小共通祖先 [いかたこのたこつぼ]」にいくつか手法がリストアップされているけど、自分が知っている手段はセグメント木だけであり、セグメント木は書くのが面倒くさい。

そこでダブリングです。

 提出 #23482710 (TLE×26 / 810 Byte / 2207 ms / 42608 KB) ※まだコンテスト期間中であり見られないはず。

間違えた(TLE)。

A = [ps=P.dup]
(D.max-1).bit_length.times{ # 1世代上はすでに P としてあるので、1回分繰り返しが無駄かも。
	A << ps = N1.times.map{|a| ps[ps[a]] }
}

Ans = lambda{|a,dd|
	i = 0
	while 0<dd
		a = A[i][a] if 0<dd&1
		dd >>= 1
		i += 1
	end
	next a
}

A 配列に事前に親、親の親(2世代上)、4世代上、8世代上、とメモしておいて、Ans 関数(Ancestors の略ったら略)で「a の dd 世代上は?」という質問に対数時間で答えられるようにした。Ans 関数がこのようなインタフェースになっているのは、LCA を経由した2頂点間の辺の数を求めたい呼び出しもとで「同じ深さにある2頂点 a,b が初めて祖先を共有する深さは?」という問いを立てて、二分探索でその深さを確定させようとしたから。次のように。

Dst = lambda{|(a,b)|
	da,db = D[a],D[b]
	dc = (1..[da,db].min).bsearch{|dc|
		Ans[a,da-dc] != Ans[b,db-dc]
	}
	next dc ? da-dc+db-dc+2 : (da-db).abs
}

競プロにおいては対数は定数と言われるけれど、かなり大きな定数ではあり、必要がないところで log をくっつけると TLE に苦しめられたりする>「Pairs」。同じ日記に書いてあるけど、「射撃王」や「Handshake」のように余分な log があっても TLE にならないこともある。

 提出 #23482781 (AC / 873 Byte / 1082 ms / 42672 KB) ※まだコンテスト期間中であり見られないはず。

A 配列は正しくはこう使う。共有されている yuruhiya さんの解答 を見ても LCA#lca メソッドが同じ感じだったので、大嘘はついてないと思う。(Dst は Distance の略。D は Depth の略)

Dst = lambda{|(a,b)|
	da,db = D[a],D[b]
	a = Ans[a,da-db] if db<da
	b = Ans[b,db-da] if da<db
	A.reverse_each{|ans|
		a,b = ans[a],ans[b] if ans[a]!=ans[b]
	} if a!=b
	next a==b ? (da-db).abs : da+db-2*D[P[a]]
}

実は解説2にはこれを説明する具体的手順が書いてある(あとで詳しく読んだ)。だけどありとあらゆる落とし穴にはまりたがる自分にとって、「こうすればいいんですよ」とか「こうしてはいけませんよ」いうアドバイスは役に立たないんですな。「要は繰り返し二乗法でしょ」というだけの理解で実装してみて、「あれは良かったここはダメだった」と納得するまでは身にならない。仮にアドバイスのおかげで最初からうまくやれたとしても、それは今回だけのことであり、将来必ず自分の性向に導かれて穴にはまる。早いうちに地図を作っておくべきだ。そうすれば多少は、ね。