2022/11/11〜2022/11/20に開催されたHACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016)に参加しました。
今回のAHCはおよそ1週間という長期のコンテスト。前回の長期コンでは、結局サボってしまい、提出せず終了したので、今回はまともに取り組んでみようかなーという感じで臨むこととしました。
参加します。
— devgenjin77 (@devgenjin77) 2022年11月11日
今回は期間をフルに使って、じっくりと取り組みたいと思います。
HACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016) - AtCoder https://t.co/2rlDcfrKA2
今回の結果
確定295位でした。個人的にはそこそこ頑張ったつもりですが、上には上がいるものだという感想です。
今回のパフォーマンスは、水色上位。前回AHC15も同じぐらいでしたね。
レーティングはそこそこ上がって、ヒューリスティックの方も4桁レートに乗せることができましたとさ。
次回入水できるように頑張ります。
— devgenjin77 (@devgenjin77) 2022年11月22日
devgenjin77さんのHACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016)での成績:295位
パフォーマンス:1533相当
レーティング:962→1103 (+141) :)#AtCoder #HACKTOTHEFUTURE2023予選(AtCoderHeuristicContest016) https://t.co/JSrcePhZx1
振り返り
初回提出は、最終日の深夜と大分遅めの提出。そこから大きく改善させることはできませんでした。
A問題
とりあえず、コンテスト開始から2日間は考察メイン。やった事としては以下のとおり。
とりあえず問題文を読んで内容の理解に努める。
NとEの関係でスコアがどうなるかをExcelで計算してみる。結果を眺めながら、正答率を上げる事も大事だが、を減らす工夫をするのも大事かななど思ったりする。
- 大体の方向性を考える。グラフの辺が一定確率で変わることと、頂点情報がなくなってしまうとのことで、元のグラフとの比較材料は、辺数の増減か次数の増減ぐらいしかないかと考えた。あと、エラー率が0の場合、グラフの辺数が不変になるので、辺数と次数をユニークにしておくと全問正解が可能。ここでどこまでを減らせるかというところかと。
開始3日目ぐらいから、実装に着手。とりあえず、グラフ生成のパートと、ローカルでシミュレーションを回すところの実装を行う。
グラフ生成は、辺数指定、次数指定をしてグラフを生成する関数を作成。シミュレーション用に、エラー率を元にグラフを変化させる関数を作る。
これを使って、実際に色んなエラー率でグラフがどう変化するかなどを観察してみる。エラー率40%ぐらいになると、次数を偏らせたかどうかもわからないぐらい原形を留めていないように見える。
と、こんな試行錯誤を繰り返しながら、実装内容を詰めていきました。
結局初回提出版の内容としては、こんな感じに。
の場合
正答率100%を達成できる最小のを検証する。
辺数だけでユニークにすると、結果が大きくなってしまうので、次数をソートした配列で何通りユニークなグラフを生成できるかを計算した。
結果、で個、で個、で個作成できる模様。ということで、の場合はに対してこの内容でを決めることに。*1
の場合
評価関数として、変化後のグラフと、元のグラフがどの程度異なるかを計算する関数を作成。
元のグラフから、エラー率を元にした、変化後の辺数の期待値、及び次数の期待値に着目し、あとは変化後のグラフの辺数、次数の2乗との差をとっていけばそれっぽい感じになるかと。で、評価関数の結果が一番小さかったものを答えとすることに。
グラフ生成のパートでは、を元にグラフ毎の辺数の差を最大するように調整。あと、次数の変化も検証対象になるので、なるべく次数を偏らせたグラフ、次数を平準化したグラフを交互に作成することにしました。
あとは、、の値を元に、をどうするかというところだが、これは、実際に、の全パターンで回してみて、一番平均が大きそうなを目視で決めていくという方針でいってみることに。シミュレーションの計算とを決めるために、土曜の1日を使って作業しました。
提出結果
コンテスト終了まで24時間を切った、土曜の深夜に初提出。結果は暫定248位というところでした。
とりあえず期間内に出せました。
— devgenjin77 (@devgenjin77) 2022年11月19日
もう少し調整するやも。。#HTTF #AHC016 pic.twitter.com/06daue8FRj
今回は、だいぶ上に行けるかなーという甘い考えがありましたが、それは無惨にも打ち砕かれ、上位陣の凄さに圧倒されるばかり。。
結局、日曜にの値を少なめに調整したもので再提出。点数が少し上がったところで、終了としました。
ちょっと上がったけど、まだまだ上は遠いなあ。。
— devgenjin77 (@devgenjin77) 2022年11月20日
今回はこれにて終了です。#HTTF #AHC016 pic.twitter.com/Nss7cQvFvJ
最終提出コード
https://atcoder.jp/contests/ahc016/submissions/36688963
これまでの実績
レーティングは上がってくれましたが、これから上に行くのはだいぶ大変そうだなあ、という印象です。
総括
今回は、なかなか興味深い問題で、どういう工夫をすれば正解率が上がるかを考察するのは、楽しかったです。
反省点としては、公式のビジュアライザをあまり活用できていなかったこと、初回提出が遅く、自分の解法がどれぐらいのものかを把握するのが遅かったところかなあと。
自分なりに取り組んだつもりが、まだまだ考察が荒く、足りないところがあるなあというのを痛感した回でした。
次回AHCでは、この反省を生かして、もっと上のパフォーマンスが出せるように精進していこうと思います。
ということで、また次回も頑張ります。
*1:コンテスト後にわかった事だが、N=5の場合は34個までいけるらしい。。