AHC016（HTTF2023予選）の日記〜ノイズ付き同型グラフの識別〜

AHC106（HTTF2023予選）でシステムテスト72位（パフォーマンス2132）になりましたので、記念に記事を書きます。

スコアは相対838,757,687,186点、絶対45,359,775,902でした。

今回の問題はとても興味深い内容であり、競プロマラソンコンテストの新境地を開いたのではと思いました。作問された天才の人をはじめとして、提供者の方々、参加者の方々、対戦ありがとうございました。

# 1. 問題の概要

- 与えられたM（$10 \le M \le 100$）に対して、好きなN（$4 \le N \le 100$）を決めて、N頂点のグラフをM個作成する。
- そのあと、100回のクエリーでランダムにグラフが示されるので、それぞれ何番目のグラフなのかを逐次に的中させる。
- なお、クエリーで提示されるグラフは、頂点が完全ランダムに入れ替わり、グラフの辺のありなしは与えられた確率$\epsilon$で変化する。
- スコアは、「$的中率の指数関数 \div N$」に比例する。
- 絶対スコアではなく、問題ごとの「$自分のスコア \div $全人類の最高スコア」の合計（相対スコア）が最終スコアとなる。

# 2. 攻略の勘所

1. グラフは任意の同型写像（頂点の入れ替え）で変化する。そのため同型写像で変化しない、「グラフ不変量」に着目するとよい。
2. 辺の変化は偏りがある。例えば、全く辺が無い場合、乱数での変化は辺が新たに作られる方向にしか作用しない。逆に、すべて辺が存在する場合、乱数での変化は辺が削除される方向にしか作用しない。
3. 相対スコアなので、点数が低くても難しい問題を最適化することの効果が高い。逆に、絶対スコアが大きくできる可能性を見逃さないようにする。
4. やることが非常に多岐にわたるため、「前処理」、特に「提出プログラム外での準備」が重要である。

また、全体を通した本問題の大きな特徴として、 <font color='red'>**「実際のクエリーやりとりを始める前に、クエリーをシミュレーション可能なこと」**</font> があげられる。

> なお、最上位の方々の解法に至る勘所は、上記とは一部異なります。

## 2.1. グラフ不変量の選定

グラフ不変量の詳細は、Wiki（英文がよい。Google日本語翻訳で十分読める）などを参照してほしい。

代表例
+ 辺の数（サンプル回答で利用）　
+ 次数列（頂点ごとの辺の数を、配列にしてソートしたもの）
+ 隣接行列やエルミート行列のスペクトル

これらの中で、比較のための情報量の多さ、計算の簡便さから、次数列を採用する。

## 2.2. 辺の変化の偏りへの対応

単純にグラフ不変量から元のグラフを推定しようとすると、辺の変化の偏りにより推定精度を高められない。そのため、与えられた$\epsilon$を使って、前処理で辺を変化させる試行を多く行っておき、それの結果の次数列（の平均）を記録しておく。実際のクエリーにおいては、記録した変化後の次数列と比較することで、推定精度を高めることが可能である。

次数列の比較には以下の方法を使い分ける。

+ MSE（平均二乗誤差）: 高速に比較可能であり、前処理で多数の比較を実施する場合に都合がよい。
+ K-近傍法: 比較対象となるグラフの組み合わせは全て知ったいる中で、未知のグラフを種別を求める本問題は、教師あり機械学習の多クラス分類問題である。そのため、教師あり機械学習の多クラス分類問題の解法として、平易かつそれなりに精度の高い、K近傍法を用いる。本番のクエリー処理時など、精度が求められる時に利用する。

本番クエリー比較方法を、MSEとK-近傍法で使い分け比較した結果、K-近傍法の方が有意に相対スコアが高かった。これは、偏りの影響で、平均値を中心とした分布になっていないためと思われる。絶対スコアだと、大きいスコアが出る場合に隠されてしまうため、影響はわかりにくい。

## 2.3. パラメータによる戦略の使い分け

長期AHCではおなじみであるが、与えられたパラメータであるMと$\epsilon$によって、戦略が大きく変化する。さまざまな戦略を併せ持った提出プログラムを作成することで、さまざまな可能性にきめ細かく対応でき、結果として相対スコアに強くすることができる。

(1) $\epsilon$=0の場合

+ あらかじめNが小さいグラフは全探索して、次数列が異なるものだけ抽出する。なお、N=9のグラフの探索には、筆者のPCで22時間かかると出たので、諦めた。
+ $\epsilon$=0では、同型写像を除き、辺の乱数変化が無いため、次数列は変化しない。そのため、M以上の次数列種別があるグラフの組合せを使えば、100%正解できる。
+ なおかつ、M=100であっても、N=6のグラフで表せるため、あらかじめ抽出しているグラフの組合せのみで、最高点の獲得が保証される。（次数列が同じグラフでも区別する方法を導入した天才を除く）

|N |全グラフ数 |次数列が異なるグラフ数 |
|--|-:|-:|
|4 |64 |11 |
|5 |1,024 |31 |
|6 |32,768 |102 |
|7 |2,097,152 |342 |
|8 |268,435,456 |1,213 |

(2) Mまたは$\epsilon$がとても小さい 場合

+ 「実際のクエリーやりとりを始める前に、クエリーをシミュレーション可能なこと」を活用して、前処理の段階で焼きなまし法により、最適なNおよびM個のグラフの組み合わせを求める。
+ Mまたは$\epsilon$がとても小さい場合、候補は(1)で準備したグラフの中にある。

(3) Mかつ$\epsilon$がとても大きい 場合

+ ワーストケースにおいては、下手に予測して精度を高めようとするよりも、N=4にして完全ランダムに解答したほうが、絶対スコアが高くなる可能性がある。

(4) 上記以外の場合

+ 別にあらかじめ用意したNが大きいグラフの組み合わせを使って、前処理の段階で焼きなまし法により、最適なNおよびM個のグラフの組み合わせを求める。
+ グラフは、多重ループ型やスター型などから派生させて、なるべくノイズに強そうなグラフを手作業と計算で生成した。Nが大きいと、全探索は不可能であるとともに、乱数でのグラフ生成ではなく手作業と計算での生成にすることで、ノイズ下で相互の識別能力が強いグラフが生成できる。

なお、実際には、上記の戦略の切り替えは、前処理による比較シミュレーションで決定する。

# 2.4. 提出プログラム外での前処理

ここまでに記述した以下の前処理は、精度を高めるにはとても時間がかかる。そのため、提出プログラム外で前処理をして、結果を提出プログラムにエンコーディングしておく。

+ Nが小さいグラフの全探索と次数列の比較
+ Nが大きいグラフの計算処理
+ 代表的なMと$\epsilon$に対応する最適なグラフの組み合わせを焼きなましで抽出

結果として、1469個のグラフ情報、300ケース以上のグラフの組み合わせリスト、を「前処理」して、提出プログラムにエンコーディングした。提出プログラムサイズは約170KBとなった。

また、アドホックに記述を変える前処理はPythonで、高速性が重要な提出プログラムはRustで作成した。

提出プログラムは、前処理ケースで未対応のMと$\epsilon$に対応する、細かいチューニングのみを実施して、その後、本番クエリーを処理している。

# 3. 日記および感想

11/11金

- 問題文読解。見たことがない問題パターン、電子レンジでメールを過去に送るやつ、なんかあったなー。エル・プサイ・コングルゥ・・・。
- 焼きなまし教団員としては、焼きなまししたい！

11/12土

- Twitterで、今回は相対得点方式であるとわかる。Twitterありがとう。
- 少し考察。なるほどなるほど。同型写像での不変量を使うとよさげ。また、提出プログラム外での前処理がかなり重要そう。自分がすぐに見抜いたレベルなので、全人類同じことに気づいていそう。
- 提出している人が多いが、自分はVScodeのフォルダをやっとつくるレベル。

11/13日

- グラフ不変量で、いろいろググる。次数列が使いやすい。
- グラフをあらかじめ作って、コードに埋め込もう。単純に16進数エンコーディングだと512KiBの上限が心許ない。ランレングスエンコーディングと組合せればなんとかなりそう。
- グラフはノイズに強そうな種類を、アルゴリズム的に生成しよう。その組み合わせも、事前に焼きなまししておこう。提出プログラムでは焼かないが、事前に焼く。焼きなまし教万歳。

11/14月〜11/15火

- 事前準備をPyPyでコーディング。グラフの生成、エンコーディング、焼きなまし。一通り作って試してみる。まあうまく動く。

11/16水

- やっと本番コードを書いて、1st submit完。178位、絶対スコア274M点。全人類、すでにレベルが高かった。

11/17木

- なかなか順位が上がらない。方針見直し。次数列以外の不変量は何があるか。隣接行列の固有値スペクトルとか、エルミートスペクトルとかが有名。しかし、固有値近似計算作るだけで期間終わりそうで、それでも重たそう。
- 次数列の比較で、K-近傍法 を使ってみる。正直、効果が出たかどうか不明瞭。

11/18金

- 相対スコアのランキング表を眺める。ローカル実行では半分以上が満点なのに、絶対スコア9G点ということは、満点がたかだか9回しか無い、ということ。これはなぜ？　あー、N=100だけでやっていた。ここではじめて、Nの割り算が絶対スコアに影響あるということを理解する。すごい誤読をしていた！
- 既存のグラフセットをリサイズする関数の追加するとともに、Nが小さいグラフの全探索の必要性を理解する。

11/19土

- 全力で新方針をコーディング、47位、相対スコア21G、絶対スコア1.1Gまでジャンプアップした。

11/20日

- 細かいチューニング、事前計算の密度や精度をあげていく。
- 方針間の自動選択評価を実装。もはやこのあたりは、絶対スコアも増えたり減ったりで、最終日追い込みメンバーに抜かれて、順位も少し落ちる。まあ、2桁順位はとれたと思うので、上出来。