丸紅プログラミングコンテスト2023(AtCoder Heuristic Contest 024)参加記

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

2023/9/24に開催された丸紅プログラミングコンテスト2023(AtCoder Heuristic Contest 024)に参加しました。

atcoder.jp

ヒューリスティックのレートは、あとちょっとで青に到達というところですが、ここのところ大した結果が出せずで、足踏みが続いています。

今回は、久々の短期コン。今度こそ、良い成績を出して入青を決めようという気持ちで挑みました。

今回の結果

350位で終了。今回も微妙な結果になりました。

AHC024結果
AHC024結果

パフォーマンスは、水色の下というところ。またしても、入青はお預けになりました。。

振り返り

試したい事は色々ありましたが、時間に追われてほとんど実装できずでした。

AHC024提出結果
AHC024提出結果

A問題

A - Topological Map

結論から言うと、最低限のことだけやって提出したという感じになりました。

今回は、マップの各エリアの連結性を維持しながら、どれだけ全体の面積を小さくできるかという問題でした。

連結性を崩すのはNGなので、適当にいじるというのが出来ないところに難しさがあります。

コンテスト開始後は、とりあえずどういうアプローチが考えられるか検討してみましたが、なかなか良いアイデアは思いつかず。なんとか一時間強検討して浮かんだアイデアは、こんな感じでした。

  1. 適当に１行、または１列選んで消すことでマップを圧縮できないか。

  2. 上記を実現しやすくするために、マップ上の余計に出っ張ってるマスをいい感じに塗り替えられないか。

  3. とりあえず、外周マスを可能な限り0に置き換えてスコアを稼げないか。

このうち、３.が一番簡単そうなので、取り急ぎ実装してみようかという感じ。

あとは1.と2.だが、これが難しい。。とにかく、消すことによって、全体の連結性が崩れたらダメなので、そこの判定をどうしようかと色々悩みましたが、まったくいい感じの実装が出来ずじまいでした。

で、気が付いたら、もう残り１時間になろうかというところで、ノー提出。なんか提出しないとしょうがないという所まで追い込まれました。

結局、3.の実装を取り急ぎ実施し、なんとか気持ち程度の点数を獲得。あとは、これを少し改善して、外周を可能な限り0で埋めれる実装まで提出したところで終了です。

最終提出コード

https://atcoder.jp/contests/ahc024/submissions/45915860

感想

  • とにかく考察に結構時間を使ってしまったので、実装に使える時間がありませんでした。

  • コンテスト後のTLを見てみると、今回は焼きなましが強かった模様。やはり、焼きなましの勉強をしないとなあという感じです。

これまでの実績

まだまだ入青は遠いです。

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

総括

短期コンテストの場合は、実装時間に限りがあるので、発想はともかく、実装力が結構大事だと痛感した回でした。

特に、ヒューリスティックコンテストで要求される実装スキルは、アルゴリズムのコンテストとは異なるものになるので、過去問に取り組むことで慣れていく必要があるかというところです。

次月もAHCの開催があるということなので、それに向けて、とりあえず焼きなましが普通に書けるぐらいには精進していこうと思います。

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