m_solutions2019D

https://gyazo.com/f834dc866fa9261fabb4587700813ecb

考えたこと

小さい数はなるべく位数の小さい頂点に置きたい

小さい数はなるべく小さい数のそばに置きたい

証明できればいい

木だから位数1の点が沢山ある

最小の数xを位数1の点に置くと、1本の辺がxになる

0本の辺をxにする方法は存在しない

だから位数1の点に置くのが最良

ソートして小さい順に置いていけばよい

公式解説

だいぶ違う話をしてるな

大きい方から固めて置いていくメソッド

大きい数の集まりが連結であることを保ちながら大きい方から置いていくので、小さい数を端から置いていく僕の方法と結果は同じだと思う

辺を全部チェックしてO(N^2)でも間に合うって書いてあるけど、深さ優先探索でO(N)でしょう

位数1の点から埋めていく僕の方法は深さ優先探索の帰り掛け順