自己紹介
大学三年生です.アルゴの方は結構やっていて,現在黄色です.ヒューリスティックは今回が初めてでした.焼きなましとかビームサーチとか何も知らない状態での参戦でした.
考えたこと/やったこと
ヒューリスティックで戦う方法を知らないので,とにかく貪欲にやりました.考えたこと/やったことを順番に書いていきます.
まず,1 色のコンピュータ 100 台をすべてつなげるとその時点で 4950 点がもらえてかなりお得だなと感じたので,それを達成する方法を考えました.とはいっても移動できる操作回数が限られており,特に遠くにある 2 つのコンピュータをの接続をどうするか非常に悩みました.しばらく考えて,以下のような方法にたどり着きました.
初期段階で,移動しなくてもすでにいくつかのクラスタが形成可能です.その中から 2 つのクラスタを選び,うまく接続して 1 つの大きなクラスタにします.その後も,できあがった大きなクラスタと別のクラスタを接続してさらに大きなクラスタを作る,ということを何回か繰り返すことである程度の大きさのクラスタが出来上がります.具体的な手順は以下の通りです.
これをある程度行った後,残ったコンピュータたちをどうにかして接続していきます.方法は完全に iwashi31 さんのやり方と完全一致でした.
クラスタ同士の繋げ方貼り忘れてた。だいたいこんな感じ #AHC013 #rcl_procon pic.twitter.com/QTk9BPkNRF
— iwashi31 (@iwashi31) 2022年8月16日
これ以外にも,周りに囲まれたコンピュータを救出する方法も行いました(実装がかなりしんどかった...).使ったアルゴリズムは BFS だけです.
他にも,できる限り移動回数を減らす工夫をしたり,残りの余った部分で別の色をつなげるということをしました(細かすぎるので割愛します).こんなことをしてたら pretest で 246000 点ほど得られました.
その時の seed=1 の結果です.
このとき,順位は 11 位でだいぶ調子が良かったみたいです.
246k いえええええええい pic.twitter.com/laTCx9Li8k
— とりゐ(競プロ) (@torii_kyopro) 2022年8月12日
しかし,上の画像を眺めると,1 のクラスタが分断されているせいでスコアが 4950 からあまり伸びていません.これらの分断されたクラスタをうまく連結できる方法を考えました.
いろいろ考えた結果,外周をあらかじめ別の色で囲っておいてからその内側ででかいクラスタを作ると,残りの部分でうまく連結させられるのではないかという方針にたどり着きました.
これをすることで,pretest での score は 300000 点を超えることができました!.
seed=1 の画像です.
残りの部分のクラスタが分断されるという問題点をかなり解消できているのが一目でわかると思います.
結果
ここから先は自分でも問題点が見つからず,アイディアも浮かばずで何もせずに終わってしまいました.pretest で 310000 点,システムテスト後の順位は 34 位でした.
良かった点・悪かった点
良かった点としては,ヒューリスティックで使える手法を何も知らないまま果敢に挑戦できたことだと思います.他の上位陣が焼きなまし法を使ってる中で自分は BFS という簡素なアルゴリズムだけでここまで順位を上げれたことは良かったのかなあという風に感じています.
また,実装量が多いことを嫌がらずに黙々とコードを書けたことです.ICPC の練習で培った実装力を生かせました.
悪かった点は,ちゃんとヒューリスティックのための勉強をしなかったことでしょう.さらに上位に行くためには,ヒューリスティック特有の手法を身につけないとだめなんだなと痛感しました(でもヒューリスティックの勉強をするやる気が起きない...どうしよう...).
それから,ここまでちゃんとやると思ってなかったので,最初の方のコードがかなりぐちゃぐちゃになって可読性が失われていたことです.デバッグするのが本当に大変で,かなり精神が疲弊しました.
今後
今回初めて参加した感想としては,楽しかったけど精神的・肉体的にかなり疲れるなあという感じでした(楽しさ<<<疲労 だったので長期コンには当分出ないかなあ...).短期コンは出てみようかなと思います.ヒューリスティックの勉強は気が向いたらしようと思います.