脳log[20200709] AtCoder Beginner Contest 173／F 問題 Intervals on Tree

最終更新: 2020-08-15T20:50+0900

♪ [AtCoder] AtCoder Beginner Contest 173／F 問題 Intervals on Tree

コンテスト中に解けなかった(問題文を読むところまでいかなかった)問題に挑戦。

「連結成分」っていうのがわかんないよね、まず。出力例１の解説を読むに、頂点集合が辺で繋がれたいくつの部分に分かれるかを数えるみたい。

 考えたこと

1. 頂点集合は考え得るすべての通し番号から作られる(１～２、１～３、２～７など)。頂点番号と木の構造に関連はない。
2. 頂点集合ごとに Union-Find するのはどう考えても間に合わない。
3. LCA が高速に求められたらいけるだろうか。頂点集合に含まれる任意の２頂点をすべて試していたらどう考えても間に合わない。
4. トポロジカルソートして割り振った番号と実際の頂点番号を見比べて何かわかるだろうか。わかんない。
5. 木を構成する頂点を「決まったやり方で並べていったら(20200607p01.02)」連結成分が配列の連続する部分として見出せるだろうか。そんなにうまくない。
6. 木ってどこが根とか決まってたっけ？ どのノードでも根になれる？ 葉でも根になる？ なる。
7. 一番考えやすいのは、葉が単独で連結成分を構成するとき。葉Cと親Pのあいだに辺があるような(=CとPが共に頂点集合に含まれるような) L,R の選び方が L<=[C,P].min && [C,P].max<=R だから、その否定。(追記：これは嘘。実装中に気がついたがこれだと頂点 C が頂点集合に含まれないケースが紛れている)
8. 大元の根(※勝手に１つ決めます)に一番近いノードに連結成分を代表させることにすると、あるノードCを根とする連結成分がカウントされるかどうかはノードCと親とのあいだに辺があるかどうかでわかる。
9. すべての連結成分(=任意のノードを根とする連結成分)について、それがカウントされるような L,R の選び方を数えよう。

 提出 #15106396 (AC / 307 Byte / 351 ms / 35716 KB)

スクリプト化にあたって一番考えたのって、重複組合せの求め方だった。最初 N×N にして間違っていて、仕切りを置く場所を考えるんだったような、と思い出すのに時間がかかった。そして最終的に補集合ではなく目的のものを直接数えられることがわかって無駄になった。

あと、ちょこざいなやり方だとは思うけど、C と P の大小で場合分けをしたくないなと思って符号を利用した>[(c+1)*(p-c),(p-c)*(c-N),].max。あ、カンマが余分。これは「２頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」が最後まで見抜けなかった恨みである。

こうしたら最後の計算で根(c==0)の場合を例外扱いしないで済む。

P[0] = N # 0 を根にする。N は計算のため。

p (0...N).sum{|c|
	p = P[c]
	[(c+1)*(p-c),(p-c)*(c-N)].max
}

 「Ruby(2.7)によるすべての提出」

ワンライナーとかわけがわかりません＞＜

あ、これ？ 「閉路が存在しないならば「連結成分の個数 = 頂点数 - 辺の数」が成り立つ。」 木のどの部分を切り取っても木だろうし、木なら頂点数と辺の数は N 対 N-1 に決まってるので、頂点数と辺の数のずれの大きさがそのまま森を構成する木(連結成分)の数というのは、まあ、言われたらそうかもね、という感じ。

言われなきゃわからないし、なんなら、連結なグラフで頂点数と辺の数の比が N 対 N-1 ならそれは木だというのも、最初からなんだか化かされてるような気がしてる。