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. 攻略の勘所
- グラフは任意の同型写像（頂点の入れ替え）で変化する。そのため同型写像で変化しない、「グラフ不変量」に着目するとよい。
- 辺の変化は偏りがある。例えば、全く辺が無い場合、乱数での変化は辺が新たに作られる方向にしか作用しない。逆に、すべて辺が存在する場合、乱数での変化は辺が削除される方向にしか作用しない。
- 相対スコアなので、点数が低くても難しい問題を最適化することの効果が高い。逆に、絶対スコアが大きくできる可能性を見逃さないようにする。
- やることが非常に多岐にわたるため、「前処理」、特に「提出プログラム外での準備」が重要である。
また、全体を通した本問題の大きな特徴として、 「実際のクエリーやりとりを始める前に、クエリーをシミュレーション可能なこと」 があげられる。
なお、最上位の方々の解法に至る勘所は、上記とは一部異なります。
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桁順位はとれたと思うので、上出来。