参加しながら考えたこと試したことの源泉かけ流し。

最終的な方針はまとめにまとめてあります。

問題概要

好きなグラフを N 個出力せよ。その後、それらのいずれかにノイズを付加したグラフが 100 個入力されるので、それぞれ元となったグラフがどれかを推定せよ。正答数が多いほど、またグラフの頂点数が少ないほど高得点となる。

A - Graphorean

1 日目

問題を読む。推定する系だ！
単に推定するだけじゃなく推定しやすいグラフも自分で作んなきゃなんだ。おもしろ〜！

アッそんで順位表上のスコアが相対スコアになってる！AHC、もう非の打ち所がないぜ。

グラフの同型性判定について軽く調べてみたけど一般にはあまり簡単にできるものではなさそうだ。

グラフの最小数が 10 でグラフの頂点数の下限が 4 ってことは、頂点数 4 のグラフで互いに同型でないグラフが 10 個以上作れるってこと？（メタ考察）
→ 11 個作れるらしい。やっぱりね。

detail.chiebukuro.yahoo.co.jp

この各頂点の次数でソートして同型判別する方法、頂点数が大きくなると粗が目立ち始める（例えば {2, 2, 2, 2, 2, 2} は六角形 1 つなのか三角形 2 つなのか分からない）けど小さいうちは楽で良さそうに見える。

しっかし、eps の最大値 0.4 はかなりキツそうだな...。例えば頂点数 100 で辺 0 本のグラフと 4950 本のグラフがあったとして、ノイズが加わるとこれが 1980 ~ 2970 本くらいに圧縮される。100 通りのグラフを作らないといけない場合は辺の本数の期待値が 10 本刻みぐらいになってしまって、これぐらいは乱数ですぐブレそう。グラフの特徴として辺の総本数だけ見るのは無理がありすぎるので、構造にも着目して構築していく必要がある。

とりあえず eps=0.00 の場合は厳密にやるべきなので完全に個別の解法、それ以降はノイズの大きさに応じて最も似ているグラフとの距離のマージンを調整しつつ...いや、これは距離のマージンを 0 にすると eps=0.00 でも同じ解になる？

グラフの構造の違い、ノイズ付加後にどれくらい顕著に出るんだろなぁ。例えば頂点数 99 で 1 個の大きい輪を作った場合と、三角形を 33 個作った場合。eps=0.40 だとどちらもかなりわちゃわちゃになりそうな気がする。一応大きい輪の方には 6 割程度辺が繋がった輪が少なくとも 1 個はあると期待できるけど、わちゃわちゃの方にもそんなもの探せば 1 個くらいありそうな気がする。あとそれ以前に見つけるのが難しそう。

クリークとかならもう少し分かりやすいかな。頂点数 100 のグラフで、サイズ 10 のクリークを 10 個作る。互いが互いに 6 割程度結合している 10 個の頂点を探す...？どうかな。うーん。

辺の数だけに着目して今すぐ実装に取り掛かりたい誘惑に駆られるけど、この方針だとどうせ 3 日目くらいからどう足掻いても抜けない人たちが現れそうなんだよな...。これ！っていう方針を思いつけられれば良いが。

次数 0 の頂点のノイズ後次数はどのくらいブレるんだろう。

eps=0.4 としても次数 55 以下になる確率が 99.9%。ふむふむ。
そうすると、サイズ 70 のクリークと次数 0 の頂点 30 個とかなら、まぁ次数 70 の頂点がノイズ加えて次数 55 以下になることも同じくほぼなさそう？（追記：そんなわけはないんですが、勘違いにしばらくお付き合いください...）なので、ノイズ付加後もそれぞれの頂点がどちらだったかほぼほぼ正確に判定できるはず。これをサイズ 70~100 くらいでやれば 30 通りくらいは特定可能になる。

あとこれに加えて、上記のパターンと同じくらいの辺の数だけどすべての頂点が均等な次数になってるパターン。これらはノイズ前に次数 0 だったと思われる頂点が見つからないことからこのパターンであることが判別できる（追記：ノイズで次数 0 だったと思われる頂点に化けるよ...）。これらのパターン内での差異は辺の総本数でしかつけられないので、十分にマージンを取りつついくらかパターンを用意する。
雑に計算した感じだと eps=0.4 頂点数 100 の場合、ノイズ後の期待値 ± 100 本くらいに 99% くらい収まるから、200 本ずつ間隔開ければおおむね判別可能で、これで 4950/200 ≒ 25 パターンくらいはイケる。± 30 本くらいだと 60% くらい？精度はかなり低くなるけど一応これで残りの 70 パターンを埋めることもできる。

上の計算は全部一番 eps がキツいケースで考えてるので、M, eps の値に応じてノイズ後のブレ具合を計算して頂点数を適切な塩梅で決めてあげる必要がある。

クリークの中でも次数に差をつけるというのはできそう？次数 70 くらいの頂点が 90 個と、次数 0 が 10 個的な（いやそれはもはやクリークではない...クラスタと呼ぼうか）。これも次数 70 と 0 の違いはノイズ後にも判別できて、次数 90 と 70 の違いはというと、どうかな？多分ある頂点について 90 か 70 か？と言われると正確な判定はできないんだけど、この 90 個の頂点が 90 か 70 か？と言われるとほぼ正確な判定ができると思う。

ふむ...そう考えると (クラスタに含まれる頂点数) * (クラスタに含まれる辺の総本数) の組み合わせでもう少しバリエーションが作れそうだ。うん、とりあえずこれで M=100, eps=0.4 の最悪ケースでもほぼ 100% 正答できそうな解はできそう。あとは入力に応じて如何に頂点数を削減できるかだ。

ただ、やっぱり eps が十分に小さいケースだと別の方針にした方が手堅く頂点数を削減できる気がするのよね。eps=0.0 だとクラスタなんか考える必要ないし、eps が十分低くて高々 2 個くらいしか反転しないと仮定できる場合にはとかでもやはりクラスタ作ったりするよりは、互いに距離が 5 以上のグラフを列挙した方が賢く思える。こっちの方針も実装入る前に詰めときたいな。

グラフの距離について。つまりは「最小何本辺を反転させたら同型になるか」だけれども、これの計算って厳密にやろうとするとまぁ、大変だと思う。多分ここらで最初に言ってたソート済み次数だけ見る雑な同型判定が役に立つんじゃないかな。

eps から高々 X 本くらいしか反転しないと仮定し、以下の手順で指定個数のグラフを作れるか判定する。

グラフの集合を S とする（最初は空）。
S に含まれるいずれのグラフからも距離が 2*X + 1 以上であるグラフを探し S に加える、を繰り返す。
S が指定されたサイズになれば成功。その前にグラフが見つからなくなれば失敗。

これを頂点数について二分探索し、成功した中で最も小さい頂点数でのグラフの集合を出力する。うん、良さそう！距離の定義を厳密方向に寄せていくことでスコアを伸ばす余地もありそう。

というかグラフの集合については埋め込むことが可能なので、厳密な距離で事前にたっぷり時間かけて集合計算しておくこともできるんだ。頂点数 10 くらいまでなら愚直に総当たりで同型判定できそうだけど、それ以上になるとどうかな…。

ところで、クラスタと次数 0 の頂点に分割する方法だと、次数 0 の頂点は特定できるのでそこから伸びる辺は全てノイズと断定できる。辺の総本数から元のグラフ推定する際はこれを考慮すると少しマージン小さく抑えられるかも。

互いに同型でないグラフの個数、OEIS にありそうな気がするなぁと思い 1, 2, 4, 11 で検索すると案の定見つかった。

A000088 - OEIS

頂点数 6 で 156 個あるらしいので eps=0.00 なら N=6 以下でベスト解が出せるようだ。

そろそろ実装に入っていきます。まずは空の Solver クラスの作成と入出力の抽象化から。シミュレーションをたくさん回して使うグラフの剪定にしっかり時間を使いたいので。

時間といえば、今の方針だと制限時間の 5 秒はグラフの剪定に使い切って後の predict のフェーズではほとんど時間を要さない感じなんだけど、predict に時間をかけるという方針も別であるような気がする。まぁこれは必要がありそうならまたおいおい。

...いや、手持ちのグラフと入力されたグラフの距離を計算して〜みたいなことしようとすると自然と時間使いそうだな。普通に使います、時間。

二項分布に関する確率密度とか累積確率を計算するコードを書く。

上手な実装が分からないのでとりあえず愚直に計算するやつを書いた。一応これでも累積確率 (100, 200, 0.5) くらいなら 1ms もかからず計算できるし、(2475, 4950, 0.5) でも 70ms くらい。ひとまずこれで初期の実装は乗り切れるかな。

2 日目

最初はクラスタを作る方の解法から実装してみる。こちらは（eps が小さいケースで最適でないにせよ）全てのケースで完答できるので。

指定したクラスタのサイズとクラスタ内ノードの次元数でグラフを作ってくれるコードを書く。これは id が 0~{クラスタサイズ-1} のノードのうち現時点で最も次元数の小さいノードに対し、指定された次元数になるまで他の次元数が小さいノードと接続していくのを繰り返せばとりあえず条件を満たすものができた（偶奇の関係で 1 だけズレるのは起きるけど）。

実装しててなんかおかしいな...？と思ってたら、

まぁ次数 70 の頂点がノイズ加えて次数 55 以下になることも同じくほぼなさそう

これ何？そんなわけないだろ...。

さすがにもう一つの方の方針で eps が高いケースもカバーできるとは思えないし、方針練り直しか...。

特徴のある構造のグラフにするってのは良いと思うんだけど。

例えば今次数 80 のクラスタを作っているとして、eps=0.4 だと 99.9% で保証される（クラスタ内との繋がりのみをカウントした）ノイズ後次数は 35 以上。次数 90 でようやく 40 くらい。...うーん、さすがにここまでノイズが強くかかると孤立点と誤判断しない方が難しいな。精度を妥協するしかない？

あとこの方針が完全にダメになったという訳ではなくて、eps=0.2 とかなら閾値を下げれるので全然通用すると思う。eps 低め、中ぐらい、高めの三段階で方針分ける？

別のグラフ構造としてウニみたいなのを思いついた。次数 99 の頂点が 1 つ、次数 1 が 99 個。これもまぁ、ノイズ後の次数 50 あたりを閾値として判定すれば eps によるがそこそこの精度で判別できると思う。

アイデアを整理しよう。今大きな方針が 2 つあって、1 つはノイズでブレうる距離だけマージンを取りつつ列挙したグラフを使う方法で、eps 低め向け。eps が高いともう一つの方針で、これはグラフの構造、具体的には各頂点の次数に特徴を持たせて元のグラフを判別する方法。構造には 3 種類あって、クラスタ構造（次数大:多、次数小:少）、ウニ構造（次数大:少、次数小:多）、ランダム構造（次数均等）。次数均等は場合によってはクラスタとかウニに見えることもあるかもなので注意が必要かも。こんな感じか。

eps が高いときは次数大or小を判断するときに低確率で誤判定するのは避けられないので、クラスタのサイズを 1 ずつ飛び飛びにしてグラフを用意すると良いかもしれない。ただその分用意できるグラフ数は減っちゃうけど、そこは頑張って調整するということで。

3 日目

とりあえずクラスタ作る方針の Solver は頂点数 100 決めうちで雑にやって eps が低いケースでは全部正答できることを確認した。

この方針の実装の見通しは立ってきたので一旦置いておいて、ちょっと実装重そうなグラフの同型判定とか埋め込むグラフの生成に取り掛かろう。

メモ: 0.9³⁰ ≒ 4/100 なので、頂点数 100 にしても正答率が (30 + 100/M) % を下回るなら N=4 にして predict 0 だけしてた方がスコアは高くなる。M=100, eps=0.4 とかのケースだともしかしたら有効になるかも？

同型判定がちゃんと動いてそうなので、互いに同型でないグラフの列挙をやる。愚直に発見済みの全てのグラフと同型判定するコードを書いたが、頂点数 8 までならスプラトゥーンやってる間に概ね列挙できた（想定計算完了時間の 5% くらいで全体の 95% くらいが列挙できたので途中で打ち切った）。頂点数 9 についても裏で回しつつ次の作業を進めよう。

これを何に使うのかというと、当然 eps=0.00 ではそのまま使うし、互いに距離が x 以上のグラフの集合を作るのにも使う。というわけで次はグラフ同士の距離（が x 未満であること）を調べるコードだな。

...の前に、eps=0.00 のときの Solver を書いてスコア理論値叩き出せるの確認した。むふー
ひとまずこれで暫定順位表での 1G 点分は確保したことになる。この調子でいくぞ！

冷静に考えると互いに距離が x 以上のグラフの集合は初日に言ってた雑な同型判定でやった方が距離の計算も軽いし集合も楽に見つけられそうなんだった。手つける前に気付いて良かった〜上で見つけた厳密非同型グラフセットに対して激重乱択やるとこだった。まぁ距離 10 以上みたいなこと言われたときにどれくらいの数確保できるのかがやってみないと分からないのだけれど。距離 100 以上とかでもある程度数確保できるなら夢があるよな〜。

4 日目

99% 以下の確率でブレうるだけの距離を↑の雑な距離定義で確保したグラフの集合を使うやつ実装できた。MarginedSetSolver と名付けよう。走らせてみると eps=0.06~0.08 あたりが距離確保できる限界のようだ。

全てを諦めて N=4 で predict 0 だけする Solver を作って、今までの Solver のうちシミュレートして一番スコアが高くなるものを選ぶようにした。悲しいことに eps=0.30 以上だと諦め Solver が一番良いスコアが出る。

クラスタ作る Solver でクラスタ内 or not の判定の閾値を調整したら eps=0.37 くらいまでは諦め Solver に勝てるようになった。そりゃね。

MarginedSetSolver では predict の際に使う距離をソート済み次数の各要素の差の絶対値の和を使っていたが、差の二乗の和が最小のグラフを使うようにしたらスコアが上がった。基本やね。

seed=0~99 の結果を眺めていると、eps=0.08~0.20 あたりはずっと 1e7 点（つまり、頂点数 100 での満点）付近の値が続いている。これは雑に作って開発中断してたクラスタ作る Solver が出してる得点で、スコアが頂点数 100 の満点で頭打ちになっているということは頂点数を減らす余地があるということ。ここは明らかに伸ばせるところなので詰めていこう。

5 日目

クラスタ作る方針、デカクリークの方針だと辺を間引いてパターン分けができるけどウニみたいな方針は間引く辺がないなぁ...と思っていたが、こっちは次数が小さい頂点間に辺を足してあげることでパターン分けができることに気がついた。要するに全体を 0~10 個くらいのクラスタと、90~100 個くらいのクラスタに分けて、それぞれのクラスタの次数が (大, 小), (小, 大) の二通りのパターンがある。また、90~100 個くらいの方のクラスタでは次数の大小にかかわらずクラスタ内の辺の本数を調整することでさらにパターン分けができる。これ使えばかなり精度上げられるんじゃないかな！？

↑ 実装して調整して少し良くなった。具体的には 1e7 点が並んでいたラインが 1.0~1.6e7 くらいになった。

ひとまず手持ちの案は一掃できたので提出！ 16.0G。うーんまぁそんなもんか。本音を言うと 20G くらいは欲しいなと思っていたが...。

伸び代は...やはりほとんど正答できてない eps>=0.35 あたり？ eps=0.15 周辺で 16666667 みたいな全問正解できてそうなスコアが並んでるのも気になる。もうちょっと 1 回くらい誤答するかどうかの瀬戸際まで攻めて欲しい気持ち。とはいえこの辺は伸びるとしても多分せいぜい 2 倍くらいで、現時点での致命的な欠点とまではいかない気がする。

眺めてたら、eps が高い値とはいえ M=11 とかで低スコアになってるのは何とかできるなと気がついた。今ってクラスタの頂点数を 1 刻みでしかパターンに差つけてないので、eps 高いときとかに少しでも大きくブレた頂点があるとアウトになっちゃう。ので、これの刻み数を良い感じに調整する。

今気付いたけど、辺の総本数だけ見るなら、辺が 0 本の場合と N/(N-1)/4 本の場合でブレかたが違う。例えば頂点数 30（辺数 450）の場合、もともとの辺が 0 本だと ~60 本くらいまでブレるのに対し、もともとの辺が 225 本だとせいぜい ± 20 本くらいまでしかブレない。なので、マージンを取るときはそのあたりも考慮すると少し効率よくグラフの生成ができる。（追記：これは嘘で、どちらの場合もノイズ後の辺の数の期待値からのブレ方はそんなにかわんないです。）

冷静に考えたら辺の総本数が同じ {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4} と {9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0} はノイズ後も総本数の期待値は同じだけど、次数の分布は全然違うので判別できるはず。これの特殊な場合だけ切り取ったのがクラスタの方針だったわけで、もうちょっとこれ一般化できるな？

いや、でもこれ MarginedSetSolver でやってることと一緒っぽい...？うーん。

あー、ソートした次数の列についてノイズ前とノイズ後比較するとき、ノイズ後と比較するべきなのはノイズ前ではなく、ノイズ前にノイズ加えた後の期待値の列とノイズ後を比較するべきだな。MarginedSetSolver で predict 時の基準に距離の二乗を採用してスコア上がったのもそういうことだったんだろうな。 → これちゃんとノイズ加えた後の期待値との差の二乗で距離測るようにして提出したら 0.5G 点くらい伸びた。

そう思うと {9, 1, 1, 1, 1, 1, 1, 1, 1, 1} - {9, 9, 2, 2, 2, 2, 2, 2, 2, 2} 間の距離と {9, 1, 1, 1, 1, 1, 1, 1, 1, 1} - {9, 3, 3, 3, 3, 3, 3, 3, 2, 2} 間の距離は一定マージン確保したグラフの集合作る上では同じ扱いなんだけど、どう考えても前者のブレかたは非常に稀なので同じ距離として扱うべきではない...もしかして集合作る上でも差の二乗みたいなの使った方が良い？ → 軽く試したけどあまり上手くいかなかった。

さっき真ん中の方がブレが小さいみたいな話をしていたと思うんだけど、検証すると辺 0 本のときとちょうど半分の辺が繋がっているとき、ノイズ加えた後繋がってる辺の本数の期待値からのブレはほぼ同じくらいらしい。そうなの！？まぁ計算が楽になってラッキーと思おうか...。

6 日目

2 日目に

クラスタ構造（次数大:多、次数小:少）、ウニ構造（次数大:少、次数小:多）、ランダム構造（次数均等）

という話をしていたけど、元のグラフで次数が均等であったことを確認するのは結構難しいことに気付いた。というのも、例えば N=100, eps=0.4 だとノイズ後は各頂点の次数が 99.99% の確率で期待値 ±19 くらいに収まるが、孤立点の少ないクラスタ構造で孤立点のノイズ後次数が全部この範囲に入ることは普通に起こり得て、その場合は次数均等パターンと見分けがつかなくなる。難しいなぁ。

今 63 位なんだけど、この順位帯ならもう少しシンプルなアイデアで効率良くスコアを上げる方法があるような気がする。

MarginedSetSolver で確保してるマージンは概算 99% 以上の確率で正答できる値に設定してたのだけど、これを固定値にしていくつかのバリエーションを用意するようにしたら eps=0.08~0.20 くらいで満遍なく伸びた。概算が雑だったからもうちょっとマージン狭めても OK だったんだろうな。あと気になるのが、マージンの値を偶数にするとなぜか少し伸びる。直感的には距離は奇数の方が、お互いからちょうど等距離のところが発生しなくて嬉しそうなもんだけど。→ バグだった！違和感はやっぱりしっかり追求するべきだね。→ バグじゃないかも、よくわからん...。

7 日目

なんかがむしゃらに色々試しましたがダメでした。メモを書き留める元気もない。無策で色々トライするのは最終手段にした方が良いね。

8 日目

手持ちの Solver を整理しよう。今大きく 5 つの solver があって、全部手元でシミュレートした後一番成績の良かったもので本番に臨むようになっている。

StrictSolver: 互いに同型でないグラフ集合を出力し、各クエリで厳密に同型チェックをする Solver。eps=0.00 でのみ使い、おそらく理論値を出せる。
MarginedSetSolver: 各頂点の次数をソートした数列の差をグラフの距離と定義し、お互い一定以上の距離が離れたグラフ集合を使う Solver。eps=0.01~0.20 くらいで一番つよい。
ClusterSolver: 頂点を次数の極端に大きいものと極端に小さいものの 2 つに分け、それぞれの頂点の個数と接続されている辺の総数でグラフを判定する Solver。eps=0.21~0.35 くらいで一番つよい。
UniformDistributionSolver: 頂点数 100 固定で、全ての頂点の次数が等しいグラフを M 個出力し、辺の数でグラフを特定する Solver。eps=0.35~ かつ M が小さい場合に一番つよい。
SurrenderSolver: 頂点数 4 固定、各クエリの出力も 0 固定。eps=0.35~ かつ M が小さくない場合に一番つよい。

で、今提出時のスコアが 20G くらい。100 点満点中 40 点。eps=~0.20 くらいまでは安定して 10⁷ 点取れているのでおそらくこの辺はボトルネックではなくて、後半の特に SurrenderSolver に頼ってるあたりをなんとかしないとヤバいんだと思う。

eps が大きくなるにつれて ClusterSolver に UniformDistributionSolver が勝ち始めるのだが、これは多分、ClusterSolver が各頂点の次数に着目してグラフを判定しているのに対し、UniformDistributionSolver では辺の総数に着目することで eps が大きくなってもブレを小さく抑えることができていることに起因しているものと思われる。各頂点の次数は高々 99 であり eps=0.40 だとこれが 45~75 くらいにブレるので流石に扱いづらい。

じゃあこういうのはどうだろう。頂点を例えば 4 つのクラスタに分割し、それぞれのクラスタ内の頂点の次数はすべて等しくする。で、この 4 つのクラスタの次数をソートした数列を保持する。{99, 75, 50, 25} みたいな。ノイズ後は各頂点を次数順にソートして 4 分割し、それぞれのクラスタの平均次数を元のグラフのものと比較してグラフの特定を行う。これならクラスタの次数が一頂点の次数よりも相対的にブレにくいからよりロバストになると思う。UniformDistributionSolver の拡張と言っても良いかも。StepwiseDistributionSolver と名付けよう。

↑ のやつ実装してみて期待通り動いてそうに見えるけど、eps 低いうちは MarginedSetSolver に負けるし eps が高くなると ClusterSolver と UniformDistributionSolver に敵わない。ほげ...。確かに次数を {80, 60, 60, 60, 40} みたいにしたときに、60 の上振れと下振れが前後に寄るからその辺が 80 とか 40 に誤判定されやすそうというのはあるけど、それにしても...？

うーん、ClusterSolver を磨くべきなのか...？

もうちょっとちゃんと StepwiseDistributionSolver がうまくいかない理由を調べてみた。例えば seed=40 (M=17, eps=0.27) とかはもうちょっと性能出せそうなものなのに 10⁶ 点くらいしか出せてない。シミュレート中の様子を眺めてみると、

predict (2, 1, 1, 0)  
 answer (1, 1, 1, 1)

みたいな失敗が多い（4 クラスタに分割し、それぞれの次数が a[i] * vertex_num / 4 の意）。ほら見たことか！同じ次数のクラスタが存在しないよう工夫しようね。

改善はしたけど既存の Solver には届かない！そう.....。惜しいところまではいってるんだけどねえ。1000 ケースくらい回すと 3 ケースくらいこの Solver が使われてることもあるけど、それよりこれのシミュレーションに時間を割いた分全体のシミュレート精度が気持ち下がったことによるスコア低下が大きそうに見える。

思ったのが、端っこはノイズに少し強いんだよね。というのも、例えば頂点数 100 で次数 50 の頂点はノイズが加わると多少ブレて 45 とか 55 とかと混同されてしまうんだけど、次数 0 の頂点では 5 と混同することはあっても -5 と混同することはないので。ClusterSolver ではこの性質をうまく活かせている。

しっかし、eps が大きいとは言え seed=63 (M=11, eps=0.39) で頂点数 100 でも全問正解できないのはさすがに何とかできるような気がする。だってお前...たった 11 種類よ？ StepwiseDistributionSolver は何をしてるんだ？

覗いてみたら、使っているクラスタの次数タイプの集合が

 (2, 1, 0, )
 (3, 1, 0, )
 (3, 2, 0, )
 (3, 2, 1, )
 (4, 2, 0, )
 (4, 2, 1, )
 (4, 3, 0, )
 (4, 3, 1, )
 (4, 3, 2, )
 (5, 2, 1, )
 (5, 3, 1, )

こんな感じで、一箇所ズレただけで他の次数タイプになっちゃうのがマズいっぽい。この次数タイプ間にもマージンを取ってあげると良い？

9 日目

んああ！閃いた！そんなことやってる場合じゃないわ。

最初の方で厳密な定義での距離については計算が難しいと言っていたけど、二つのグラフの距離が x 以下（ただし x <= 3 くらい）かどうかなら現実的な時間で計算できそうな気がする。

これができると何が嬉しいかというと、MarginedSetSolver を厳密な距離の定義でできることになるので、同じ M に対してより小さい頂点数で対応できるようになる。今 MarginedSetSolver が活躍してるあたりでは概ね頂点数 7~30 くらいになっており、頂点数を削減はかなりスコアに響く。ようやく 3 日目に列挙した頂点数 6~9 での互いに同型でないグラフの集合が役に立つ時が来たようだ。

厳密な距離で 3 以上離れたグラフ集合を作った。以前のグラフ集合の数からの推移はこう。

6 vertices: 18 -> 22 graphs
7 vertices: 42 -> 68 graphs
8 vertices: 93 -> 100 graphs

これで反転する辺が高確率で 1 本以下の入力に対しては少し強めの応答ができるようになった。

この調子で距離 5 以上でグラフ集合作りたいがこれは頂点数 9 で無限に時間がかかっているので、その間に少し頂点数増えても良いから高速に集合を作れる方法を探す。

距離 5 の集合もできた。

7 vertices: 11 -> 17 graphs
8 vertices: 17 -> 44 graphs
9 vertices: 42 -> 100 graphs

提出したら 0.1G くらい伸びた。思ったより渋かった...。

距離 7 は...作ってみてたけど、あまり意味がなさそう。今のやり方だと 11 頂点くらいになるんだけど、ここらにくると辺の数がだいぶ増えるので、eps が 0.03 くらいでもノイズでの反転数が 3 より大きくなることが結構増えてきてあまり使い物にならなかった。頂点数 8 距離 5 でやる方が成功率が高いまである。この方針もここまでか...。

今 MarginedSetSolver では 14 パターンのマージン値についてそのマージンを確保できる最小の頂点数を求めてやっているのだけど、これ頂点数から確保できる最大のマージンを求めてやった方が実行時の計算が早くなるしその分いろんなパターンを試せる気がしてきた。

N, M のペアから確保できる最大マージンについては事前に手元で計算して埋め込むことにする。

走らせてみたら結構良くて、eps=~0.35 くらいまで MarginedSetSolver が優勢になり、提出したら 1.2G くらい伸びた。最後の足掻きにしては大きい伸び幅。

まとめ

暫定順位 / スコア

70 位 / 20,442,040,800

方針

下記のソルバを手元でシミュレーションして一番平均スコアが高かったものを使う。

StrictSolver: 互いに同型でないグラフ集合を出力し、各クエリで厳密に同型チェックをする Solver。eps=0.00 でのみ使う。
StrictMarginedSetSolver: 反転すると同型になる最小の辺の数をグラフの距離と定義し、お互い一定以上距離が離れたグラフ集合を使う Solver 。実行時間的にシビアなので eps=0.01~0.03 でのみ使う。
MarginedSetSolver: 各頂点の次数をソートした数列の差をグラフの距離と定義し、お互い一定以上の距離が離れたグラフ集合を使う Solver。グラフの推定もソートした次数の列の類似度で行う。eps=0.01~0.35 くらいで活躍。
ClusterSolver: 頂点を次数の極端に大きいものと極端に小さいものの 2 つに分け、それぞれの頂点の個数等でグラフを推定する Solver。eps=0.24~0.35 くらいで活躍。
UniformDistributionSolver: 頂点数 100 固定で、全ての頂点の次数が等しいグラフを M 個出力し、辺の数でグラフを推定する Solver。eps=0.36~ かつ M があまり大きくない場合に活躍。
SurrenderSolver: 頂点数 4 固定、各クエリの出力も 0 固定。eps=0.36~ かつ M が大きい場合に活躍。