アルゴ式: 943 木の 2 頂点間の距離 (Swift)
Published
•1 min read木の 2 頂点間の距離
- 昨晩に問題を見て布団で考えていたものを今朝実装
- いろいろ考えられども、考え始めると実装したくなるし、睡眠にはよくないかも？
- 整理していて、避けようとしていたことは、忘れて普通に同じ考えを辿って思い出した気がする
- 今回は寝る前に考える方法はうまくいかなかったかな
- また、試してもよいとは思う
- 昨日に引き続きSetを使って実装
- ユニークなノード数が、接続に必要な枝の数と同じになるということを利用
- insertの返り値を使った方法でも実装したけれども、Setのドキュメントをみて、
[symmetricDifference(_:)](symmetricDifference(_:))も見つけたので、それを利用した実装もしてみた - 加えて1巡目で距離を記録して、2巡目で1巡目で記録した距離に見つかったら解答する方法も実装してみた
- こっちの方が考え方としては素直なんだろうけど、実装としてはちょっと複雑になるかなぁ
- 競技プログラミングという文脈では実行速度も大事だけど、結局は計算複雑性さえ外さなければ影響は少ない
- 簡潔なコードでの読みやすさもミスを減らせて大事だよな、と改めて考えさせられる