HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016）

HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016） - AtCoder に参加しました。暫定49位でした。

解法

1. εが小さいときは前計算して埋め込んだグラフを使って、編集距離の最も近いものを答えとして出力する
2. εが大きくてMが小さいときは、辺の数が違うグラフをいくつか作ってそこから推定する
3. εと M が両方大きいときは諦める
4. それ以外のときはあらかじめ 5 頂点のグラフ（自己ループあり）を 100 個用意しておき、それぞれの頂点をいくつかの頂点の集合に置き換えたものを G として出力する。自己ループを持つ頂点に対応する集合はクリークにする。推定パートは隣接点の集合が似ているものをまとめるクラスタリングをして、小さいときと同様に編集距離で元の 5 頂点のグラフを推定する。

グラフの構築方法はおおよそ解説配信と同じに見えるし、推定パートもよく似ているので、たぶんクラスタリングと推定の精度が悪い。単純に距離が近いものを答えるだけでは精度が出ないケースがあり、ベイズの定理で推定した方がよかったようです。言われてみれば。

ということで解法のメインの部分は解説してもあまり意味がない感じなので、楽しかった部分のことを書きます。

埋め込むグラフの作り方

注意: 上に書いたように、これは元々の問題の解法として特によいものではないようです。

ε=0 の場合を最初に書いたらεが 0 でなくても小さいときはこれでできるんじゃないかという気がして、そっちにかなりの時間を費やしました。誤り訂正みたいなことができればよいので 100 個のグラフをどの二つも編集距離がある程度大きいように作ればよい、ということでそういう集合の構築をずっとやってました。

編集距離

編集距離（単に距離と書きます）の定義は、辺の有無を何回入れ替えると同型になるかです。より正確には頂点数が等しいグラフ G, H の距離は以下のように定義されます。（ここではこう定義しましたが一般的な定義かどうかは知りません）

• を全単射とするとき、そのコストを とします。要するに f で写したときに辺の有無が違ってる箇所の数です。
• G と H の距離はすべての全単射 についてのコストを考えたときの最小値です。

これは f を DFS で構築しながら、既に構築した部分のコストがいくつになるかを覚えておくと ぐらいで計算できます（行き先を一つ決めるごとにコストの増加量を計算するのに O(N) かかります）。途中で f が最後まで構築できたときに距離の上界が求まるので、それ以降はその上界を使った枝刈りをします。また、ある閾値 d があって距離が d 以上のときは求めなくてもいい場合は、DFS の途中で f のコストが d 以上になったら打ち切る、とすると同様に枝刈りできます。これを d = 1 としてやるとグラフの同型判定になります。

どの二つも距離が d 以上になる N 頂点グラフの集合を探したら見つかった集合のサイズは以下のようになりました。行が N で列が d です。やってないところは ? になってます。4 をあんまりやってないのは奇数の方がうれしい気がして最初は 2, 3, 5 しかやらなかったためです。

        距離1   距離2   距離3   距離4   距離5
4       11      6       3       ?       ?
5       34      18      8       ?       ?
6       156     78      32      ?       10
7       1044    522     93      ?       19
8       12346   ?       >=100   247     66

距離 2 以上のは以下の手順で求めました。

1. 同型でないグラフを全部列挙する
2. グラフ間の全ペアの距離を求める
3. 列挙したグラフを頂点とし、距離 d 未満のグラフ間に辺を張ったグラフを作り、最大独立集合を求める

最大独立集合は昔書いた近似アルゴリズムを使ったので厳密解かどうかはよくわかりません。

1.は隣接行列の左上から順番に辺を張るか張らないかで分岐する DFS です。どうせ同型なものは一回しか見なくてよいので頂点番号は次数でソートされていると仮定してよく、隣接行列の各行の 1 の個数が降順になるものだけ列挙したらそれなりに速くなりました。同型判定はまず次数列を比較して、同じだったら編集距離のアルゴリズムを閾値 1 として走らせてます。

2.はほぼ上に書いたアルゴリズムで尽きていますが、最初に辺の本数の差を調べて閾値以上だったらすぐ return すると結構効率がよくなりました。

ちなみに N = 8, d = 5 のときに構築されるグラフは 12346 頂点 45270502 辺だったらしいです。結構辺が多くて、やる前は 8 頂点ならサイズ 100 の独立集合が見つかるだろうと思っていたけど見つかりませんでした。（それで d = 4 もやった）

一番重いのは全対の距離を求めるところで、8 頂点のときは閾値 6 としておいたら半日ぐらいで求まりました。もっと効率的な方法あるのかな。（ありそう）

コンテストの反省

頑張ったわりには微妙な順位だなーと思いますが、スコアへの寄与が比較的少ないεが小さい場合とε=0.4の場合にしか時間をかけてなかったので、力の入れどころを間違えただけのような気もします（しかもε=0.4のときは結局うまくいかなかった）。

「だけ」といってもコンテストがスコアを競うものである以上それではダメといえばそうですが、スコアよりも楽しさと学びを重視しているつもりなので、その意味ではまあ悪くなかったかなと思います。

やろうと思ったことを一通りやってから提出しようと思っていたら一度も提出しないまま最終日になってしまったのですが（ε=0.4の場合が全くうまくいかなかったため）、今回は特に提出した結果から推定できることがあるタイプの問題だったので、一区切りつくごとに提出した方がよかった気がします。