最終144位でした。
コンテスト後のツイート
グラフは、「前半に1を詰めるのと後半に1を詰めるのの二通りで、辺の本数の差が辺の総数/Mにしたものたち」に加えて、「各頂点から出る辺の本数が均等なもの」をいくつか使った。Nの値とかは実験して何が良さそうか調べた。
— titia (@titia_til) November 20, 2022
最終提出で順位が10個くらい下がったけど、下振れってことで大丈夫かな……。
クリークに分解したのを上手く戻せたら……という方針でやっていて、どうもうまくいかないため、残り二日あたりで各頂点の辺の個数だけを見る方針に切り替えた。
結論からいうと、どちらでも上位を狙えた模様。
ただ、クリーク判定は他の方の解説など見てもいまいちやり方が分かっていないので、辺の本数だけ見る方針に早い段階で切り替えた方が上位に入る可能性は高かったか。
辺の本数だけ見る方針でもTOP10に入れたらしい。
ここで重要なのは、確率epsのノイズが入ったときどういう辺の個数の分布になるか、というところ。そのあたりの考察が甘かった。（クリークを考えたときや、epsが小さい場合でも、そのあたりをきちんと考えるのが大事だったみたい）
この辺、ちゃんと考察を立式して考えるべきだった。まあ、上手い式が浮かんでいないから立式できていないのだけど、式を探す努力もしていなかった気がする。
また、ノイズに強い「良いグラフを探す」というのは、結構序盤から時間があったらやろうと考えていて、結局最後までできなかった。この辺もできていればもうちょっと違ったかも。
時間いっぱいやり切ったつもりだったけど、そう考えると結構やり残しはあるなぁ。
0 件のコメント:
コメントを投稿