AHC026参加記（67位）
先日、トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）に参加し、67位を獲得しました。
下図は67位を獲得した提出のseed=0000のビジュアライザ、獲得点数は9354でした。
点数推移と各提出の解法概要
- 1,319,800(本番615位相当) 1から順に目的の箱の上の箱を一番低い山に置く貪欲。
- 1,329,478(本番574位相当) 番兵として各山の底に9999番の箱があるとした（番兵）。上の箱を運ぶときに、移動する箱の底と移動先の一番上の箱の値が昇順になるようにする。不可能なら差の絶対値を小さくする。
- 1,343,061(本番524位相当) 番兵として各山の底に201番の箱があるとする。これまでまとめて移動してきた箱を小分けに移動する。移動する箱は上から昇順に並んでいるならまとめて移動する。移動先は、できるだけ差が小さく昇順にできるような場所に移動する。
- （参考）1,356,657 (本番426位相当) 箱はまとめて移動する、移動先は最小値が最大の山にする。（この点数集団が結構多いようです）
- 1,375,649(本番273位相当) 3の解法で、昇順に並んだ箱をまとめて移動する部分に制約をつける。昇順でも差が15より大きい場合は分割する。
- 1,387,723(本番139位相当) 条件を加える。移動先に箱を置くときに、基本は昇順に並ぶことを優先するが、差が大きくなりすぎる場合は、降順に並ぶことを許容する。
- 1,389,848(本番117位相当) 条件を加える。移動先に箱を置くときに、基本は昇順に並ぶことを優先するが、差が大きくなりすぎる場合は、降順に並ぶことを許容する（6で漏れていた部分を改修）。
- 1,396,055(本番67位) 序盤で箱の移動をするとき、一時的に高さが低くなる山があれば、すべて取り出して他の山に移動する。空いた山にはできるだけ大きい箱を底に敷く。
考察
序盤
コンテスト中どのような考察をしたのかを解説します。 はじめは、細切れに箱を移動するほうが最終的なコストが大きくなりそうなので、提出1の解法をベースに箱をまとめて移動することを考えました。提出1から提出2にかけて、まとめて箱を移動する効率的な方法を考察しましたが、値の大きい箱は順番に箱を取り出す過程で各山をたらい回しされることになります。そのため、提出2を終えた段階で小分けに箱を動かす手法に切り替えました。まとめて移動する手法では、参考に書いた4の手法がかなり良い点数だと思いますが、これ以上スコアを上げるには一筋縄ではいかなそうです。
中盤
提出3~8にかけては、基本的な考え方は同じで改良を重ねました。箱を小分けに移動しますが、移動先でどうなっていてほしいかを考えます。序盤の提出ではまとめて箱を移動していましたが、これはあまりよくありませんでした。箱の値がバラバラのまま移動しても、値の大きい箱は再び避ける必要があり移動コストがかかってしまいます。特に値の大きい箱が山の上の方にあると何度も山を移動することになります。なのでできるだけ移動先で昇順に並べて箱の移動コストを削減します。この考察に至ると各山をソートしたくなってきますが、この時自分は厳密にソートするとコストが結構かかるのではないかとよく考えずに切り捨ててしまいました*1。
上図は序盤の様子です。箱の移動はできるだけ昇順に並ぶように移動することを考えます。一回目の移動では37の箱を移動していますが、昇順に並べることだけを考えると87の上になるはずですが、箱の値の差がかなり大きいのであまり嬉しくありません。箱の値の差が一定以上*2の場合は、降順に並ぶことも許容すると図のように19の上に移動することになります。降順を許容することで、できるだけ長く昇順に並ぶ可能性が高くなります。昇順に並んでいる箱を移動する必要が出てきたとき、その部分を丸ごと移すことで移動コストが削減できて、対象の箱を運び出す時も上に避けなくてはならない箱がたくさん並んでいる確率を減らすことができます。
この操作を繰り返していくと上図のようになります。これは12個目の箱を取り出そうとしているところを切り出したものになります。この時点ですでに左右の山の上部が綺麗にグラデーションになっており、昇順に並んでいることがわかります。
終盤
今回の解法の一番重要な部分はここまでで後は各パラメータの調整と細かな工夫を入れていきました。その後の考察は、ビジュアライザを観察し続けて試行錯誤しました。例えば、上図を見ていると中央の高い山の上部に200番周辺の最終盤に取り出したい箱が集まっています。その右横には5個しか箱の積まれていない山があります。途中で低くなった山からはすべて取り出してしまって、他の山から大きめの値の箱を持ってくることができれば改善が見込めそうです。後半1時間はこのような感じで、今より1でもスコアが上がれ！と思って実装をしていました。
感想
今回は今まで戦えるスコアになったことがなかった短期のAHCで100位以内に入り、入青することができました。 これまでの傾向からすると、短期長期ともに貪欲解が使えるときに比較的いいパフォーマンスを出している気がします。 まだ長期の方では、黄パフォを取ったことがないのでそこを目指しつつ、当分はレート2000黄色を目指して精進します。
