0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴3年半のかえでです。
今回は、第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）に参加しました。開催期間は2023年9月3日(日)10:00から2023年9月10日(日)20:00までの8日間の長期コンテストでした。
今回は十分な時間が取れず、ちょっとしたメモになります。それでも今回の問題がどのような問題なのかを知ってもらったり、簡単な解法を伝えることで興味を持ってもらえたらいいなと思い、公開することにしました。AtCoderのAHCの解説には誰でも投稿することができるので、ぜひ他の方も自分の解法を投稿してもらえればと思っています。それでは、始めましょう。
1.問題文を読む
これまでのAsprovaのコンテストは自分の中では、問題文が長く実装が大変なイメージがあり、参加したことがありませんでした。今回はAHCレーティングの対象となったので正の得点を取るところまでがんばりたいという目標を持ってドキドキしながら問題文を開きました。
あれ？
思ったよりも問題文が短く、入力の受け取りも少ないように思いました。これならできるかも...。わくわくして問題文を読み進めます。
- 分割された土地に作物を育てて収穫する。
- 作物は植えられる期間と収穫するタイミングが決まっている。
- 収穫時には作物を植えた土地と一か所だけある出入口が何も植えていない土地でつながっていなければならない。
詳しくは問題文を読んで欲しいのですが、内容自体はとてもシンプルでした。
2.ビジュアライザを見る
seed0のビジュアライザに手動で入力します。作物1を（0,0）にmonth1の時期に植えたところです。作物1はmonth88までならいつでも植えることができ、month100に収穫できます。Scoreは325でした。左端の真ん中くらいにある切れ目が出入口です。
3.BFSをする
取り掛かることができないまま時間が経過しました。日にちは2023年9月7日。コンテスト5日目です。
BFSをして収穫時期が早い順に作物を並べ替えて、出入り口に近いほうから並べることにしました。同じときに一斉に植えて、全部が収穫し終わったら、もう一度一斉に植えます。100monthが終わるまで一斉に植えることと収穫を繰り返すとseed0のスコアは404600になりました。
提出をすると得点は21,339,175、順位は700人中368位でした。
トップとの差を考えてみます。現在のトップはsaharanさんで、得点は43,768,025です。今回は絶対スコアなので、自分のスコアと比較すると、単純に考えても倍の作物は植えることができそうです。
seed0では4978個の作物があります。先ほどの解法では2170個を植えて収穫していました。ビジュアライザを見ると、先に収穫して空いている土地をうまく活用すればもう少したくさんの作物を植えることができそうです。
今の悩みは、この複雑に区分けされた土地の中で、道として取っておくべき土地と作物を植えても良い土地をどうしたらうまく判別できるのかということです。
4.コンテスト最終日
その後忙しくてほとんど時間を取ることができませんでした。今日は2023年9月10日、コンテスト最終日です。20時に終了するので、自分が使える時間は残り最大10時間程度です。時間のあるときに考察をしていたので、今日は実装をがんばりたいと思います。これからやることです。
- 出入口と出入り口から一番遠い場所までの1本道を作る。そこには作物を植えない。
- 一本道の各地点を全部キューに入れてBFSをする。
- グループに分ける。
- グループごとに植えることと収穫を繰り返す。
- 植える順はDが小さい順（Dが同じときはD-Sが大きい順）。
これまでの自分の解法だと植えてから収穫までのサイクルが長く、最大6周しかできませんでした。グループに分けることで植えてから収穫までのサイクルを短くするのが目的です。グループに分ける方法が詰め切れていないのですが、まずは1本道を作ります。
1本道を書こうと思ったのですが、四隅と結ぼうかなあと思います。(0,0),(0,19),(19,0),(19,19)の各点と出入り口を結んでみます。途中でどこかの道にぶつかったら終了します。経路復元でなぜか(19,19)がバグるので(18,19)に変更。書いてみたら、グループに自然と分かれてくれそうだなあと思います。
UnionFindでグループを作ります。グループごとに作物を植えて収穫できればだいぶ周期が短くなって、スコアが上がりそうだなあと思います。わくわく。
やってみましたがスコアは少し上がっただけで、思ったほど上がりません。しかし少しは上がりそうなので提出します。しかしTLE。100テストケースでは特に問題がなかったので、1000個のテストケースを生成して実行してみます。1ケースだけ、出力がうまく出ていないものがありました。修正して提出しますがまたTLE。困りました…。
その後変更したことです。
- 最初は全ての土地に作物を植えることにしました。
- 最初からスコアの高い作物3000個に絞り込んでみました。
経路復元でバグっていたことがわかり、何とか1000ケースでバグが出ないコードに修正できました。
時刻は19時40分。最終提出を終えたところです。最終提出の方が少しスコアが落ちましたが、1000テストケースで全てACした方を出しました。得点は25,084,175です。6連続TLEが続いたときは最後までACできないのではないかと心配になりましたが、何とかACするコードを書くことができてよかったです。長期のヒューリスティック・コンテストは30分間隔でしか提出できないので、6連続TLEをすると3時間が経過します…。
6.終わりに
あっという間の一日でした。
疲れた～。
とても楽しい問題だったので、他の人の解法を聞くのをとても楽しみにしています！今日の21時からは感想会スペースを開こうと思っています。また、2023年9月13日21時からはAHCラジオもあります。コンテストが終わった後の時間が大好きです。体力的には限界ですが...。
7.最終結果（2023年9月11日更新）
システムテストが終わりました。2000ケース全てACしていました。得点は991,665,725で、909人中419位でした。
昨日と今日は、他の人の解法を見たり、聞いたりしていました。通路の作り方や作物の植え方を工夫していて、参加者のみなさんが共有してくださったビジュアライザのアニメーションを見るのがとても楽しかったです。通路をどのように作るかで見た目がかなり違いました。トップの方たちは焼きなましをしていて、通路がなくなっていたのがすごいと思いました。
あさって2023年9月13日20時からはAHCラジオの放送を予定しています。writerのkozimaさんが出演してくださるとのことで今から楽しみにしています。問題が楽しかったという声とともに、実装が難しかったという声も同じくらい聞きました。サンプルコードを活用することでどの程度の得点を出せるのかを聞けたらいいなと思っています。みなさんもぜひご覧ください。
私のHeuristicのRatingは3だけ上がりました。青になるまであと151。少しでも近づいていければと思います。
