トヨタ自動車プログラミングコンテスト2023#6（AHC026）に参加しました。
問題名はStack of Boxes。積み上げた箱を移動しながら順番に取り出す問題でした。
結果は提出789人中13位。
短期の最高順位を大幅更新でとても嬉しい。
問題
200個の箱が10の山に分かれているよ。
ある箱を移動するときは上の箱ごと動かすよ。このとき箱の数+1のコストがかかるよ。
一番上にある箱は取り出せるよ。
なるべく小さいコストで、小さい番号の箱から順に取り出してね。
考察
複数の山を並べて、小さいものから順に除外して。ソリティア？
いや、階段を作るわけでもないし、妥当でない盤面を経由するので雰囲気が似ているだけか。ソリティアの知見は使いづらそう。*1
それよりも、各山内の大小関係だけ保てていれば順番に取り出せる。トヨタコン頻出のヒープかな。
実行例を見ると、取り出す箱より上を全部除けて箱を取り出すの繰り返し。箱をどう除けるかを改善すれば、とりあえずスコアは伸びるかな？適当な貪欲を組んで、どういう方針が良いか探るところからか。
あとは本番中のメモをそのまま掲載。
動かした箱の個数＋１の体力を消費
・動かす箱の個数を減らしたい
・動かす回数を減らしたい（１個２回は２個１回より重い）
・動かした箱の再移動を減らしたい
→箱の最小値が一番大きい山に動かす
・転倒数が減るよう移動する
→箱を数回に分けて動かす
→次に使う箱は別の山へ
動かすルール
・上からチェックする
・各列の最小値より小さいものが出たら、それだけを別の列に退避する
（それより上を予定移動列に移動、それを任意の列[最小値が最小の列]に移動）
・最後まで見終わったら、残りを何回かに分けて移動する
・最大値を一番下にする？最小値を一番上にする？
実装
まずは実行例と同じ方針で、動かす先の山だけ変えてみる。
箱の数を平均化する方針はどうかな。
→1,319,252点。これより上に同点数集団があり、もっと良い方針がありそう。
転倒数は減らしたいけどそれより目先を追って、直近使いそうな箱を塞がないことが大事か？最後まで使わない山、つまり最小値が大きい山にどかす。
→1,356,657点。同点数集団のほぼ最高帯（47位タイくらい*2）。強豪の面々もここにおり、良い方針を引いたっぽい。
全ての箱を一度に動かす必要は無い。基本方針はこのまま、複数回に分けて動かすことを考える。
ヒープもどき、かつ小さい箱から取り出すルールなので、「各山の上N枚が最小値からでソート済み」な状態が良い状態と見定める。下側や大きい数の転倒数はそんなに気にしてもしょうがない。
箱を除けるときに、ある箱を単独で任意の山*3に移動して良い状態を作れる/保てるならそうしてみる。それ以外の箱は変わらず、最後まで使わない山へ移動。
単独移動の候補山が複数ある場合、少し試した感じだと山の最小値を下回らない範囲で最小値が最小の山に動かすのが良かった。6 Nimmt!はマラソンの役に立つ。
→1,393,545点。11位。バグ取って1,399,894点。うへへ。
大量移動する側を効率化することを考える。例えば半々で2回に分けて移動すれば、上半分と下半分を交換できる。これは試した感じ、移動する中の最小値を一番上に持ってくるのが良かった。ただ1個だけ移動するのは若干筋が悪く、許容する移動個数の下限を増やしていくとスコアもじわ伸び。
→1,400,609点。大台突破。
もうルールベースで出来ることはやりきったか？シミュレーションして良い分割位置を探す。シミュレーションでは爆発防止のため分割移動しない。実スコアで評価したが、これも分割しすぎにペナを入れた方が良さそう。
→1,406,616点まで。瞬間風速6位。
残り1時間。ここからビームサーチを試みるも良い結果が出ず、13位で終了。
他の人の考察を見て
ソリティアよりはハノイの塔らしい。確かにそっちの方がまだ解法を流用できそう。窮屈さが全然違う＆最小を除外できるので、やっぱり流用する意味は薄い気がするけど。
最上位帯を見ると、完全にソートしてしまうらしい。
1山を9山に分けて戻して。コストは平均2個ずつ移動するのに3*10、戻すと20個+9回で29、これを10山で(3*10+20+9)*10で590ペナの9410点、150ケースで1,411,500点（本番6位相当）の計算。
上下の大小関係は50%なので、一度に動かせる期待値が約2個という感じか。もうちょっと少なそう？*4
なるほどなぁ。これは確かに強いし、方針を決める時点で高得点が見える。
ただ実際はどうソートするの？とか、それでもソートしきれなかったらどうするの？といった部分を詰める必要があり、それを本番で仕上げきった人達の強さもあると思う。
私は短期コンではこういう駄目だったときにリカバリが難しい方針には手を出さないのだけど、検討自体投げ捨てちゃったので計算まではしても良かったかなと思った。回数側のペナルティが膨れて筋が悪そうと間違っていたので。
一方非ソート勢の中ではかなり良い順位。差別化できた点は、箱を除ける際に小さい箱を別の山に退避する、をルールベースで書けたところかな。ここはヒープ(ソート)と問題の性質を意識したことで良い状態を導き出し、ルールベースで十分良い結果が出るという答えに辿り着けたと思う。*5
感想
自分が得意とする、自明（そう）の中から答えを探し出すという勝ち方を綺麗に出来た。ビームまでは撃ち切れなかったけど。
摂動を入れて焼く、もよく見かけるけど地味にやったことが無いのでいつかやってみたい。
実装苦手マンが中盤で1ページ目に入ったことと最高スコアで30msという実行速度からルールベースがバレるかと思ったけど、案外大丈夫だった。WJの長さでカモフラージュ出来た？
