2023/11/5に開催されたトヨタ自動車プログラミングコンテスト2023#6(AtCoder Heuristic Contest 026)に参加しました。
前回のAHCで青パフォをゲットし、ヒューリスティックのレートは、やっと入青というところまで来ました。
今後は、青パフォ以上を取っていかないと、まともにレートが上がっていかないという状況。今回は青パフォ目指して頑張っていきます。
参加します。
— devgenjin77 (@devgenjin77) 2023年11月5日
前回の短期AHCでは、良い結果が出なかったので、今回は青パフォ目標で頑張ります
トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026） - AtCoder https://t.co/v76pvVdg99
今回の結果
なんと542位で終了。。全くスコアが伸びずで、散々な結果になりました。
パフォーマンスは、緑色の真ん中というところ。レートは結局１しか上がりませんでした。。
頑張ったつもりが、緑パフォで終了😩
— devgenjin77 (@devgenjin77) 2023年11月5日
devgenjin77さんのトヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）での成績：542位
パフォーマンス：1043相当
レーティング：1618→1619 (+1) :)
Highestを更新しました！#AtCoder #AHC026 https://t.co/Vy7wO7H9LH
振り返り
最初の方針が悪かったみたいです。。
A問題
方針の概要としては、以下のような感じでした。
#AHC026 お疲れ様でした。
— devgenjin77 (@devgenjin77) 2023年11月5日
得点は1,338,830点。最終結果542位でした。
取り除くべき箱の上に積んでいる箱を他の山に動かす際、移動先の山の転倒数の悪化具合が一番ましな山に動かす貪欲を思いついたのですが、全然スコアが伸びずでした😩 pic.twitter.com/TGX5vYDpac
今回は、10個の山に積まれた箱を番号順に取り出す時、どう動かせば効率良く全て取り出せるかという問題。
最大の操作回数が回ということで、箱の数
に対しては少し大きめかなあという印象。
ふつうにやれば、取り出すべき箱の上のをごっそり他にもってけば良いので、これだけ操作回数が多いのは、まとめて持っていくよりは分割して各山に散らす方針が良いのでは？という感じがしました。
次に、動かすべき箱のかたまりを上から下へ見た時に、単調増加でない箇所があれば、いずれ下にある箱を取り除く時に、上にあるかたまりを動かす必要がでてくるので、最初から分割して運んだらいいのでは？というアイデアが浮かびました。
さらに、動かす先は、できるだけ自分より小さい数が少ない場所が良いだろうということで、かたまりの移動先の山の転倒数を操作前後で比較し、増加具合が一番小さい山を遷移先とすることに。
これで、実装したら結構いい感じになるかと思ってましたが、実際に提出してみると、順位は400の中盤ぐらいという感じで全然大したことが無かったです。。
この後は、前半だけ、かたまりを丸ごと移動させて、後半は単調増加のかたまりに分割して移動するなどの工夫を入れてみましたが、気持ち程度の得点増加にしかならずでした。
最終提出コード
https://atcoder.jp/contests/ahc026/submissions/47306750
感想
最初に選んだ方針がダメすぎたのと、方針転換が全然できなかったのが反省点かと。実装にも結構手間取ったので、色々試す余裕は無かったです。
コンテスト後のTLを見てみると、今回は山毎にソートする方針が強かった模様。が、、理屈がよくわかってないです。
これまでの実績
上がりました。
総括
今回の短期コンテストは、ハズレ方針を引いてしまったなあという感じです。
大変残念な回でしたが、めげてても仕方ないので、また次、勝てるように精進していこうと思います。
ということで、また次回も頑張ります。
