124位、パフォーマンスは1803でした。AHC、むずかしい…

問題

https://atcoder.jp/contests/ahc013/tasks/ahc013_a

やったこと

できるだけ大きい連結成分を作るとうれしいです。

また、問題文では移動を完了してから接続を行っていますが、接続に使ったブロックには移動できないとすると接続の後に移動を行っても大丈夫になります(上位陣は接続より先に移動を行うようにすることで飛び越せるようにしていたりして、すごい…になりました)。

移動の削除・接続の解除は大変そうで実装が嫌だなぁ、という気持ちになったのでランダムにPCを一つ選びそこから貪欲に広げていく…みたいなことをしました。

具体的には、次のようなことを実装しました。

1. PCの種類をランダムにえらぶ
2. 選んだ種類のPCをランダムに選び、そこからBFSして広げていく
   • ブロックからまっすぐ進み、同じ種類のPCがいたら接続する
   • ほかの種類のPCがいたら1マス外に避ける
   • 1マス隣に同じ種類のPCがいたら持ってくる
3. 違うPCを経由して接続でき、尚且つ得点が上がるならそれを採用する

これを時間まで回す…みたいなことをしました。

https://github.com/Kyo-s-s/AHC013

反省点

サンプルのUnionFindをパクりましたが、じつはこのUnionFindはmapをつかっているためだいぶ遅かったようです。コンテスト終了後にTLを眺めていたらそんなツイが流れてきて、かなしくなりました。

また、適当貪欲に走ってしまったこともよくなかったなと反省しています。上位陣は焼いたり工夫した貪欲をしたりしていたので、適当に書き始めるのではなくある程度考察を進めたうえで実装するべきでした。

感想

あまりよくない方針を進んでしまいましたが、それでも青パフォが取れたのは成長…だと信じます。

Heuristic黄の道は、とても険しいようです…