第10回 Asprova プログラミングコンテスト(AtCoder Heuristic Contest 023)参加記

AtCoder 競プロ AHC 企業主催コンテスト

2023/9/3〜2023/9/10に開催された第10回 Asprova プログラミングコンテスト(AtCoder Heuristic Contest 023)に参加しました。

atcoder.jp

ヒューリスティックのレートも、もう少しで青になろうかというところです。

本当は、前回のAHCで入青を決めたかった所でしたが、あまり良いパフォーマンスが出せずで、入青はお預けとなりました。

ということで、今回の目標は、もちろん青パフォ出して入青を決めることです。

今回の結果

確定441位。。。前回AHCより、さらに低い順位でフィニッシュとなりましたとさ。

AHC023結果
AHC023結果

パフォーマンスも、ギリギリで水色に到達というところ。流石に、これではAHCのレートも伸びてくれません。またもや入青はお預けになりました。。

振り返り

大分考察をサボりすぎた事が、結果に直結したという印象です。

AHC023提出結果
AHC023提出結果

A問題

https://atcoder.jp/contests/ahc023/tasks/ahc023_a

今回の方針を、ざっくりとまとめると、以下のような感じになります。

今回の問題では、植える月、栽培する月の時点で目標のマスに到達できなければ、一気にWAになってしまうという問題。WAにならない栽培計画をどうやって構築するかが最大の悩みどころでした。

で、散々考えて浮かんだアイデアが、作物を植える月を揃えてみるという事。

植える月に関しては、早い方に調整が効きます。よって、例えば１月目については全マスを１月目に植えることにすることで自由に盤面を構築できます。よって、盤面をBFSした時に、距離が遠いところから順に栽培する月が遅い作物を植えていけば、少なくともWAにはならない計画が立てられます。あとは、全てを栽培し切った後に、再度盤面全体に作物を一気に植えていくことを繰り返せば、最終ターンまでそれなりの計画が立てられるという算段です。

あとはどうやって最適な期間で区切れるかという事で、当初は植える月と栽培する月の期間を決めたときの最大スコアがどのぐらいになるかを計算し、トータルで一番最適な期間の区切り方をDPで求めてみました。

これで結構いい線行ってるかなあ、と思って提出してみたら、得点は23Mで順位は400位程度という感じ。。

ならばと、期間を前半50、後半50に区切って、栽培期間が長い作物を奥の方に詰め込んでみたり、また余った作物を適当に詰め込んでいくという実装をしてみましたが、24M程度にしか上がらずでした。

結局、これ以上のアイデアが浮かばすで終了です。

最終提出コード

https://atcoder.jp/contests/ahc023/submissions/45449040

振り返り

  • 今回は植えるタイミングでエラーが出ないように、植える月をある程度揃える方針にしましたが、これが大分ダメだった模様。上位の解法に比べると、大分無駄なコストが多い印象です。

  • コンテスト後にTLを見ていると、通路を決め打ちしている解法が多かった印象。まあ、コンテスト中、通路決めうちも思いつきはしましたが、本人に実装する力がないため不採用でした。。

  • 最上位は、焼きなましをしていた模様。今回の問題は、制約が複雑なので、焼きなましとか絶対無理だなあと思ってましたが、、まだまだ実力が足りないようです。

これまでの実績

ヒューリスティックのレートなので、成績が悪くても、気持ち程度上昇しました。が、、このペースでは入青はまだまだ遠いようです。

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

総括

前回と今回で、まだまだヒューリスティックコンテストで上位に行けるだけの実力が足りてないことを痛感させられました。

一応、今月末には、短期のAHCも開催される予定ということで、なんとかそこでリベンジしたい所。当面、ヒューリスティックコンテストで使えるアルゴリズムの予習に努めたいと思います。

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