TOYOTA Programming Contest 2023 Summer(AtCoder Heuristic Contest 021)参加記

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

2023/6/25に開催されたTOYOTA Programming Contest 2023 Summer(AtCoder Heuristic Contest 021)に参加しました。

atcoder.jp

前回のAHC020は所用で不参加だったので、結構久しぶりのAHC参加です。

また、１日間の短期コンテストでの参加も超久しぶり。大分ブランクがある状況ですが、とりあえず時間フルに使って取り組もうという気持ちで臨むこととしました。

今回の結果

なんと確定114位！これまでのAHCでの最高順位を大幅に更新することが出来ました！

AHC021結果
AHC021結果

おまけに、人生初の黄パフォをゲット。ヒューリスティックのレートは大幅に上がり、もう少しで入青が見えてくるところまで来ました。

振り返り

今回は、開始後早々に思いついたアイデアが的を得ていたようで、かなり良い結果が出てくれました。

AHC021提出結果
AHC021提出結果

A問題

A - Pyramid Sorting

開始から１時間程度は、ざっくりと問題の考察をしておりました。

以下、考察内容。

  • 多分操作回数1万回もあれば、ピラミッドの上の全てのボールをソートされた状態にできそう。

  • よって、完全にソートするための交換回数をできるだけ少なくする問題と解釈することができる。

  • ピラミッドを完全にソートするためには、自分より大きな数が上部に存在する場合交換するという操作を貪欲に繰り返していけばＯＫ。これを0から464まで順次繰り返していく。

とりあえず、考察に沿ってソート部分を実装。なんとかビジュアライザ上では、ピラミッドをソートすることに成功しました。

しかし、これだと与えられた入力に対して操作回数は一意になってしまう。スコアを改善していくには、何らかの工夫が必要。

ソートするための交換操作は必然的に上下に隣接する対する操作になる。であれば、なんらかの操作で解を改善するには左右の要素交換の操作が出てくるはずと推察。つまり、左右のペアを適当に交換してからソートする、を繰り返して最善を採用すれば良いのでは。

最終的な実装としては、先ず全ての左右のペアに対して、一定の確率(1%～5%)で要素交換を行った後、前述した小さい値から貪欲に上に持っていくソート処理を実行。このセットを時間いっぱい繰り返し、一番操作回数が小さいものを採用という形にしました。

これで、貪欲ソートだけの実装よりは、多少解が改善されたので提出。あとは実行時間の調整や、左右ペアの交換が発生する確率の調整などを実施してました。

これで、一時は70位台まで順位を伸ばせましたが、これ以上の改善手法は見いだせず。。終了にかけてどんどん順位は下がってしまい、結局114位という結果になりましたとさ。

最終提出コード

https://atcoder.jp/contests/ahc021/submissions/42955261

振り返り

自分の実力からすると、今回の結果は出来すぎのように思えます。

コンテスト中は、上位層との差がどこにあるのか全く分からずでしたが、上位層はビームサーチを使用していた模様。自分には使いこなせていない手法だったので、今後のために復習しておきます。

あと、痛い失敗として、今回はコンテスト終了後のシステムテストがあるものと勘違いしておりました。

システスでTLEしたらいかんと、最終回答は実行時間に大分余裕をもった形で作ってしまいましたが、これは実際は得点を下げる結果となってしまいました。

問題文はちゃんと全部読んでおかないといけないという教訓を得ました。

これまでの実績

人生初の黄パフォをゲットし、一気に入青直前までレートを伸ばすことに成功。次で入青を決めたいところです。

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

総括

今回のような短期コンテストでは、初っ端にいいアイデアが出るかどうかが大きな勝負の分かれ目ですね。今回たまたま当たりの解法を引けたので、良い結果が出たものと思います。

ヒューリスティックコンテストのレートは順調に上がっていますが、逆に言うと、次からはレート以上の結果が残せないと停滞モードに入ってしまうということです。今回の結果に満足せず、上位陣の解法の理解を深めて実力を上げていこうと思います。

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