AtCoder Heuristic Contest 025 参加記

AtCoder 競プロ AHC 色変記事

2023/10/14〜2023/10/22に開催されたAtCoder Heuristic Contest 025に参加しました。

atcoder.jp

ヒューリスティックのレートは入青直前という状況でありながら、ここ数回のAHCでは残念な結果しか出ずで足踏みが続いている状況です。とりあえず、今回こそは入青を決めようという気持ちで挑みました。

今回の結果

最終196位で終了。ここ最近のAHCでは、比較的良好な結果でした。

AHC025結果
AHC025結果

パフォーマンスは、なんとか青色を達成。念願の入青を達成することができました。

振り返り

個人的にはかなり頑張ったつもりでしたが、終わってみると色々改善の余地はあるかなあという内容でした。

AHC025提出結果
AHC025提出結果

A問題

A - Balancing by Balance

とりあえず、今回の方針の概要です。

まずは、各袋の重さの分散を最小化する方法のアイデア出しからです。

アイテムの重さが分かっていればランダムの初期解から焼きなましが効くんだろうが、今回は大小関係ぐらいしか分からんということで、これは難しいだろうと。

で、色々考えた所、とりあえず重たいアイテムから順に軽い袋に入れる貪欲を試してみることに。これがテストデータを元に検証してみると、それなりの結果が出たので、大体この方針で行こうと決めました。

未使用のアイテムのうち、重いアイテムを取る方法としては、未使用のアイテムを２グループに分けて１回比較し、軽い方を排除する操作を繰り返し、残った１つを最も重いアイテムとする方法を採用。

この方法だと、厳密には最も重いものが取れない可能性もあるのですが、クエリ回数を抑えつつ大体重たいものを引っ張ってくるにはいい方法かと考えました。なお、軽い袋を取ってくる方法も同じような考え方です。

どうしても十分なクエリ回数がないケースでは、ある程度ランダムに配置するしか無いのですが、その場合は前半の方で、できるだけ複数個まとめて配置し、後半にかけてちゃんと計測していくなどの工夫を実施。

最後の方は、この辺のバランス調整を色々やって、小手先の工夫では限界だと感じたところで終了としました。

ちなみに、最も軽い袋に対して、別の袋からアイテムを一個移動し、移動後の大小関係が変わらない場合は必ずスコアが改善されるという考え方から、クエリ回数が余るケースでは、この操作をできるだけ実行したのですが、気持ち程度の改善にしかなってなかったようです。

最終提出コード

https://atcoder.jp/contests/ahc025/submissions/46859842

感想

  • コンテスト後のTLを見てみると、実際の重さを推測する方法があるということで驚きでした。改めていろんな解法があるものだと感心しきりです。

  • 比較方法については、全然改善の余地があったという感じ。特に袋のソートを完全にしていれば、スコア改善の余地はまだまだあったと思ってます。

これまでの実績

とりあえずヒューリスティック入青です。

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

総括

今回は、そこそこ良い成績が取れた方でしたが、ここから上を目指すには、まだまだ知識が足りないなというのが率直な感想です。

今後の目標としては、入黄を目指していく感じになるというところ。道のりは長くなりそうですが、引き続き精進していきます。

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