/tmp

雑記帳.

HACK TO THE FUTURE 2023 予選 参加記

ふと思い立って久しぶりにヒューリスティックコンテストに参加してみたので記録しておく。来月には CodinGame もあることだし...。

というか、ヒューリスティックは成績にかかわらずなるべく参加記を残しておきたいという気持ちはある。実際、他のコンテストでも参加記を書こうという気持ち自体はあった。証拠もある。

お蔵入り

単に書き切る前に時間が立ちすぎてしまって思い出せないから書き上げられなくなってしまったということなのだ。今回はそうならないように強い意志を持って書いている。

最終順位がでたのかどうかはよくわからないが、最終スコアっぽいなにかでソートすると 15 ページ目にいるので、およそ 300 位ということで大きく変わらないだろう。 (訂正) 最終スコアはまだ (2022/11/21 22:44) 出ていないらしい。まあ 300 位ぐらいやろ....。それにしても前後の得点は割とばらけているが、こういうものなのだろうか。経験が浅くてよくわからない。

今回は割と長期のコンテストではあったけれど、私が参加したのは事実上最後の土日のみ。とは言えもともとあまり集中力が続かない方なので、もっと前に始めていたからと言ってより良い結果になったとは思えない。

問題概要

0 から  M (10 \leqq M \leqq 100) までの値をグラフ (最大 100 頂点) にエンコードせよ。その後そのうちのどれかのグラフを与えるので、逆にもとの値にデコードせよ。ただし、与えられる前にグラフの各辺は  \epsilon (0 \leqq \epsilon \leqq 0.4) の確率で反転する (あった辺はなくなり、なかった辺が増える) 上、頂点番号はシャッフルされる。なるべく小さいグラフにエンコードして大正解するほど得点が高い。

解法

至ってシンプルに入力の値に応じたサイズの完全グラフをドカンと作り、返ってきたグラフで次数がそれなりに高い頂点の数を数えるということをした。ちなみにグラフの中の部分グラフで完全なもののことをクリークと呼ぶらしいことは後で知った。それでいうと、パターンは入力値に応じたクリークと残りの孤立点、というような構成になっていた。

厳密なケース

 \epsilon が 0 のケースではミスがないので、100 通りのグラフを作っておくだけでいい感じにできる。ただ... 各種の対称性を加味してなお異なるグラフを正しく生成・判断できる自信がなかった上、全体のうち 1/40 でしか通用しない最適化をしても微妙かと思って後回しにしていた結果、サンプルと同じく単に辺の数を数える実装をそのまま残すことにした ( N M を収められる最小のものに変更しているが) 。この判断はあまりよくなかった。

エンコード

基本的には数字をそのまま頂点数として埋め込む。特に 2 進数にするなどの変換は行っていない。ただそのまま埋め込むと言っても 0 頂点の完全グラフを埋め込むというのはちょっと何言っているかわからない。そこで、とりあえずまず  0 \leqq k \lt m の入力値を +1 して  1 \leqq k \leqq m とした。これでまず一旦埋め込むことが不可能ではなくなった。

とは言っても、じゃあ 1 をエンコードして 1 頂点の完全グラフを埋め込みましょうと言っても、それはつまり単なる頂点なわけで、自己辺もないから識別できなくなってしまう。そこで頂点数に余裕があるときは、最低の頂点数  B M \epsilon によって定めて、入力が  k のときは実際には  k + B 頂点の完全グラフを生成することにした。例えば  0.02 \leqq \epsilon \lt 0.05 のときは  B = 10 としたらしい。こうすれば入力が 0 だったとしても +1 して  + B して、結局  B+1 = 11 頂点の完全グラフを作るということになる。これくらいなら十分大きいので判別できそうだ。

よし、じゃあ入力が 99 なら  B + 100 = 110 頂点の完全グラフを...? 残念ながらそうはいかない。 M が大きいときは諦めて、 B は最大でも  100 - M ということになる。

ということはつまり  M = 100 のとき  k = 0 なら 1 頂点の完全グラフを...? そうだよ。

いや、さすがに何も思わなかったわけではない。信じてほしい。挑戦したけど実を結ばなかったんだ。一応後でプレイ中の簡単な流れを記録しておくので、何を迷走していたのかはそれを見てほしい。

デコード

エンコード時点では一部のみがクリーク、残りが孤立点になっているはずなので、極端にたくさんの頂点とつながっている頂点と、全然どの頂点ともつながっていない頂点との両極端になっている。なので多少ノイズが入ったとしても次数は低いものと高いもので割りと極端に分かれるはず。真ん中あたりにいい感じのしきい値が取れればそれ以上の次数の頂点をクリークだと思えば、その集合のサイズから数字が復元できる。のだが、なかなかいい感じのしきい値が見つけられずに苦労した。

ちなみに厳密には、デコード時点では全ての頂点の次数をそのまま確認しているわけではない。グラフの中の各連結成分ごとに限定して、それぞれの中の次数をもとにクリークを検出している。これは後々、一つのグラフに複数のクリークを埋め込むことを考えるための布石を打っておいた。嘘だ。特に何も考えていなかった。クリークが一つの場合はたぶんもともとの次数で考えても良かったと思うが、当時は連結成分を求めるのが一番簡単だと思っていたようである。

問題のしきい値は、いい感じのしきい値が決められなかったので、「次数が割と極端に分かれるはず」という予想を信じて「次数を小さい順にソートしたときに最も大きく跳ね上がった値をしきい値とする」みたいに設定した。例えば次数が [2, 2, 3, 3, 9, 10, 10, ...] のようになっていたら、おそらく 9 以上の次数を持つ頂点がもともとのクリークだろうと推測することになる。

ちなみに連結成分ごとに考えるこのデコード方法では、ノイズによりクリークから完全に切断されてしまった頂点はクリークとして現れ得ない。まあでもそれは仕方ないと思うし完全グラフだからそれよりも切れにくい方法はないわけで、そう変化が偏って切れることはないと信じることにした。

で、クリークらしきものは連結成分ごとに得られることになる。最後の作業はその中から最も評価の高いものを選ぶこと。評価方法はシンプルに、クリークだと判断された頂点たちの次数の標準偏差による。本来ノイズがなければこれらはすべて一致するはずなので、標準偏差が小さければ小さいほどもっともらしいだろうと考えることにした。(ただ孤立点のところで「これが 1 頂点のクリークだ!標準偏差は 0!」と言われてしまうとたしかにとなってしまうので先に  B より小さいクリークは除く。)

スコア概要

最終的に提出していたやつの seed = 100 ~ 199 におけるスコアはこんな感じ。各値の意味はエスパーしてほしい。

0028.txt (31, 0.0) ... N = 9, E = 0, score = 111111111
0067.txt (44, 0.0) ... N = 10, E = 0, score = 100000000
0062.txt (10, 0.06) ... N = 24, E = 0, score = 41666667
0030.txt (12, 0.07) ... N = 26, E = 0, score = 38461538
0057.txt (16, 0.04) ... N = 26, E = 0, score = 38461538
0082.txt (13, 0.06) ... N = 27, E = 0, score = 37037037
0029.txt (21, 0.03) ... N = 31, E = 0, score = 32258065
0059.txt (16, 0.11) ... N = 32, E = 0, score = 31250000
0022.txt (12, 0.11) ... N = 24, E = 3, score = 30375000
0051.txt (24, 0.04) ... N = 34, E = 0, score = 29411765
0072.txt (23, 0.07) ... N = 37, E = 0, score = 27027027
0098.txt (28, 0.03) ... N = 38, E = 0, score = 26315789
0006.txt (32, 0.02) ... N = 42, E = 0, score = 23809524
0061.txt (24, 0.06) ... N = 38, E = 1, score = 23684211
0097.txt (31, 0.06) ... N = 45, E = 0, score = 22222222
0041.txt (33, 0.07) ... N = 47, E = 0, score = 21276596
0080.txt (38, 0.03) ... N = 48, E = 0, score = 20833333
0050.txt (35, 0.05) ... N = 49, E = 0, score = 20408163
0086.txt (29, 0.16) ... N = 58, E = 0, score = 17241379
0063.txt (30, 0.15) ... N = 60, E = 0, score = 16666667
0038.txt (48, 0.07) ... N = 62, E = 0, score = 16129032
0085.txt (59, 0.04) ... N = 69, E = 0, score = 14492754
0076.txt (51, 0.07) ... N = 65, E = 1, score = 13846154
0096.txt (38, 0.15) ... N = 76, E = 0, score = 13157895
0077.txt (39, 0.19) ... N = 78, E = 1, score = 11538462
0036.txt (81, 0.04) ... N = 91, E = 0, score = 10989011
0019.txt (47, 0.14) ... N = 94, E = 0, score = 10638298
0043.txt (57, 0.08) ... N = 71, E = 3, score = 10267606
0092.txt (36, 0.22) ... N = 100, E = 0, score = 10000000
0044.txt (22, 0.21) ... N = 100, E = 0, score = 10000000
0001.txt (42, 0.22) ... N = 100, E = 0, score = 10000000
0027.txt (62, 0.12) ... N = 100, E = 0, score = 10000000
0060.txt (53, 0.18) ... N = 100, E = 0, score = 10000000
0081.txt (33, 0.21) ... N = 100, E = 0, score = 10000000
0033.txt (66, 0.16) ... N = 100, E = 0, score = 10000000
0016.txt (71, 0.11) ... N = 100, E = 0, score = 10000000
0045.txt (50, 0.1) ... N = 100, E = 0, score = 10000000
0064.txt (72, 0.15) ... N = 100, E = 1, score = 9000000
0069.txt (32, 0.27) ... N = 100, E = 1, score = 9000000
0091.txt (27, 0.28) ... N = 100, E = 1, score = 9000000
0011.txt (59, 0.08) ... N = 73, E = 4, score = 8987671
0049.txt (85, 0.04) ... N = 95, E = 2, score = 8526316
0099.txt (42, 0.27) ... N = 100, E = 2, score = 8100000
0012.txt (79, 0.13) ... N = 100, E = 2, score = 8100000
0052.txt (76, 0.06) ... N = 90, E = 3, score = 8100000
0058.txt (47, 0.26) ... N = 100, E = 3, score = 7290000
0042.txt (42, 0.27) ... N = 100, E = 3, score = 7290000
0039.txt (38, 0.27) ... N = 100, E = 3, score = 7290000
0009.txt (80, 0.01) ... N = 86, E = 5, score = 6866163
0054.txt (93, 0.03) ... N = 100, E = 4, score = 6561000
0014.txt (47, 0.25) ... N = 100, E = 4, score = 6561000
0048.txt (79, 0.08) ... N = 93, E = 5, score = 6349355
0018.txt (57, 0.23) ... N = 100, E = 5, score = 5904900
0078.txt (43, 0.24) ... N = 100, E = 5, score = 5904900
0023.txt (16, 0.32) ... N = 100, E = 5, score = 5904900
0035.txt (94, 0.04) ... N = 100, E = 5, score = 5904900
0093.txt (68, 0.09) ... N = 82, E = 8, score = 5249600
0032.txt (19, 0.33) ... N = 100, E = 7, score = 4782969
0084.txt (84, 0.19) ... N = 100, E = 12, score = 2824295
0000.txt (92, 0.08) ... N = 100, E = 13, score = 2541866
0047.txt (91, 0.12) ... N = 100, E = 15, score = 2058911
0031.txt (76, 0.18) ... N = 100, E = 15, score = 2058911
0046.txt (98, 0.07) ... N = 100, E = 15, score = 2058911
0065.txt (53, 0.28) ... N = 100, E = 16, score = 1853020
0020.txt (56, 0.27) ... N = 100, E = 17, score = 1667718
0071.txt (31, 0.32) ... N = 100, E = 18, score = 1500946
0004.txt (96, 0.1) ... N = 100, E = 18, score = 1500946
0068.txt (96, 0.1) ... N = 100, E = 19, score = 1350852
0007.txt (86, 0.14) ... N = 100, E = 20, score = 1215767
0013.txt (84, 0.16) ... N = 100, E = 22, score = 984771
0079.txt (49, 0.31) ... N = 100, E = 22, score = 984771
0053.txt (17, 0.35) ... N = 100, E = 24, score = 797664
0024.txt (92, 0.17) ... N = 100, E = 25, score = 717898
0015.txt (44, 0.32) ... N = 100, E = 26, score = 646108
0040.txt (28, 0.34) ... N = 100, E = 27, score = 581497
0034.txt (90, 0.19) ... N = 100, E = 28, score = 523348
0037.txt (98, 0.19) ... N = 100, E = 32, score = 343368
0090.txt (66, 0.27) ... N = 100, E = 33, score = 309032
0073.txt (44, 0.32) ... N = 100, E = 36, score = 225284
0087.txt (84, 0.26) ... N = 100, E = 39, score = 164232
0066.txt (94, 0.26) ... N = 100, E = 44, score = 96977
0088.txt (29, 0.36) ... N = 100, E = 50, score = 51538
0074.txt (78, 0.29) ... N = 100, E = 50, score = 51538
0025.txt (58, 0.34) ... N = 100, E = 52, score = 41746
0055.txt (78, 0.31) ... N = 100, E = 53, score = 37571
0070.txt (92, 0.3) ... N = 100, E = 58, score = 22185
0094.txt (39, 0.36) ... N = 100, E = 59, score = 19967
0095.txt (60, 0.35) ... N = 100, E = 69, score = 6962
0008.txt (70, 0.35) ... N = 100, E = 71, score = 5639
0002.txt (92, 0.32) ... N = 100, E = 74, score = 4111
0089.txt (17, 0.4) ... N = 100, E = 75, score = 3700
0010.txt (48, 0.37) ... N = 100, E = 76, score = 3330
0056.txt (30, 0.39) ... N = 100, E = 80, score = 2185
0021.txt (83, 0.35) ... N = 100, E = 81, score = 1966
0005.txt (83, 0.37) ... N = 100, E = 85, score = 1290
0026.txt (29, 0.4) ... N = 100, E = 88, score = 940
0083.txt (68, 0.37) ... N = 100, E = 91, score = 686
0003.txt (56, 0.4) ... N = 100, E = 93, score = 555
0075.txt (94, 0.4) ... N = 100, E = 100, score = 266
0017.txt (100, 0.33) ... N = 100, E = 100, score = 266
sum: 1078514052

スコア順に並べているが、誤答率を見ると、やはり  M が大きいケースと  \epsilon が大きいケースに弱い。(その傾向自体は人類全員同じだと思っているが...)

結局  B を大きく取って安定感を増しているだけなので十分下駄を履かせることができないと微妙になる。一部  \epsilon \lt 0.1 くらいのケースでも誤答してしまっているのは  M が割と大きいのに  N をケチりすぎているということで、普通にもったいない。ただこのあたりの数字は温かみのある手動調整なので十分試せなかった。

ちなみに、当時適当に一番下の絶対スコア合計値でなんとなく評価していたのだが、これだと難関ケースを過小評価することになってしまうのをどうすればよいかは最後までよくわからなかった。終わってから、バケモノみたいな人たち (※褒め言葉) が難関ケースで高得点を取ってしまえば自分の解法などそこでは塵になってしまうので、そこの微改善は相対スコア的にはそんなに変わらないみたいなことを言われて鵜呑みにした。よくわかっていない。何れにせよ結局解きやすいところで大きく離されないようにすることは大切そうだった。

あと、なんですか  N = 4 でお祈りって。言われてみれば  0.9^E は絶対にゼロにはならないから、どうせ全ミスするなら頂点数が少ないほうが有利というのは気づきたかった。一番下のスコア 266 とか見てるとやっておけばよかったな...。どれくらい効果があったかはわからないけど。

コンテスト中の流れ

サンプル解提出

問題を読んで、そもそも頂点がシャッフルされる場合にどうやって情報を伝えればいいんや... と本当によくわからなかった。サンプルが辺の数を数えるという実装だったわけだが、これがなければやるべきことの発想が数時間遅れていたんじゃないかと思う。サンプル解で既に天才だと思った。 とりあえずコピー&ペーストで Python のサンプルを投げたあと、Rust で書き直して再提出。全く同一の得点が得られたことを確認した。 サンプル解では  \epsilon が 0 でないときはほとんど正解せず、0 のときは  M によっては逆に頂点の数が必要以上に多いので、とりあえず必要最低限の頂点数だけ使うという自明な改善をやった。実のところ  \epsilon = 0 の場合は最終提出でもこれである。

最初の追加実装

流石に辺の数は変化に脆弱すぎるのでもう少し多少の変化では崩れないようにしたいと思った。この時点で、デコード時にクエリとして与えられたグラフが元のグラフのどのグラフであるかを判別するという方針は取らないことにした。この実装は上位を目指すなら絶対に必要だろうとは思ったが、そもそも対称性を考慮して相異なるグラフたちを生成する方法が全く分からなかったし、作ったとしてももとの頂点順序をいい感じに復元する方法も思いつかなかったし、ロスがあったときにどのグラフと「近い」と判断するべきかの方法も全く思いつかなかった。こういうときになんとなく強そうで実装を始めてもうまくいかないことが経験則により知られているので避けた。なんとなく強そうで改善できる方々、すなわちいろいろな要素の中でどの要素が結果により寄与するか (センスあるいは経験あるいは両方で) 判断できる人たちはすごいと思う。

もとのグラフとのマッチングをしないなら、もとのグラフは単なる模様ではなく、それ自体が何かしら意味を持つようにしなければいけない。その時に思いついたのが 2 つ。

  1. 頂点を円形に並べて隣同士で手をつなぐ。シャッフルされても円は復元できる。そこで対角線のパターンを使って意味を与える
  2. ある程度のサイズのクリークを作成しておき、孤立点からそのクリークの全頂点に向かって辺を張る。そういう孤立点の数をデータとする。

このうち、実装が簡単そうな 2 をまずは選択。 実装し、少なくともサンプルよりはだいぶ強いスコアが出た。ま、サンプルは  \epsilon が 0 じゃないときはほぼ誤答だから...。

それなりの精度を出すためには「ある程度のサイズ」が  M くらい要るということがわかった。すると全体が  2M 頂点必要になるので、 M \geqq 50 で頂点数が足りなくなる。この時点では  M が大きいケースでは 1 の方法でなんとかしようと思っていたので一旦諦めていた。そして 1 についてはある程度実装した段階で、よく考えたら思った以上に対称性が高くない?となってしまい、対角線のパターンが想像以上に少ないことに気づいた。頂点数を増やすのにも限界があるし、冷静に考えたら対角線のパターンを列挙できる人間ならグラフの列挙くらいできるはずだろう。対偶を取って諦めた。そもそも対角線も (多重化していたが) だいぶ対障害性が低そうだったし。

最終提出解

2 の実装はエンコードしたい値に対して 2 倍量の頂点が必要なのがどうもまずい。比率をあれこれ悪あがきしているうちに、そもそも最初からクリークを数えればよいのでは?という発想に至った。むしろなぜこちらが先に出て来ない? ともかく、それならどれくらい下駄を履かせるかにもよるけれど、少なくとも  \epsilon が小さければ 2 倍もいらないだろう。で、生まれたのが最終提出ってわけ。

辺の数を数えてみたり

ここでシンプルな実装として辺の数を多重化して数えるやつも一応、やってみた。グラフは入力×多重度分の辺をセットしておき、戻ってきたグラフの辺の数を数えて期待値が最も近い最初のグラフを返すというやつ。  M が大きくて  \epsilon が小さいときに代替で使えるといいなと思ったが、結局そういうケースですら最終提出に正確性が劣ったため採用できなかった。

やりたかったもの

最終提出解にしても  M が大きいと履かせるべき下駄が用意できないという問題がある。このためにはどうにかして情報効率を上げたい。2 進数でも 3 進数でも良いけれど、あまりグラフが細かいコンポーネントに分かれると復元が難しくなりそうだし、そもそも桁を判別するのも難しくなる。できても 2つだろう。 ならばと「十の位+一の位」というエンコーディングをすることにした。それぞれの位は 0 ~ 9 の数字である。これを 1 ~ 10 にし、従来の方法でエンコードする。ただ、これでは位が判別できない。そこで十の位は 2 倍した偶数、一の位は 2 倍した奇数としてエンコードすることにした。例えば入力が 54 だったとしよう。これは 「10」「9」とエンコードする。逆にデコードしたときにこの 2 つが出てきたときは 54 と復元できる。10 と 9 のエンコードは従来の方法によった、つまり  B を足して 10 + B と 9 + B 頂点のクリークとした。問題は十分な精度で取れるかどうかだが、実際に単一クリークの場合は  \epsilon が小さければそれなりの正答率があるわけなので、要するに 100 連続正解を 200 連続正解にすればよいということになる。少なくとも現状  M が大きいときの小さい値の正答率が塵であることを思えば改善になるのではないかと思った。 M が大きいケースでは  N も減るし。天才では?

だが、まあ、シンプルに考えて、シャッフル+ノイズの後、10 + B と 9 + B が別のクリークであると認識するのが難しい、という、至極当たり前のことに気づかなかったあたりはいつものクオリティである。次数のしきい値が 8 あたりになってしまったとき、2つのクリークがノイズによってたまたま連結になってしまったら (たまたまどころではなく大抵はそうなるわけだが) 合わせて 19 + 2B の巨大なクリークとして発見される。これを分離するのは非常に難しい。総じて  \epsilon が小さいときでも半数程度しか正答できないような状態だった。 これは次数しか見ないとどうやっても倒せないので最小カット的なことを考えることにした。エンコード方法に対して巨大すぎるクリークが発見されたときはそれを最小カットによって 2 つに分割する。これは実装を書き上げた後、バグっていることを確認してコンテスト時間が終了となった。うまく言っていたらどれくらいだったんだろう。言ってもそこまでではない気がする。

2 つのクリーク数がすごく近いのが問題なわけで、10 の位は +30 頂点するみたいなやり方にしておけば実は良かった可能性もあるな...。

反省

まずは  \epsilon = 0 のときの実装をサボったこと。

ここはしっかり詰めるべきだった。全体の得点的に放置するのが不利になるというところもあるし、詰める途中でグラフ同型... とは言わなくても、次数列などもう少し上に向かっていける着想が得られた可能性が高そうだったから。少なくとも問題の理解度は上がったはず。

また、クリークを分離するときにずっとしきい値のことばかり考えていたこと。

それこそこういうところで焼きなましが生きたのかもしれない。わからないけれど、どう分割するのが一番すわりがいいかみたいな最適化をやればより精度が出せたかもしれない。少なくともビジュアライザでノイズ後のグラフを見る限り「これくらいなら復元できるだろう」みたいなときでも取りこぼしてることが多かった。もちろん私が見ているのはあくまで頂点シャッフル前だからというのはあるけれど。このへんはこれから経験を積んでいきたいところ。

最後、相変わらずルールの理解が甘いこと。

 N = 4 お祈りに気づけなかったこともそうだけど、 N をへらすことと正答率を上げることの (具体的な数字での) 優先順位、相対評価であることを前提としてどこを上げるのが相対スコアの向上につながるのか、といったことをもっと詰めるべきだった。パソコンが好きなのでなにか思うことがあったらすぐパソコンカタカタしてしまうけれど、何であれ、一旦落ち着いて考えをまとめてから始めたほうがいいことのほうが多い。

おわりに

やっぱり自分にプログラミングは難しいけど、コンテストは楽しい。この問題は段階に応じた手の届きそうな解法がいくつもあってとてもおもしろかった。サンプル解が重要な気づきを与えてくれる上に改善の余地があって、そこから一段ずつ上っていけるところが楽しかった。少なくともプレイ中の発想と最適化のバランスは個人的にちょうどよかった。長期コンテストは参加できるタイミングがたくさんあるので、なるべく積極的に参加していきたい。すべての時間をコンテストに費やさないといけないわけではないしね。