はじめに
ALGO ARTIS プログラミングコンテスト2023(AtCoder Heuristic Contetst 020)に参加しました
黄パフォが取れました！うれしい！
実装方針
ということでどんなコードを書いていったかを書いていく
1. 退路を断つ
26分経過 / 317,153,274点
まずは全ての放送局から適当に3000出して、ケーブルはすべて使う。
2. ケーブルの最適化
37分経過 / 329,081,596点
Visualizerを見て無駄な辺があることを確認したので、クラスカル法を使って最小全域木を作成して、それに含まれるケーブルのみ使う。
電力は3000でそのまま。
ここでそこまで得点上がらなかったので「あまりケーブルは関係なさそう？」とみて考察を進め始める。
3. 家から一番近い放送局に電力を要求
46分経過 / 411,520,772点
それぞれの家について、その家から一番近い放送局を探して、その放送局からその家まで届くように電波を送ってもらうようにした。
これだけでかなり上がる
4. 探索の絞り込み
59分経過 / 422,698,806点
探索の段階ですでにどこかの放送局に含まれている場合、3.での探索をして電力を要求する必要がないのでその場合に探索をしない。
もし探索してしまった場合、不必要な電力を全く別の(自分が含まれている放送局ではない)放送局に要求することになる。
5. 無駄な辺を消す
1時間11分経過 / 429,605,046点
ここまでで電力の探索をすると最終的に使われない放送局が出てくるので、そのような放送局にのみつながるケーブルを使わないようにする。
ちょっと上がった。
これによってさらにケーブルのオンオフがあまり重要ではないと信じ込むようになる。
(実は高得点を取るにはものすごく大事な要素だった)
6. 探索の反復、山登り
1時間18分経過 / 436,253,280点
こうしてみると、電力の探索が家の順番に大きく依存しそうだとわかったので、ランダムに家の順番を並べ替えて探索、一番良い結果を採用するように。ちなみに200回程度しか回らなかった。
(焼きなましで1万とか回してるのは何なのだろう???)
さらに改善。やっぱり電力
7. 追加コストで探索
1時間29分経過 / 477,593,042点
それまでは「各家から最も近い放送局」を選んでいたのを、「各家につながるための追加コストが最も低い放送局」を選ぶようにした。
これがかなりうまくいって、暫定順位が3位で上がる。めっちゃうれしい
8.~ それ以降
今までヒューリスティックでそんなに良いパフォーマンスが出せなかったのが、一瞬とはいえ3位まで上がることができ、満足してしまったために思考を放棄。
探索回数を上げるため高速化に走り出す。
...が、どの提出も.7を超えられなかった....
12. 最終提出
2時間59分経過 / 478,416,271点
残り1分でもうしょうがないので上振れを願って7.のコードを提出。
見事に上振れて最高点を更新！
最終結果
最終的に、
順位: 78位
パフォーマンス: 2122
レーティング: 1147→1431
とかなりいい成績を残せた。
最後思考放棄してケーブルを焼きなまそうと見直さなかったのが痛い...
とはいえ、(過去最高のパフォをとれたという理由が大きいですが)僕にとって一番楽しいAHCでした。
TERRYさん、及び主催のALGO ARTIS社の皆様、ありがとうございました。