2022-11-24

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:このパラメータは結果が色々試してよかったもので裏付けみたいなものはありません

2022-06-06

AHC011参加記

気が向いたので参加記を書きます。

今回 AHC011 に参加して暫定 37.5 M の 60 位でした。

問題

　グリッド上の木をぐちゃぐちゃにした盤面が与えられるので出来るだけ短い手数で木に戻してください。

解法

大まかな流れとしては問題を以下の 2 つのパートに分けてそれぞれ独立に考えました。

(1) タイルの数が整合する木をたくさん見つける。
(2) 見つけた木の形に揃える。

(1) 木を見つける

木の生成は DFS 探索をしました。具体的には空きマスを右下に固定した上で、左上から右下にかけて、そのマスを訪れた段階で残っているタイルを置いていき、適切な枝刈りを挟みつつ探索していきました。

枝刈りは以下の 3 種類を考慮しました (下図参照)。

① がら空き

すでに置かれている左もしくは上マスに関して手が伸びていないのに、手を伸ばそうとするもの、手が伸びているのに手を伸ばそうとするものは置けません。

② ループ誕生

そのマスに置くことでループが出来てしまうものはダメです。ループの判定は連結成分を Union-Find で管理して置き、今見ているマスで複数の手が繋がる場合、それらが同じ連結成分に属しているかどうかを判定すればいいです。undo 可能な Union-Find を用いればマス目を置く前の状態に戻すことが可能です*1。

③ 完結

そのマスに置くことでまだサイズが十分でないのに木が完結してしまうものも条件を満たしません。これは Union-Find にその連結成分から何本空いている手が伸びているかの情報を持たせておけば判定することが可能です。

　試すタイルの順番は最初は 0 から 15 までこの順に探索していましたが、順番固定だとサイズの大きいケースに関して木が見つからない場合があったため、順番をランダムにシャッフルしたものを用意し、その順で初めのマスから探索を 100 ms 行うという操作を 10 回繰り返しました。合計 1 秒の探索で、N = 6 では大体数千個、N = 10 では 50 個程度の木が見つかりました。

　見つかった木に関しては端から順番に元のどのタイルに対応するかを貪欲に割り当てていき、マンハッタン距離の和をコストとしてこれが小さい順に (2) の揃える目標の木として利用しました。

(2) タイルを揃える

タイルの揃え方に関しては以下のステップで計算しました。

① 5×5 になるまで二つずつ揃える。

② タイルと木のマスを対応づける。

③ ビームサーチで完成までの動きを求める。

ビームサーチで求まらなかった場合...

④ 終わらなかった場合 3×3 まで再び二つずつ揃え、再びビームサーチ。

① 5×5 になるまで二つずつ揃える

　最初からビームサーチで完成させたかったのですが、上手い評価関数が作れず、6×6 ではそこそこ見つかるが計算が重い、7×7 以上ではほぼほぼ見つからなかったので、5×5までは二マスずつ端から揃えていきました。

　揃える順番は下図のような端から縦と横を同時に削るような形で揃えました。また揃える時のタイルの選び方は一次元移動より二次元に動かすほうが短い手数で済むということを加味して、評価関数を $\min(|dx|, |dy|) \times 5 + |dx-dy| \times 6$ としてまだ揃えていないタイルの中から最小のものを選択しました。

　揃えるための動きに関しては (空きマス, タイル1, タイル2) の三次元の状態を用意してグラフを構成し BFS で最小手順を計算しました。

② タイルと木のマスを対応づける。

最終的に今あるタイルがどこに行くかに関して、マンハッタン距離の和が最小になるように最小費用流を計算することで求めました。また求めた割り当てに関してパリティが一致せずに到達できない場合は同じ種類の2つのタイルを入れ替えることで到達できるようにしました。

③ ビームサーチで完成までの動きを求める。

　評価関数をマンハッタン距離の和として幅 600 で一手ずつ更新しました。

④ 3×3 まで再び二つずつ揃え、再びビームサーチ。

　タイルと木の割り当てを固定したまま ①③と同様の操作を行い木を完成させました。

おおよそ一つの木に関して揃える手順を計算するのに 100 ms 程度かかり、これを TL まで回し続け、一番スコアの良かったものを採用しました。

感想

　上位の方々が N が大きいケースに関してもビームサーチで答えを見つけているのを見ると評価関数の評価が足りなかったと感じます (ビームサーチのところ一行で終わってるし...) 。コストをユークリッド距離の二乗にするなどは試してみたのですが、特定の盤面に対してペナルティやボーナスを与えるなどの評価は考えてなかったので勉強になります。順番に揃える解法に関しても前計算による高速化はなるほどとなりました。

　最初問題を見たときはどうやればいいのか全く見当がつかなかったのですが、調べたり考えているうちに色々案が出てきて最後まで飽きずにできました。有名問題に近いけどまだまだ考える余地があるという塩梅が絶妙で面白かったです。また次のマラソンも頑張りたいです。

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

*1:例えば RollbackつきUnion Find | Nyaan’s Library