HACK TO THE FUTURE 2023 予選 参戦記(AHC016)

※これは日記です　読みにくいかもしれません

一日目

起床コンテスト

無事起きることに成功しました。時差の影響で真夜中の2時に起きなくてはいけないので早く寝ました。えらいです。始まるまではゆっくりボカロの曲でも聞いていましょう。

一応テンプレ的なものも作ってきました。今回はsublime textでプログラムを書いていこうと思います。VSCodeでプログラムを実行してもPCのスペックが悪すぎてまともに実行時間を計れないのでプログラムを実行したりするのはWandboxになると思います。

コンテスト開始

何だこのややこしい問題...グラフとか難しそうです...

初提出はWAでした...20分くらいでバグを見つけて修正したので提出まで10分間休憩です。

正の得点を取りました。

暫定105位です。

方針：N=100、i個目のグラフはi個目の頂点に全部辺をつなげる、クエリでは一番つながってる辺が多かったものを出力する

今思ったのですが、この問題、グラフは全く関係なくて(N^2-N)/2桁のバイナリで情報復元能力を試すものです。つまり、QRコードの誤り訂正符号の仕組みを使えそうです。

少し調べてみましたがQRコードの誤り訂正はリード・ソロモン符号という方法で、めちゃくちゃこの問題に合っている気がします。これ理論値取れる説ありますが、、

しかしあまり理解はできていません。ハミング距離とか逆元とか競プロでつけた知識を総動員しそうです。

でも制限時間が5秒なのでこの方法は想定されてないような気がしますが...まあ時間はいくらでもあるのでとりあえずやってみます。

諦めて適当な貪欲をしてみたら結構いい点数がとれるっぽいので頑張ります。

一日目の結果

新方針：Nは適当に小さめにする、Nを7等分してiの2進数の桁ごとに分ける、1が多いか0が多いかで判断して予想する、で絶対スコア178085が限界でした。ここからは方針を根本的に変えないとだめそうです。

seed=10のビジュアライザ

明日やりたいこと：とりあえずABCで入緑する＆天才解法を思い付く(漠然としている)

一つ考えているのは(N**2-N)/2bit表せるので0から2**((N**2-N)/2)までの数字をM等分して、ハミング距離が短いのを予想する、ということです。微妙な気がしますがやってみないとわからないのでやってみます。

明日はここに入緑した歓喜の気持ちを書き込むので対戦よろしくお願いします。

二日目

ええっと...とてつもない勘違いをしていました...

この制約を見逃していました。根本から制約を変える必要がありそうです。

14頂点のグラフで14*13/2をM等分して1の数をiごとに分ける感じでやったら絶対スコアが100倍程度になりました。昨日の苦労はなんやったんや...

かなり適当な貪欲でやったのでもう少し改善したいです。

一日ずっと頑張っていましたが140M程度までしか上がりませんでした。明日どうにか改善したいと思います。

三日目

とりあえずローカルテスタの自動実行をできるようにしました。

toolsディレクトリの中にmain.pyを入れて、run.batとcalc.pyファイルを作ります。run.batはこんな感じ

calc.pyはこんな感じです。

いろいろコードをこねくり回して期待値を計算するようにしてみたら200Mくらいまで点数が上がりました。ここから何もわからないのですが...たすけて...

四日目

何もわからない！撤退！！！！！！！！

感想

問題文がめちゃくちゃ難しくて誤読まみれでしたが間違いに気づいてコードを修正できたのはえらかったと思います。しかし、長期コンなのに4日目で撤退することになってしまい、自分の集中力のなさに絶望しました(？)。でもおそらくperfはヒューリスティックの中では自己べストになるでしょう。やったー！！