HTTF2023予選お疲れ様でした。1,377,367,921,862点で7位 (perf. 2898) です。人生初のオンサイト出場権を得ることができてとても嬉しいです。

というわけで、解説を書きます。

問題概要
方針
- グラフの生成
- グラフの復元
細かいテクニック
日記
感想

問題概要

一攫千金を狙う高橋君のためにグラフのエンコードとデコードを頑張ってね。

atcoder.jp

方針

以下のような方針としました。

グラフ生成パート
- グラフの同型性判定を行い、互いに同型でないグラフを $M$ 個列挙する
- ノイズ対策として、大きさ $K$ のクリークを作ってそのクリークを1つの大きな頂点と見なす
グラフ復元パート
- 焼きなましを使用し、元のグラフのクリーク部分に含まれる頂点がそれぞれ同じグループとなるよう復元を試みる
- 各グループを1つの頂点とみなし、同型性判定を行う
- 以上の試行を複数回行い、正しいと思われるグラフを多数決で決定する

HTTFお疲れ様でした！暫定7位かな？
グラフの同型性判定（6頂点あれば識別可能）をしました。ノイズ対策としてクリークを作り、各クリークを1つの頂点と見なしました。どの頂点がどのクリークに属するかは焼きなましで求めますが、失敗することもあるので複数回焼いて多数決をしました。 #AHC016 #HTTF pic.twitter.com/MKkrHtLGgm
— TERRY (@terry_u16) 2022年11月20日

グラフの生成

まず $\epsilon=0.00$ のケースを考えます。*1 頂点がシャッフルされてしまうので、頂点番号が分からない中でできるだけ多くの情報を伝達したいです。頂点を並べ替えて一致する（同型である）グラフを同一と見なすと、頂点数 $n$ と同型でないグラフの種類数の関係は以下の表のようになりました。グラフの各頂点の次数列だけでも多くのグラフを識別することができるので、併せて載せています。

頂点数	種類数（同型性）	種類数（次数列）
4	11	11
5	34	31
6	156	102

最大でも6頂点あれば十分なようです。手元のPCで求め、ソースコードに埋め込んでしまいましょう。以下のような手順を踏みました。

グラフのリストを空で初期化する
bit全探索で $n$ 頂点の無向グラフの $n(n-1)/2$ 辺の有無を全て列挙し、得られた各グラフについて3.～4.を行う
1.のリストに含まれる全てのグラフについて、以下の手順で同型かどうか判定する
1. 次数列が一致するかどうか確かめる*2
2. 各頂点の順列全探索を行い、グラフの構造が一致するかどうか確かめる *3
いずれのグラフとも同型でなければ、1.のリストに追加する

$\epsilon=0.00$ のケースはこれで良さそうですが、 $\epsilon\gt0.00$ のケースではノイズが乗るため誤判定してしまいそうです。そこで、大きさ $K$ のクリークを作ってそのクリークを1つの大きな頂点と見なし、頂点数 $N=nK$ のグラフを作ることにしました。下図のようなイメージです。「辺1本じゃ足りないならたくさん束ねればええやん！」という発想ですね。

大きさ $K$ のクリークを1つの頂点と見なすと、クリーク内には $K(K-1)/2$ 本、クリーク間には $K^2$ 本の辺が張られることになります。 $N\le100$ なので、 $n=6$ のとき $K$ は最大で $16$ 程度まで取ることができます。二項分布を考えると*4、 $\epsilon=0.40$ のケースで反転する辺の数が半分以上となる確率はクリーク内で $1.67\%$ 、クリーク間で $0.08\%$ 程度なので、ノイズに対してそれなりにロバストと言って良いでしょう。

グラフの復元

与えられるグラフを復元したいのですが、

頂点がシャッフルされる
ノイズが乗る

という2つの点が障害となります。

一旦2.のことは忘れて、1.の対処を考えます（と言いつつ2.は最後まで忘れたままになるのですが、それでもそれなりによい結果が得られます）。正しく復元されたグラフでは、下図のように大きさ $K\times K$ の各ブロック部分の辺の有無が全て揃っているはずです。

各ブロックにおいて辺の有無ができるだけ揃うように焼きなましを行いました。より具体的には、

解表現： $n$ 個のグループのそれぞれにどの頂点が含まれるか
初期解： $n$ 個のグループのそれぞれに頂点を $K$ 個ずつランダムに割り振る
近傍：近傍は2つのグループ間のランダムな頂点をswapするだけのシンプルなもの
スコア： $S=\alpha \sum_{i=1}^n{c_{i,i}}+\sum_{i=1}^{n-1}\sum_{j=i+1}^n{\mathrm{max}(c_{i,j},K^2-c_{i,j})}$ を最大化

として焼きなましを行っています。ここで、 $c_{i,j}$ は $i$ 行 $j$ 列目のブロック内の辺の本数、 $\alpha$ は定数（ハイパーパラメータ）です。

焼きなましが終わったら、各ブロック内で辺の有無を多数決で決定することで $N$ 頂点のグラフを $n$ 頂点のグラフに変換し、順列全探索を行うことで元のグラフを推定しました。*5

問題点として、解説放送にあったようにこの焼きなましは初期解依存が大きい（初期解で多数派の方に寄りやすくなってしまう）ので、

焼きなましの初期温度を高くする
$5$ 回焼きなましを行い、それぞれの予測値の和を取って決める

ことを行いました。

細かいテクニック

混同行列

グラフによって正解しやすい・間違えやすいといった傾向があるのではと考え、正解を縦軸、実際の解答を横軸にとった混同行列を各 $(n, \epsilon)$ の組について求めました。下に結果の図を貼っているのですが、グラフによってかなりはっきりとした傾向が出ていることが見て取れます。

解説放送ほどしっかりとした考察はできなかったのですが、

$M$ 個のグラフを選ぶとき、正解率の順にソートして良い方から選ぶようにした
「グラフ $j$ だと推定したときに正解がグラフ $i$ である確率」が分かるので、それを考慮して答えを決めた

といったことを行いました。

混同行列（N=5, ε=0.35）対角成分が白くないグラフは間違えやすいグラフと言える

焼きなましの高速化

焼きなましではグループ間の頂点のswapを近傍として採用しましたが、これは適切に差分計算を行えば $O(N)$ で行うことができます。ここではこれをさらに $O(n)$ に高速化する話をします。

グループ $i$ から頂点 $v$ を削除したときに、グループ $i$ とグループ $j$ の間の辺の数 $c_{i,j}$ がいくつ減るかを高速に数えられればよいです。

入力で受け取ったグラフ $H_k$ について、頂点 $v$ から伸びる辺の集合をbit列 $X_v$ で表現する
焼きなましの解として、グループ $i$ にどの頂点が含まれているかをbit列 $Y_i$ で表現する
グループ $i$ に属する頂点 $v$ を削除することで $c_{i,j}$ がどの程度減少するか求めるには、 $X_v\ \mathrm{AND}\ Y_j$ の立っているビットの数を求めればよい

とすることで、 $c_{i,j}$ の減少量を $O(1)$ で求めることができました。文章だと分かりづらいので、図を貼っておきます。

AND演算とpopcountを用いて、頂点1を削除したときのc_{1,2}の減少量を求める

注意点として、 $X_v$ と $Y_i$ はそれぞれ $N$ bit必要となるため、今回の問題では64bit整数では足りず、128bit整数が必要になります。*6

これを行うことで $K$ 倍速……とまでは行きませんが、3倍程度は高速になりました。最終的にコードテスト上で最大ケースが0.05秒間に20万回ほど回るようになっています。

パラメータチューニング

スコア計算式を見ると分かるようにグラフの大きさ $N$ がスコアに大きく関わってくるため、十分な正解率を保ちつつ $N$ を極力小さくするようなパラメータチューニングが非常に重要でした。*7

ここで、チューニングするときに最大化したいスコアの求め方として「 $(M, \epsilon)$ を固定したテストケースを $T$ 個回して、スコアの平均値をとる」というようなやり方だと乱数によって結果がブレやすいです。

そこで配布testerを少々改造して、 $Q\ (\gg 100)$ 個のクエリを処理したときの正解率 $p$ を出力するようにしました。二項分布を考えると、成功率 $p$ の試行を $q$ 回行い $r$ 回成功する確率は $_qC_rp^r(1-p)^{q-r}$ であるため、スコアの期待値は $\sum_{r=0}^{100}{(_{100}C_rp^r(1-p)^{100-r}\times \mathrm{round}(10^9\times0.9^{100-r}/N))}$ と計算できます。このようにすると乱数によるスコアのブレを抑制しやすくなります。

日記

生々しい方の日記はこちら。考察過程等が含まれていますが、長いです。

github.com

感想

初日に問題文を読んで、その面白さに衝撃を受けました。こういった最適化問題を見るのは初めてだったので、AHCの奥深さというものを感じさせられたように思います。そして最初全く手の付け方が分からなくても、仮説を立てて実験して考察を行うサイクルを繰り返すことでだんだん良い解が出せるようになっていく面白さを今回強く実感しました。

今回で長期コンテスト1ページ目ランクインが連続5回目となりました。安定感が出てきたのは嬉しいです。今回は分かりやすく焼くような問題ではなかったので、こういう問題でも良い成績を取れると自信が付きますね。

長期コンテストの勝ちパターンは今までずっと先行逃げ切りだったのですが、今回は序盤でハズレ方針を2回ほど引きつつも終盤追い上げることができたのは良かったなと思います。行けると思った解法が全然ダメだと凹んだりするのですが、そこで諦めないのは大事ですね。

HTTFは2年前に私が道を踏み外す……ではなく、ヒューリスティックコンテストの面白さを知るきっかけとなった思い入れのあるコンテストだったので、本戦進出権を得ることができたのはとても嬉しいです。本戦も頑張ります！

*1:実際は最初からこのケースを考えられていたわけではありませんでした。詳しくは日記参照。

*2:次数列が一致しなければ同型ではないため、これによりほとんどのグラフを弾くことができます。

*3:私はVF2アルゴリズムを実装しましたが、順列全列挙が十分高速なので不要でした……。

*4:最近勉強したばかりだったので助かりました。

*5:辺の有無を01に潰すのではなく実数値として、元のグラフとの距離を求めた方が良かったかもしれません。

*6:64bit整数を2つくっつけてもよいです。

*7:今回はクラウド対応する余裕がなかったため、ローカルでチューニングを行いました。

TERRYのブログ

最近は競技プログラミングにお熱。

HACK TO THE FUTURE 2023 予選 (AHC016) 解説