HACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016)参加記

2022/11/11〜2022/11/20に開催されたHACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016)に参加しました。

atcoder.jp

今回のAHCはおよそ1週間という長期のコンテスト。前回の長期コンでは、結局サボってしまい、提出せず終了したので、今回はまともに取り組んでみようかなーという感じで臨むこととしました。

今回の結果

確定295位でした。個人的にはそこそこ頑張ったつもりですが、上には上がいるものだという感想です。

AHC016結果
AHC016結果

今回のパフォーマンスは、水色上位。前回AHC15も同じぐらいでしたね。

レーティングはそこそこ上がって、ヒューリスティックの方も4桁レートに乗せることができましたとさ。

振り返り

初回提出は、最終日の深夜と大分遅めの提出。そこから大きく改善させることはできませんでした。

AHC016提出結果
AHC016提出結果

A問題

A - Graphorean

とりあえず、コンテスト開始から2日間は考察メイン。やった事としては以下のとおり。

  • とりあえず問題文を読んで内容の理解に努める。

  • NとEの関係でスコアがどうなるかをExcelで計算してみる。結果を眺めながら、正答率を上げる事も大事だが、Nを減らす工夫をするのも大事かななど思ったりする。

AHC016スコア考察
AHC016スコア考察

  • 大体の方向性を考える。グラフの辺が一定確率で変わることと、頂点情報がなくなってしまうとのことで、元のグラフとの比較材料は、辺数の増減か次数の増減ぐらいしかないかと考えた。あと、エラー率が0の場合、グラフの辺数が不変になるので、辺数と次数をユニークにしておくと全問正解が可能。ここでどこまでNを減らせるかというところかと。

開始3日目ぐらいから、実装に着手。とりあえず、グラフ生成のパートと、ローカルでシミュレーションを回すところの実装を行う。

グラフ生成は、辺数指定、次数指定をしてグラフを生成する関数を作成。シミュレーション用に、エラー率を元にグラフを変化させる関数を作る。

これを使って、実際に色んなエラー率でグラフがどう変化するかなどを観察してみる。エラー率40%ぐらいになると、次数を偏らせたかどうかもわからないぐらい原形を留めていないように見える。

と、こんな試行錯誤を繰り返しながら、実装内容を詰めていきました。

結局初回提出版の内容としては、こんな感じに。

\epsilon = 0の場合

正答率100%を達成できる最小のNを検証する。

辺数だけでユニークにすると、結果Nが大きくなってしまうので、次数をソートした配列で何通りユニークなグラフを生成できるかを計算した。

結果、N=411個、N=531個、N=6102個作成できる模様。ということで、\epsilon = 0の場合はMに対してこの内容でNを決めることに。*1

\epsilon \ne 0の場合

評価関数として、変化後のグラフと、元のグラフがどの程度異なるかを計算する関数を作成。

元のグラフから、エラー率を元にした、変化後の辺数の期待値、及び次数の期待値に着目し、あとは変化後のグラフの辺数、次数の2乗との差をとっていけばそれっぽい感じになるかと。で、評価関数の結果が一番小さかったものを答えとすることに。

グラフ生成のパートでは、Mを元にグラフ毎の辺数の差を最大するように調整。あと、次数の変化も検証対象になるので、なるべく次数を偏らせたグラフ、次数を平準化したグラフを交互に作成することにしました。

あとは、M\epsilonの値を元に、Nをどうするかというところだが、これは、実際にM\epsilonの全パターンで回してみて、一番平均が大きそうなNを目視で決めていくという方針でいってみることに。シミュレーションの計算とNを決めるために、土曜の1日を使って作業しました。

提出結果

コンテスト終了まで24時間を切った、土曜の深夜に初提出。結果は暫定248位というところでした。

今回は、だいぶ上に行けるかなーという甘い考えがありましたが、それは無惨にも打ち砕かれ、上位陣の凄さに圧倒されるばかり。。

結局、日曜にNの値を少なめに調整したもので再提出。点数が少し上がったところで、終了としました。

最終提出コード

https://atcoder.jp/contests/ahc016/submissions/36688963

これまでの実績

レーティングは上がってくれましたが、これから上に行くのはだいぶ大変そうだなあ、という印象です。

コンテスト実績
コンテスト実績

総括

今回は、なかなか興味深い問題で、どういう工夫をすれば正解率が上がるかを考察するのは、楽しかったです。

反省点としては、公式のビジュアライザをあまり活用できていなかったこと、初回提出が遅く、自分の解法がどれぐらいのものかを把握するのが遅かったところかなあと。

自分なりに取り組んだつもりが、まだまだ考察が荒く、足りないところがあるなあというのを痛感した回でした。

次回AHCでは、この反省を生かして、もっと上のパフォーマンスが出せるように精進していこうと思います。

ということで、また次回も頑張ります。

*1:コンテスト後にわかった事だが、N=5の場合は34個までいけるらしい。。