【Postmortem】HTTF2023予選(AHC016) - MON.T+α Programming Room

※画像は公式Visualizerよりお借りしています

この記事は11/11~11/20にAtCoderで開催されました、FUTURE様主催のHACK TO THE FUTURE 2023予選（AHC016）のPostmortemになります。

はじめに
この記事で用いる表現について
最終提出の概要
後悔している点
統計データ
- ローカルでのSeed=0,...,99の得点
- M,epsとNの値
おわりに

はじめに

　11/11~11/20の9日間開催されていた、HACK TO THE FUTURE 2023予選（AHC016）に参加しました。

　結果ですが、システス前54位、システス後は順位を一つ上げ53位でした。

　以下、最終提出について書いていきます。

この記事で用いる表現について

勝手に使っているあいまいな表現があるので書いておきます

・グラフの差

かなり直感的に考えていたのですが、あえてしっかりと定めるなら二つのグラフをそれぞれ01の行列の形で表し、そのxorをとったものです。xorをとったものの1の数を用いて差が大きいとか差が小さいとか言っています。他の方が的を得た表現をなさっていたので参考にしますと、おそらく辺についての編集距離というものです。

最終提出の概要

　言語はいつも通りGo言語です。

基本的にeps<=0.04かそれ以外の2パターンに分けて考えました。

eps<=0.04の場合

1.事前にグラフを用意しておく

2.与えられたHを頂点swapでM個の各グラフと差ができるだけ小さくなるようにする

3.差が小さかったグラフを答えとする

ちなみにグラフを大量に埋め込んでます。

magic4 形の違う11個のグラフ eps=0.00で使用

magic5 形の違う34個のグラフ eps=0.00で使用

magic6 形の違う100個のグラフ eps=0.00で使用

magic6_2 互いのグラフの差が3以上の13個のグラフ eps<=0.02で使用

magic7 　互いのグラフの差が3以上の37個のグラフ eps<=0.01で使用

magic8 互いのグラフの差が4以上の65個のグラフ今確認すると不採用

magic9 互いのグラフの差が5以上の50個のグラフ eps<=0.02で使用

magic10 互いのグラフの差が7以上の25個のグラフ eps<=0.04で使用

magic10_2 互いのグラフの差が6以上の100個のグラフ eps<=0.02で使用

magic12 互いのグラフの差が9以上の100個のグラフ eps<=0.03で使用

magic15 互いのグラフの差が15以上の100個のグラフ eps<=0.04で使用

基本的に2k+1の辺の差があればk個までのエラーに確実に耐えられるので、そのあたりを考えつつ生成しました。

　これらのグラフの数はもっとうまくとればよりたくさん用意できると思いますが、そこまでは詰めませんでした。あんまりその頂点数のでの限界数もらっても、実際に5秒で走らせるほうのプログラムの差計算ががそこまで優秀でなかったのでちょっと間違って別の形のほうが近いといわれちゃうのは・・・。

公式解説放送やほかの方の解法を漁ってみたところ、差ではなくより確率的な計算をすれば、あるいはN=9ぐらいのところでグラフを100個用意できていたら、eps<=0.04で使う分にはN=15とかまで考える必要はなさそうです。

　与えられたHを上で用意したグラフそれぞれに寄せる際には頂点のswapによる局所解を500回くらい求めています。初期解を変えつつ500回こなせば頂点15でもそんなに間違えることはありません。

eps>0.04の場合

1.適当なdを求めて,k<M/2について

(A)1をd*k個並べたのちに残り0を並べる

(B)0をd*k個並べたのちに残り1を並べる

を考え、M個のグラフとして設定する

2.与えられたHに貪欲に頂点番号をつけていく

3.グラフの差について二項分布（頂点数が多い場合は正規分布とみなす）として確率を求める

2.の貪欲に頂点番号をつけるというのはepsが小さいときに行っていた「各グラフの形に近づける」という部分に対応しますが、以下のようにつけることで各Gごとに考える必要がなくなります。

2-0,Hの各頂点に頂点番号をつけておきます

2-1.最も辺の数が多い頂点を選びます（この頂点番号をiとする）

2-2.頂点番号iと1を入れ替えます

2-3.頂点番号が2以上の頂点のうち、頂点番号2以上への辺が最も多い頂点を選びます（この頂点番号をiとする）

2-4.頂点番号iと2を入れ替えます

2-5.以下同様にこれを頂点の数くらい繰り返します

最初に辺の数を計算してそこから入れ替えのたびに辺の数を更新していけば、この作業は非常に簡単に終わります。そしてこれは(A)タイプのグラフとの差を考える場合に、swap操作における局所解になります。（A）の01を反転させた（B）については割愛します。

注：一般にグラフ同士の差を考える場合はこのようにはいきません。あくまでM個のグラフを(A)(B)のようにとったからこそ使える方法です。

　実行時間に余裕があるので、初期値を変えつつ上の手法をやり直します。数百～数千回くらいやり直せましたが、多少精度が上がる程度です。

解法の大別

　様々な解法を拝見したのですが、おおよそ以下のように分類ができると思いました。

自分の最終提出は

・各グラフの合計の辺の数が全然違えばよいのでは？

・各グラフにそれらしい頂点番号をつけてみる

・「あるはずの辺がない」「ないはずの辺がある」これもある確率分布に従う？

を念頭に作られています。

（頂点番号をつけていますが、頂点番号の完全一致を目指すものではなく辺の多いグループと辺の少ないグループを当てることが目標なので、そういう意味ではグループ分けのほうが正しいかも？）

　エラー率が少ない場合(eps<=0.04)では

・グラフが形として全然違えばよいのでは？

・与えられたHにそれらしい頂点番号をつけてみる？

・「あるはずの辺がない」「ないはずの辺がある」をカウントしてみる？

を採用しています。

　エラーがひどい場合は諦めたらよいのでは？（つまりN=4にする）

というのは、最後まで採用するか悩みましたが、最悪ケースでもなんとかあきらめた場合と張り合えるようになったので採用しませんでした。

後悔している点

もっとグラフとしてとらえていれば・・・

　上の解法の紹介の段階でお気づきかもしれませんが、私MON.T+αは今回の問題を対称行列的にしか見ておらず、swapの実装もしっかり行列の行入れ替え・列入れ替えを念頭に実装してしまっています。頂点同士が辺でつながっているという感覚が全くありませんでした。結果、M個のグラフの選び方はPythonのサンプルコードの延長線でしかなく、クリーク（部分完全グラフ？）とやらのアイデアが浮かぶこともありませんでした。そういった解法を拝見した後で自分の解法を見ると、ある意味大きなクリークを埋め込んでいるとも言えるんですが・・・。次回はより広い視点で問題を見つめることで幅広い着想を得たいですね。

もっとM個のグラフについていろいろな場合を試していれば・・・

　これは問題の特徴をもう少し考えておくべきだったと反省しています。

　今回の問題、プログラムが考えるのは、

・M個のグラフを何にするか

・与えられたHがM個のどれから得られたものか

の二点ですが、「M個のグラフをどんな形にするか」を決めた時点で、ある程度取れる得点の限界が決まってしまいます。私は「生成が簡単かつ元のグラフの形を推し量りやすい」という理由で

上のようなグラフを採用してしまいましたが、これはバリエーション豊かなグラフの一部分しか使えていません。順位表といろいろな方の解法を照らし合わせてみると、たとえ各グラフからの生成確率を最も正確に判定しても、暫定テストのスコア限界は20~25Gなのではないかという気がしています（自分の前後あたりまで似た解法の方が多かった気がします）。特にエラーが少ない場合での頂点数が多くなりがちです。

　最終的に「与えられたHがM個のどれから得られたものか」の段階は十分妥当な結果を返しており、実行時間もかなりの余裕があったので、最上位陣のような「元の形を推し量るのに技術を要するが、推し量ることができたらかなり高得点」なグラフに挑戦してみてもよかったかもしれません。

頂点数N、ローカルで最善のものを探していれば・・・

　これはいうほどスコアにおいて致命傷になってるわけではないんですが、シンプルにローカルで試せることはいろいろ試しておくべきだったなと思っています。ローカルで回す分には特に何かを失うわけではないですし。

統計データ

ローカルでのSeed=0,...,99の得点

ローカルでデータを取っていたものの中での最高点を示しています。詳しくはわかりませんが、正答率100%をとれていないケースが20~25ケースほどあります。

Seed	M	eps	Score
0	10	0	250000000
1	76	0.01	100000000
2	87	0.25	10309278
3	48	0.34	8100000
4	31	0.05	62500000
5	32	0.06	58823529
6	80	0.04	66666666
7	51	0.15	23809523
8	93	0.31	6561000
9	47	0.26	14285714
10	72	0.38	119725
11	41	0.36	6561000
12	39	0.28	13698630
13	69	0.04	66666666
14	35	0.16	27777777
15	26	0.15	37037037
16	32	0.4	646108
17	97	0.38	46383
18	83	0.16	17543859
19	75	0.14	20408163
20	58	0.13	25000000
21	57	0.27	11111111
22	70	0.03	66666666
23	63	0.32	7290000
24	17	0.27	26315789
25	67	0.32	7290000
26	91	0.34	1350851
27	75	0.13	21739130
28	45	0.06	40500000
29	88	0.11	21276595
30	64	0	166666666
31	11	0.24	40000000
32	49	0.24	14285714
33	50	0.19	18867924
34	72	0.15	20000000
35	29	0.03	83333333
36	54	0.05	43478260
37	33	0.05	56250000
38	34	0.33	10000000
39	66	0.04	66666666
40	17	0.28	20833333
41	36	0.16	27027027
42	89	0.01	100000000
43	15	0.08	71428571
44	33	0.18	25000000
45	83	0.36	423911
46	96	0.02	100000000
47	92	0.3	7290000
48	30	0.39	2058911
49	27	0.1	45000000
50	30	0.18	27027027
51	48	0.26	13157894
52	82	0.1	25000000
53	18	0.35	12500000
54	58	0.09	34615384
55	14	0.26	32142857
56	49	0	166666666
57	77	0.03	66666666
58	42	0.36	4782969
59	71	0.36	717897
60	92	0.21	12857142
61	14	0.25	37037037
62	98	0.03	66666666
63	11	0.39	10000000
64	20	0.37	10000000
65	13	0.06	90000000
66	77	0.08	27777777
67	83	0.09	25641025
68	17	0.16	47619047
69	84	0.18	15625000
70	99	0.31	4304672
71	100	0.02	100000000
72	54	0.1	30303030
73	97	0.38	46383
74	87	0.38	107752
75	29	0.16	36000000
76	13	0.39	9000000
77	93	0.33	2541865
78	75	0.19	16666666
79	70	0.19	16666666
80	61	0.04	66666666
81	77	0.23	12658227
82	62	0.3	10000000
83	97	0.3	5314410
84	60	0.05	38461538
85	33	0.31	11363636
86	76	0.11	23809523
87	93	0.28	9000000
88	56	0.04	66666666
89	56	0.23	15000000
90	41	0.19	20833333
91	22	0.03	100000000
92	51	0.3	10000000
93	50	0.05	45000000
94	56	0.19	18518518
95	66	0.35	2287679
96	81	0.4	11790
97	26	0.35	10000000
98	32	0.3	11904761
99	88	0.12	20408163