m_solutions2019D
考えたこと
小さい数はなるべく位数の小さい頂点に置きたい
小さい数はなるべく小さい数のそばに置きたい
証明できればいい
木だから位数1の点が沢山ある
最小の数xを位数1の点に置くと、1本の辺がxになる
0本の辺をxにする方法は存在しない
だから位数1の点に置くのが最良
ソートして小さい順に置いていけばよい
公式解説
だいぶ違う話をしてるな
大きい方から固めて置いていくメソッド
大きい数の集まりが連結であることを保ちながら大きい方から置いていくので、小さい数を端から置いていく僕の方法と結果は同じだと思う
原理としては飛地をつくらない
僕の方は端から埋める
辺を全部チェックしてO(N^2)でも間に合うって書いてあるけど、深さ優先探索でO(N)でしょう
位数1の点から埋めていく僕の方法は深さ優先探索の帰り掛け順

Related