HACK TO THE FUTURE 2023 予選(AHC016)に参加しました。
問題名はGraphorean。グラフを複数個作って、ノイズで破壊されたものを識別する問題でした。
結果は暫定テスト1121人中157位でした。本選進出ならず。
問題
単純グラフをM個作って出力してね。
その後グラフの各辺の有無が確率εで反転されて、頂点をシャッフルしたものを与えるのでどのグラフか当ててね。
誤答数とグラフの頂点数が少ないほど得点が高いよ。
考察
頂点数を減らすこと、誤答を減らすことでそれぞれ点が上がる。これはExcelで表を作って、どの辺りを狙うべきか随時確認する。基本的には頂点数が増えても誤答が減る方が嬉しそう。頂点数を減らすのは誤答を減らしてからで良い。
エラー率が0.00～0.40。0のこともあるのね。まずエラー無しなら識別可能なグラフを作れってこと？まずM=10 N=4のパターンのパターンを試してみると、ちょうどN=4で作り切れることが分かる。*1ちゃんと計算してないけど、M=100でもかなり少ないNで出来そう。ただ、ここからエラーあり時の解法に上手く繋がらないので実装は保留。*2
次に極端な例を考える。M=2のとき、「全て非連結な真っ白なグラフ」「全て連結な真っ黒なグラフ」とすればいいのは分かりやすい。逆に、「100個で1つの長い線を作ったグラフ」「各50個で2つの線を作ったグラフ」みたいなのは駄目だと分かる。
順番に依存しないこと、情報が多重化されていることが大事。Nを減らすには、頂点ごとに別々の情報を持たせないといけないかな。…順番に依存しないことが大事と言いつつ、ビジュアライザに頂点番号予測機能があるんだけど、どういうこと…？
色々関係ありそうなワードを掘ってみる。「同型写像」「線型符号」「完全グラフ」「正則グラフ」あたり。→何も分からん。
次数（頂点から生えている辺の数）はエラー率が低いうちはかなり頼りになりそう。次数ごとの頂点数でパターンを作って、*3logMに落とせれば嬉しいの精神。流石にそこまでは落ちないけど。とりあえず次数を使う方針で実装を始める。
実装
とりあえず、次数列を指定するとグラフを作ってくれるという機能から作り始める。いや、難しくない？なんかこれで論文出るレベルっぽいんだけど…。後にあまり厳密じゃないけどそれっぽくやる版を作って、そちらの方が簡単で完成率も高かった。
実データからの次数復元は二項分布を使用。愚直に100C50とか計算しようとして、オーバーフローで死ぬ。試行回数nや成功回数kが1少ない状態から遷移するDPでOK。頂点のマッチングは実は次数が大きい順の貪欲でいいので、頂点ごとにその次数になる確率を求めて全部掛け、一番妥当なパターンを求める。事前確率や一番妥当な頂点組み合わせ以外は無視。
各次数の頂点数は奇数が良さそう。偶数だとちょうど真ん中のケースがどっち寄りか分からない。
辺の引き方は、次数が違う頂点同士での接続を優先すると良さそう。同じだと、エラーが起きたときに1つの情報が大きく動いてしまう。2つの情報が小さく動く方が良い。
あとは分解能や次数の間隔、Nなどを調整すべく、パラメータを変えて自動で回してくれるやつを作ってみる。色々トラブってコンテスト終了までに回しきれなかったが、勝手は掴んだので活用していきたい。*4
この方針だとスコア14M程度が出ていて、おそらく上手く調整しても17Mやそこら？これ以上を狙うと、「次数の多い頂点と次数の多い頂点が繋がっている」とか、そういう情報を見ることになりそう。*5
1つの情報を表すのにビット（辺）を使いすぎなので、小さなクリーク（完全グラフ）を作ればビットのロスを減らせるのではと思いつく。サイズ5,6,7,8,9,10,11のクリークが存在するかで2進表記を試してみる。縦横に並べるとまた別の問題が出そうなので試験的に斜めに並べてテスト。サイズ5にノイズが乗ってサイズ6と誤認するなど、全然精度が出ず断念。
他の人の解法を見て
正直まだ理解しきれていませんが、クリークを1マスに見立ててエラー率0時に作るグラフを大きく作る感じ？
まずエラー率0時のグラフを作れと誘導されている感、クリーク、と材料は集まっていたのに辿り着けなかった感が。情報量をlogで減らすことに執着しすぎてたかな…。
まぁ辿り着いたとしても理詰め実装をしきれる気が全然しないんですが。
感想
数学の教養が無くてうごごご。
ハイパーパラメータ探索に手を出し、結果は出なかったものの勝手は掴んだので今後は活用していきたい。マラソンも突き詰めるごとに設計大事ねとなる。
