HACK TO THE FUTURE 2023 予選 (AHC016) 参加記

こんにちは。kens です。

今回 HACK TO THE FUTURE 2023 予選 (AHC016) に参加し、最終相対スコア 62.54 % の 19 位でした！

長期コンの参加記は毎回書こうと思うのですが、サボりがちになっているので今回は真面目に書きます*1。

問題

グラフを $M$ 個作って下さい。その後、 $M$ 個のグラフからランダムに選び、辺にエラー率 $\epsilon$ のノイズを加えた上で頂点をシャッフルしたものが渡されるので、どのグラフから生成されたのか判別してください。100 回のクエリの正答率が高く、またグラフの頂点数が小さいほど多くの得点が得られます。

atcoder.jp

解法

概略

　解法の大筋としては、グラフの中でクリークをいくつか作り、そのクリークのサイズ列を推定することによってグラフを識別しました。クリークのサイズ列はグラフに含まれるクリークのサイズを昇順に並び替えたもので、例えば $N = 10$ のグラフにサイズ 3, 3, 2 の 3 つのクリークが含まれる場合、(2, 3, 3) となります。グラフの作成方法と推定方法に関してそれぞれ分けて説明します。

グラフの作成方法

グラフの作成はクリークサイズをどうするかが肝となるのですが、 $\epsilon \leq 0.31$ の範囲と $\epsilon \geq 0.32$ で方針を分けて考えました。また頂点数を減らすために補グラフを活用しました。

(1) 補グラフの利用

クリークを作ったグラフの辺の有無を入れ替えた補グラフは元々のグラフがクリークを持つ場合はクリークを持たないため、元々のグラフと干渉しにくいです。なので、補グラフを利用することでグラフの種類数を 2 倍にすることが可能で実質的に $M$ を半減できます *2。

(2) $\epsilon \leq 0.31$ の場合

　この範囲では基本的に、使えるクリークの最小サイズを決定した上で、 $M$ 種類のグラフを作れる最小の頂点数をグラフの頂点数 $N$ としました。クリークの数に関しては特に制限を加えていません。

　クリークの最小サイズに関しては、クリークに含まれないある頂点とクリークに含まれる頂点間の辺の数がクリークのサイズの半分以上になってしまうと、その頂点は見かけ上クリークに属するように見えてしまい、サイズの推定を間違えてしまいます。したがってその確率が小さくなることを保証するために、二項分布 $Bin(n,\epsilon)$ に従う確率変数 $X$ に関して、 $P(X \geq \frac{n}{2}) \leq \frac{1}{2000}$ となる最小の $n$ をクリークの最小サイズとしました *3。

　また、これに加えて、頂点数 $N$ を減らすために、この最小クリークサイズを下回るサイズのクリークを持つグラフに関しても、他のグラフとの距離が離れている場合には使えるようにしました。グラフ間の距離はクリーク数が等しい二つのグラフに関してクリークサイズ列の差の絶対値の和としています。

　具体的には、 $P(X \geq \frac{n}{2}) \leq \frac{1}{1000}$ を満たすサイズのクリークに関してはグラフ間の距離 3 以上、 $P(X \geq \frac{n}{2}) \leq \frac{1}{200}$ を満たすサイズのクリークに関してはグラフ間の距離 5 以上離れれば使ってよいということにしました。これによりクリークサイズの推定が多少ずれても、グラフの種類は一意に特定可能です。

$\epsilon \geq 0.32$ の場合

$\epsilon$ が大きくなると、上記の方針では, $M$ がある程度大きくなった場合に $N$ が 100 を超えるので、基本的にクリークの最小サイズを 30、クリーク数は 1 つか 2 つ、 $N = 100$ とした上でグラフ間の距離が出来るだけ離れるように (パラメータは以下の表) グラフを決定しました。候補が $M$ 個以上ある場合は最小のクリークサイズが大きいものを優先的に選択しました。

$M$	グラフ間の最小距離
1 ~ 46	9
47 ~ 64	7
65 ~ 96	5
97 ~ 100	3

グラフの推定方法

シャッフルを考慮しない場合、あるグラフ $H$ が得られた場合のグラフ $G$ の対数尤度 $l(G~|~H)$ は、 $H$ と $G$ で有無の等しい辺の数を $k$ 本とすると、 $l(G~|~H) = k\log (1-\epsilon) + (\frac{N(N-1)}{2} - k) \log \epsilon$ と表せます。これを基に、元々のグラフと頂点をシャッフルした $N!M$ 個のグラフの内、この対数尤度が最大のグラフのクリークのサイズ列が元々のグラフのクリークのサイズ列と考えました。結局やってることは、各辺に関して有無が一致しているときに得点 $\log (1-\epsilon)$ を与え、一致しない場合に得点 $\log \epsilon$ を与え、この合計得点を最大にするクリークの組み合わせと頂点の割り当てを探しています。

この対数尤度を最大化するクリークの組み合わせの探索は焼きなまし法を用いました。クリーク数を固定した上で、最初にある程度共通の辺を多く持つ頂点を同じクリークに属させて初期解を形成し、頂点をランダムに選び別のクリーク (もしくはどのクリークにも属さない状態) に移す近傍を取りました。この処理をクリーク数とグラフか補グラフかに関して全パターンで行い、その中で対数尤度が最大のグラフとクリークサイズ列が等しいグラフ (一致するものがない場合は最も近いもの) を元々のグラフと推定しました。

統計

　自分の解法での seed 0 ~ 999 の 1000 ケースのエラー率 $\epsilon$ に対する誤答数 $E$ 、頂点数 $N$ の分布はこんな感じでした。

感想

　問題文を最初に読んだとき、統計や機械学習よりの問題で AHC003 みたいな感じなのかなと思いましたが、統計よりの解法もマラソンよりの解法も色々あって面白かったです。自分はコンテスト中はクリークを用いる解法しか思いつかなかったのですが、上位の方々のクリーク間に辺を繋げ、一般のグラフの同定判定を行う解法と比べると少し表現力に差が出たのかなと思います。

　ただ何はともあれ、最終的に1 ページ目に残れたので嬉しかったです！なんやかんやレートが橙までもう少しなので早いうちに達成したいです。

　最後に主催していただいたフューチャー株式会社さんと tsukammoさんと運営の方々、作問者の wata さん、どうもありがとうございました！

最後までお読みいただきありがとうございました。

*1:今まで3回くらい書いた気になっていたけど実は1回しか書いていなかった...

*2:さらっと書いていますがこれに気付いたのはコンテスト終了 4 時間前で大慌てで実装しました

*3:このパラメータは結果が色々試してよかったもので裏付けみたいなものはありません