AHC037に参加()しました！
- 遅刻したのでバーチャル参加
結果(本参加していたらの順位)
- 173rd / 922
考察
-
それぞれの点を独立して原点からつなげるのは効率が悪い
- コストを考えると全体的に二分木を構築すると効率がよさそう
-
それぞれの点と近い点を辺の先とする頂点を決める必要がある
- x,y軸において小さい座標をそれぞれ組み合わせた点を頂点とする
- これを繰り返すといい感じに繋げられそう
-
つなげ方は現在存在している頂点に一番近い頂点を選ぶ
-
一部無駄なつなげ方をする挙動が見られたので対策として軸付近に頂点を存在させておく
-
感想
- 結構面白かったけれど、もう少し詰めれる知識がなかったのが悔やまれる
- ヒューリスティックに参加はしているけれど、ちょくちょく参加を逃す時に限って相性の良い問題が出てきたりしてて悲しい