【日記】HTTF（AHC016） - MON.T+α Programming Room

以下はHTTFコンテスト期間時に考えたことをそのままメモしたものです。公開にあたって改めて見直していますがメモ程度のものだったので誤字脱字多いかもしれないです、コンテスト前半は体験記、問題の考察中心で、中盤以降は改善点中心です。

参加登録

　HTTFが今年も行われるみたい。去年は都合が合わず参加できなかったけど今年は参加したい。本選は数年ぶりのオンサイトらしく、大変めでたい話だ。就活一本の人もいるだろうから24卒対象者ではないとしておくか・・・。一応24卒対象者以外でも最上位10人は行けるみたいだが、そこまでの実力がないことはわかっているので、マラソンの経験を積むために参加させてもらおう。

一日目(11/11)

　問題文を読みました。

　よくわかりませんでした。よくわからないのでVisualizerにあるinputを使ってサンプルコードで試そうとしましたが、なぜかうまくいきませんでした。いつもはこれで問題がつかめるのに・・・。問題をよく見るとかなりインタラクティブなようで、これはローカルにいろいろ用意しなければという気持ちになりましたが、それは明日以降の自分に託すことにしました。

今日の取り組み

　・使うグラフの頂点数は少ないほうが良い

　・正答率は高いほうが良い

の二点から、可能な限り極端なグラフを用意して判別するのがよさそう。上で述べたグラフの頂点数が少ないほど正答率下がってしまうのでちょうどよいところを探したいが、それは序盤にやるべきではなさそう。（前科あり）

　極端なグラフといっても、頂点の番号を入れ替えると似たようになるものは、Hの生成方法を考えると判別しにくそう。雑にMと同じだけ頂点を用意してみるか・・・。辺の数が0~N-1個で判別しようとするとエラーに弱いので、等間隔に辺の数を離して 0~N(N-1)/2個で判別したほうが確実かな・・・？

　ん？だとするとエラー率が十分小さいときはそんなに頂点いらないのでは・・・？まあ考え出すときりがないので明日以降にするか・・・

上はそれぞれのGからエラー後の辺の数の期待値をとり、それが最も近いものを選んだ場合

下は頂点数N＝Mで、Gのうちで辺の数が一番近いものを選んだ場合

　辺の少ないグラフは基本エラーで増えるし、辺の多いグラフは基本エラーで減ってしまうので、確かに上のほうが合っていそう。

　どうしても問題が気になるので考察を続行した。

頂点の数少なくしすぎて全然判別できなかった。最終提出が採用されるので間違えたものを提出すると順位表駆け下りていくの面白い。

これらは自己記録よりかなり下だが、順位表ではベストとおなじくらいだった。相対評価、かなり奥が深い・・・

この日はいろいろやってみたがあまりつかめなかった・・・（まだローカルでテストできないけどたぶん正答率結構低い気がする）

　まだサンプルコードを流用しているのである程度考察出来たらGo言語で書いていきたいなあ・・・

二日目(11/12)

　まだコンテストも序盤、そう焦ることはないはず。この日はあまり取り組みませんでした。

　今日の取り組み

　初日のコードをGo言語で実装し、正答率を確認してみる。Seed=2での結果がこちら。

やはり正答率が厳しいか。かといってM=100,ε=0.40でまともに当てる方法も思いつかない。上位陣はどうにか判別できるのだろうか。

　なお、M,εがかなり大きい場合はあきらめてN=4にしたほうが良いんじゃないかと思っていたけれど、そんなことはなかった（最悪ケースではよくなるみたいだが、たぶん最高点からの相対得点ではほぼ無だろう）。ビジュアライザを見る限りもう計算のバグはなさそうなのでシンプルに新しい方針が必要。

　いったんHTTFから離れていると、各グラフから、与えられたHが生成される確率を正規分布に近似した確率計算により求めるのがよいのではないかという結論に至った。どうやら良い方針のようで、この時43位になった。

三日目(11/13)

　今日はほとんどコードを書きませんでした。前日に思いついた正規分布に近似した確率計算に希望を見出したのでそれをもとに構想を練っています。

今日は

・ローカルでseed=0,...,99の100ケースを試す機能

・より筋のよさそうな確率計算

をして多少改善しました。

四日目(11/14)

　三日目に考えていたことと合わせて、一応今回のコンテストでの方針を固めました。今回は順位表が相対評価であることもあって、どの部分に伸びしろがあるのかよくわからないです・・・。

今日の取り組み

今回の方針をまとめてみる。

1. epsが大きくなるにつれて極端に頂点数が増えるようにNを設定（(1-2*eps)が分母に入るようなのが正解か・・・？）

2. Gとして極端なグラフを用意（一部の頂点から大量に辺が伸びているのがよさそう？）

3. 与えられたHをGに可能な限り寄せる

4. GとHの差を確認し、その差がありえるかどうか計算する（各頂点で、辺の数の差は頂点数が十分大きいなら平均(N-1)*eps,標準偏差 *1^(1/2)に従う？）

と書いたところで、突然強くなった。

　これはM個の極端なグラフの取り方によるものであろう。Gとして下の二種類を考えてみると、パターン1とパターン2は意外にも各頂点から出ている辺の数という点では十分区別できるようだ。

上二つは一部の頂点からあらゆる頂点へと辺が伸びている一方、下二つは一部の頂点間でのみ辺が伸びているため、3でのグラフの寄せ方次第ではかなりの差が生まれる。

パターン1

パターン2

この二タイプが区別できないようなエラー率のものはもともとはもっと壊滅的なので、純粋に全ケースで改善したと思われる。

一方でGの多様化により従来の3.の寄せ方（辺の多い頂点順に並べる）ではあまり正しく近づけなくなったので、3.の寄せ方として「i番目とj番目を入れ替えてみて、グラフの差が小さくなれば採用する」を繰り返すというのを実装するのがよさそうだ。

五日目(11/15)

　昨日はかなり得点を伸ばせたのでこの調子で進みたいところですが、今日は少しおやすみ。少しコードがまとまっていないので、最低限整理していきます。

　脱線しまして、ちょっとしたお話。私のコンテスト中の取り組み方は

思いつきを雑に実装→良ければ採用→思いつきを雑に実装→良ければ採用→...→一旦雑な実装を整理→思いつきを雑に実装→...

という風になっています。こうやって見ると山登り法みたいですね。思いつきは採用されないことも多いので、思い付きを実装するときに形を整えてしまうと時間がかかってしまいます。また、一つの思い付きを採用したのちにすぐ整えてしまうと直後の思い付きで破壊されることもあるので、ある程度良いタイミングを見計らって整えています。ほかの方はどうなさっているんでしょうか。

今日の取り組み

　昨日の実装で、方針3.のグラフの寄せ方としてグラフの頂点のswapを考えることになったので最低限の高速化が必要か。とりあえず文字列として辺の情報を持っておくのはあらゆる点で効率が悪く、早急に作り直したほうがよいだろう。ということでbitBoardになった。

あまりに思いつくままに書いていたので構造体、関数定義をしながら、HをGにできるだけ寄せる作業ができているか確認。

　swapも実装できたが、ちょっとswapの性能に自信がないので正規分布による確率計算ではなくグラフの差を評価基準に提出してみた。合計点が下がったが、意外と正規近似の際と張り合っている。

六日目～(11/16~11/20)

　急に雑になりました。というのも、この日以降なかなか改善ができない中でMON.T+α本人が執筆をあきらめてしまったからです。というわけで、コンテスト後の私がこの後の改善についてお話します。時間がたってしまっていることもあり、かいつまんでの紹介になります。紹介する順番ですが、互いに関係するところのみ時系列順です。

　六日目以降の取り組み

・確率計算、もうちょっとしっかりさせてみる

以下のようなHを考える

今回注目してほしいのは二列目の部分。上のHの二列目の形は下二つのGならどちらから生成されただろうか？

確率的に高いのは圧倒的に右（後者）である。これの詳しい話はAtCoder公式解説放送でお話しされていたので割愛。一方、5日目までのの計算システムではepsが小さめの時「わずかに右のほうがあり得る」といった結果だった。

　よくよく考えれば、「本来あるはずの辺がなくなっている」「本来ないはずの辺がある」数のカウントは足し合わせないほうが良い気がする。この二つを区別すると、左のグラフでは「5本のうち2本の辺がエラーでなくなった」右のグラフでは「なかった9本のうち2本の辺がエラーで増えた」となり、しっかり確率に差がつきそうだ。多少改善した

・確率計算、もっとしっかりさせてみる

　今の確率計算、そもそも問題点として、「エラーの起こる数の確率分布（二項分布）が正規分布に近似できるのか」という問題がある。