HACK TO THE FUTURE 2020 本戦 参加記録
オンサイト本戦に参加し、その1で8位、その2で10位のダブル入賞でした！
ネタになるエピソードとか写真とかは特にないので、マジメにコンテストについて書こうと思います。
本戦1
問題を理解し、正の得点を得る提出をするまで49分。ここまでのハードルが結構高かったと思います。
木 を作っても余計な辺が含まれているとほぼ無得点なので、初めは異なる木
間で頂点が被らないような作り方をしていました。ただしこれでは最大でも50個までしか木
を作れず、そんな中で満点が出てしまったので、昼食を食べた後に方針転換。
1000個の座標点で、20頂点の木 を1000個全て作る場合、必然的に頂点を共有することになります。そこでこれらの木を「重ねる」ような方針を取りました。なるべく多く辺が共有されるように木を重ねていき、その和集合になるような大きな木を作ることができれば、その中に全ての
を収容することができます。
具体的には以下のような実装です。木 と区別するため、和集合となる大きな木を「大域木」と呼ぶことにします。この大域木がそのまま出力するグラフ
になります。
- まず
個の座標点のペア全てについて「そのペアに辺を張れるか」を前計算し、各点について辺を張れる相手の個数を計算する。これを座標点の「強さ」と呼ぶことにする。
- 一番強い座標点
を大域木の根に固定し、全ての
の根をこの
- 各
- その途中でもし大域木の頂点
に子が足りなくなったら補充する。このときまだ大域木に使っておらず、
- 子が複数ある場合にどう対応させるかは、木
幅優先探索にしたのはなるべく浅い頂点を先に見たかったからです。強い頂点から順に使われていくので、深さ優先より幅優先のほうが浅い頂点が強くなると考えました。
子を次数でソートして割り当てたのは、子がたくさん必要な頂点を集中させるためです。大域木において先に追加した子（つまり強い子）ほど多くの次数が必要になるようにします。
これを提出して満点ゲット！この実装でexample_01を解くと大域木の辺数が258になりました。
Submission #8818174 - HACK TO THE FUTURE 2020 本選
実際、本戦1の設定ではパワーが強すぎて辺が非常に張りやすく、先ほどの「強さ」の平均がexample_01で約377、つまり自分以外の座標点のうち平均で1/3以上とは接続可能という状態でした。本戦2ではパワーの値が調整されたことで、この平均値はexample_01で約49になっています。
本戦2
まずは本戦1の解法をほぼそのまま出しました。木によって頂点数が異なるので、頂点数の少ない木から順番に作っていき、作れないものは諦めるようにしました。ここでの「作れない」とは、先ほどの手順中に子が足りなくなって、かつそこに接続できるような座標点も存在しないような場合です。
これを提出して2988400点。なかなか良い感じです。（とはいえ最上位層は既に400万点を出していたのですが…）
Submission #8819099 - HACK TO THE FUTURE 2020 本選 2
ここから実行時間を活用できる焼きなまし等にしたかったのですが、いまいち近傍の取り方が思いつきません。ということで1周目で作れなかった木について、割り当て方を変えて再チャレンジすることをひたすら繰り返す乱択を組みました。1周目では子を次数順にソートしていましたが、これを周回ごとに適当にスワップします。
とりあえずこれだけ実装して3364100点。
Submission #8819625 - HACK TO THE FUTURE 2020 本選 2
方針としてはここまででほぼ終わりで、時間を伸ばすとスコアが伸びることは分かっていたので高速化です。これで3616300点。
Submission #8821469 - HACK TO THE FUTURE 2020 本選 2
最後に有意な改善となったのは「反復回数がある程度までいったら、頂点数の多い木は切り捨てて他をいっぱい回すようにする」ことで、これで3659100点。最後の1時間では結局ここからスコアが伸びませんでした。
Submission #8822189 - HACK TO THE FUTURE 2020 本選 2
感想
本戦1で入賞枠が満点で埋まるという予想外の展開になりましたが…そこから即席で本戦2を準備したのは流石という感じです。これはこれで面白い体験でしたし、結果としてダブル入賞もできたので良かったです。
問題については過去問のうち「モンスターテイマー」ではオープンコンテストで良い成績を残せた一方、「ツカモの栽培」は全く何をしていいか分からない感じだったので、どう転ぶか…と思っていました。結果的には初見で絶望感があったものの、実装コスパの良い方針を掴むことができてかなり善戦できたと思います。
8時間コンテストということで交流できる時間は少ないかなと思っていましたが、お弁当を食べるテーブルや終了後の懇親会でけっこう話すことができたし、会いたかった人達にも会えたので大満足です。
これは順位表から分からない情報ですが、ご飯です #HTTF pic.twitter.com/DLBOQBIBSW
— アルメリア (@armeria_betrue) 2019年12月7日
また今回は18歳以下のユース枠が設けられていて、運営面でも非常に配慮が行き届いているように思いました。帰りにいただいたお菓子は、ご家族へのお土産にという気持ちもあったのかなと思ったり。（チョイスが完全におつまみ系…）
おしゃれ〜(柿の種専門店とは) #HTTF pic.twitter.com/8YvcwnQXTz
— アルメリア (@armeria_betrue) 2019年12月7日
ということでマラソンオンサイトは初めてだったんですが、とても楽しかったです。腕を上げてまた来れるよう頑張ります。運営スタッフの方々、ありがとうございました！
