hogecoder

tsutaj 競技プログラミングの記録

HACK TO THE FUTURE 2023 予選 (AHC016) 自分の解法

HACK TO THE FUTURE 2023 予選 (AtCoder Heuristic Contest 016) に参加しました。暫定の相対スコアが 14.1G で 154 位でした。他の参加者と解法が違いそうなのでまとめていきます。

解法の概要

画像一枚で説明するとこんな感じです。

グラフ生成

バーコードのように、デコードすると整数が得られるようなグラフを考えました。赤色で示したコード部にある頂点は、白か黒の 2 つの状態があるので 1bit 分の情報を格納できます。これを  \lceil \log_2 M \rceil bit 分用意すれば良いというわけです。

パターンは結構考えましたが、最終的にはグラフの次数をできるだけ unique にすることを意識して作りました。自己ループ・多重辺がない  N 頂点のグラフについて、 N-1 頂点までは次数を unique にできるので*1、そのようになるようにパターンを作りました。ノイズ対策のため、適当にバケットサイズ  B を定義して、 B 頂点で 1 頂点分の情報を表現するようにしました。

コード部は 1 行か 2 行です。表現したい整数の最大値が 100 なので最大で 7bit 必要になりますが、多く bit が必要なときは 2 行になったりします。2 行になる場合、上の行か下の行かの区別を付けるために情報を 1 bitずつ付加する必要があり、2bit 増えます。つまり 1 行で表現する bit 数は半分で済むものの 2 bit 余計に増えてしまうという感じです。

対角線をコード部として使うこともあります。バケットサイズが小さいときは対角線に情報を入れても消えやすいので使いませんでしたが、ある程度バケットサイズが大きくなってくると入れても問題ないので入れました。bit を奇数個用意したいとき、対角線で 1bit 表現できれば下段のコード部で必要な列数が 1 個減るので結構重要でした。

クエリ処理

画像にあるとおり焼きなましを 2 回行っています。グループ分けの焼きなましとグループ配置の焼きなましです。後で反省ポイントとしても挙げていますが、最適化を 2 回必要としている時点で上位の解法と差が付いてしまっている気がします。

感想戦を見た感想

反省ポイントを書いていきます。

  • 見かけ上の頂点数が少ないので、グラフ同型性判定が普通にできた
    • これは全く気づいていなかった・・・これに気づいてれば 6 頂点で足りるので見かけ上の頂点数を大幅に削減できましたね。同型性判定の解法はグループ分けだけちゃんとできれば良くて、グループ分けした後に並び替えとかもしなくて良いので、かなり強そうです (同型性判定が高速に出来る必要はありますが)。
  • 見かけ上の頂点は自己ループありなので、パターンに使う頂点は次数を全部 unique にできた
    • コンテスト後に気づきました。ただし自己ループを使って全頂点の次数を unique にしてしまうと対角線上に bit 情報を置けなくなるはずで、修正したとしても微妙かもしれません。
  • 1 回の山登りや焼きなましを時間いっぱいまで回すのではなく、何回か回して最も良いものを取ることも考えるべきだった
    • これもやるべきでした。自分の解法も時間いっぱい回しても結果が結構ぶれてたので、何回か回すべきだったかな・・・
  • パラメータ別に得点の傾向を見るべきだった
    • M が小さいときに露骨に成績が悪いので何か手を打つべきでした。去年の HTTF はパラメータごとに見る時間があったんですが、今回は手いっぱいだったので次回は余裕を持ちたいですね。

*1:自己ループ・多重辺がない場合、 N 頂点すべての次数を unique にすることはできません。次数  N-1 と次数  0 の頂点のことを考えつつ背理法を使うと簡単に示せます