HTTF2023予選 参加記
はじめに
今年のユースボーダーが去年の倍くらい厳しくなりそうで戦慄しています
最終的な解法
のとき
グラフが頂点シャッフルのみされた後返ってくるため、シャッフルしても判別できるようなグラフが 種類以上ある
のうち最小のものを探せばいいです。
これは bit 全探索と順列全探索を組み合わせれば実装できます。
のとき
個くらいのグラフを作成し、それぞれについて各頂点における次数を昇順ソートした配列を用意しておきます。各グラフ対について次数の誤差(？)二乗和を計算し、その値が
により定まる基準以下であれば基準との差の二乗を、基準と比べ圧倒的に小さければさらに大きなペナルティを加算し、この値が最小になるようなグラフ集合を山登り法で求めます。
グラフ集合は、
1. スターグラフ
2. 次数が全て同じグラフ
3. 次数が である頂点が
個、それ以外は次数
であるグラフ
4. 全ての辺の生成確率をランダムにしたグラフ
から成ります。
また、グラフ作成時に、ジャッジ処理後のグラフの次数がどのように変化するかという確率分布を二項分布を用いて計算しておきます。二項分布は、はじめに前計算しておきます。
クエリ処理は、先ほど計算しておいた確率分布からおおよその作成確率を求め、それが最も大きいものを解とします。確率が 以下のものが含まれている場合はペナルティを与えています。
最終提出
実装がまあまあ汚くなってるのは許してください
日記
day1,2 (11/11,12)
計算量の情報的に頂点関係を含めて復元するのは難しそう→次数だけで判断できる方法が欲しい
スターグラフいっぱい作ると上手くいきそう
次数から構築可能か判定するのはエルデシュガライの定理とかいうのを使って
二項分布をいい感じにいじれるといい感じになりそう
とりあえず のときを実装して 300M 点
day3 (11/13)
m<=50 は何とかなりそう
期待値との誤差二乗和を求めると上手くいきそう → 384M 点
day4 (11/14)
スターグラフに加えて次数が N-1 の頂点を増やしていく作戦→eが小さければ効果大(444M)
ε<=0.1 くらいなら 1e7 点くらい取れるようになってきてる
二項分布を前計算して更に正確な評価ができるようにした
改善してたら意味の分からないバグを踏んだ(終わった後も未だに原因が分かっていない)
day6 (11/16)
生成時に隣接させてたものと間違えることが多い(それはそう)
判定方法を改善するとかなり伸びそう
生成時に辺の生成確率を一定にしたものを混ぜてグラフ集合を山登りで決定 → 481M
次数の生成確率から復元 → 561M
day7 (11/17)
復元時の山登りは隣接交換のが良さそう→微増
グラフを決めた頂点集合の確率の積で評価→602M
頂点集合の作成をちょっと改善→797M
day9 (11/19)
次数を昇順ソートした配列の誤差二乗和をもとに評価する→Nとεに依存した評価→927M(やばい)
ε=0.33 くらいまでまともな解を出してくれるようになる
day10 (11/20)
11/17 の解が一部ケースで現状解に勝ってたので適用範囲を自力にぶたんで適用→ 1050M くらい
おわりに
上位陣の解を見ていると近いようで遠い感じがしますね。悔しいです。
認知している 18 歳以下内での順位が 10 位周辺(たぶん)なので、システスでハマることを祈っておきます。
追記
無事本選出場です！
期末初日→途中参加→翌日JOI2次→翌々日期末2日目 とかいうムーブになりそうですが何とかします
