Part 1 で 14 位、Part 2 で 9 位でした。
問題
最初は 1 問のみだったのですが、かなり早い段階で満点が出たので急遽制約を厳しくした 2 問目が追加されました。
基本方針
概要
- 与えられた点で根付き木を作る。
- $S$ 個の根付き木が作った根付き木と対応付けられるか調べる。
- 作った根付き木の根を別のノードに変えたり、$S$ 個の根付き木のいずれとも対応させられなかったノードを別の親に繋ぎ変えたりして時間いっぱい 2. を回す。
ゆるふわ解法なのでこの方針で詰めても満点は出せないような気はしています。
1. 与えられた点で根付き木を作る
中央あたりにあるパワーの大きいノードを選んで根とし、適当に全点を連結させた根付き木を作ります。
各深さのノード数はこんな感じ。
depth 0 : 1 depth 1 : 10 depth 2 : 106 depth 3 : 190 depth 4 : 195 depth 5 : 165 depth 6 : 118 depth 7 : 61 depth 8 : 38 depth 9 : 13 depth 10 : 6 depth 11 : 2 depth 12 : 1
2. $S$ 個の根付き木が作った根付き木と対応させられるか調べる
便宜上、与えられた点で作った根付き木を $T_A$、$S$ 個の方の根付き木を $T_B$ と呼びます。
$T_A$ のとあるノードと $T_B$ のとあるノードを対応付け可能どうかは、下記のような手順で再帰で書けます。
- $T_B$ に子供がいないなら、対応付け可能。
- $T_B$ に子供がいるなら、$T_B$ の子供すべてに対し $T_A$ のいずれかの子供で対応付け可能である場合、対応付け可能。
// nodeId: T_A 上のノード番号(1~N) // treeId: T_B のツリー番号(1~S) // treeNodeId: T_B 上のノード番号(1~K) map<int, int> canAssign(int nodeId, int treeId, int treeNodeId) { map<int, int> m; // m[T_B 上のノード番号] = T_A のノード番号 という対応表 set<int> used; for (int treeChild : trees[treeId].points[treeNodeId].children) { bool assigned = false; for (int child : points[nodeId].children) { if (used.find(child) != used.end()) continue; auto m2 = canAssign(child, treeId, treeChild); if (!m2.empty()) { for (auto &pr : m2) m.insert(pr); used.insert(child); assigned = true; break; } } // T_B[treeNodeId] の子供に対応するノードが T_A[nodeId] の子供にいなければアウト if (!assigned) return map<int, int>(); } m[treeNodeId] = nodeId; return m; }
$T_A$, $T_B$ の根っこをこの関数に渡して、対応付け可能であればめでたしめでたしです。
対応付けできなかった $T_B$ については、次のステップの処理を行った後再チャレンジします。
3.1 作った根付き木の根を別のノードに変えたり
$T_A$, $T_B$ の対応判定はそれぞれの根から比べていくロジックを書いちゃったので、$T_A$ の根を動かせばそれまで見つからなかった対応が見つかることもあります。
根付き木の根を変えるの面倒くさそうな印象だったのですが、よく考えたら根をひとつ隣のノードに移し替えるだけならば辺の向きを 1 本変えるだけで済みました。
根はグラフの中心付近にある方が良い気がした（未検証）ので、最初の根っこ付近でうにうに入れ替えをしつつ時間いっぱい回します。
3.2 $S$ 個の根付き木のいずれとも対応させられなかったノードを別の親に繋ぎ変えたり
いずれの $T_B$ のノードとも対応しなかった $T_A$ のノードはもはや不要なので、適当な他のノードに接ぎ変えて次の世代では何かしらと対応してくれることを祈ります。
おわり
楽しかった上にたくさんのおみやげもいただいてしまいました。
来年もよろしくお願いします！
