AHC020 に参加しました

もう終了から約一週間が経っているけど、忘れないように自分が競技中にやったことだけでもまとめておく。（コンテスト後の提出に関してはまた今度個々のページに更新する予定）

あと文字だけだと殺風景だし、 seed=0とかの画像も添えておこうかな。

結果

コンテスト中の最高点は $447485604$ 点。

記録

15:00

問題文を読む。パッと見た感じ

• 通信ケーブル（以下、「ケーブル」）は最小全域木
• 出力強度は山登りでうまく求められそう

というのが浮かんだ。とりあえず初期解として

1. 貪欲に出力強度を高めていき、全員にいきわたらせる
2. 使った頂点を全部結ぶように最小全域木の要領でケーブルをつなぐ

というものを作成した。

16:02

初提出。 $411520772$ 点。

16:26

$(0, 0)$ をつながなければいけないことに気づく。修正して提出。 $415261195$ 点。

16:27

山登りの近傍を考え始める。

• ランダムに人を選び、担当する放送局をスワップする

$1$ 回あたり $O(K)$

というものを書いた。

17:02

上を提出。 $428325691$ 点。

17:11

「山を登り切れていない」という根拠はなかったのだが、スワップする際に元の出力強度を超えるような放送局を候補としないようにした。 $434346707$ 点。

18:02

出力 $0$ でかつ葉となっている放送局を見つけた。とりあえずそれを除くプログラムをいれた（バグあり）。 $438877587$ 点。

18:42

ラスサブ。人を選んでスワップする際に、多少スコアが減るのを許した（焼きなましチック）。 $447485604$ 点。

その他時系列不明なもの

人を変更する際に、前計算をしておくことで計算量が減りそうだなと思ったが、実装が間に合わなさそう（というかそれよりもより良い解法があるのではないかと考えていた）。

感想

短期AHCはやることがいっぱいで大変。テスターを用意していたおかげで、コードのバグや改善点に気づくことができて良かった。

ただ、本番中は思い切ってケーブルに関する考察を捨ててしまったので、もう少しそれらを含むような解法を考えるべきだったのかもしれない（山登りのスコアに、ケーブルの重みも含めるとか）

今月はもう $1$ つ短期AHCがあるから、それに向けて準備と調整を怠らないようにしたい。

After-Contest

コンテスト後の最高点は $447490835$ 点。

葉を取り除くパートのバグ修正

なぜか $1$ 段階しか葉を取ってなかったようで、これをちょっとだけ手直しした。 $447490835$ 点。