トヨタ自動車プログラミングコンテスト2023#6(AHC026)¶

問題概要¶

最初、1からn(=200)までの番号の付いた箱が、m(=10)個の山に、番号はランダムに、個数は均等に積まれている
以下の操作を最大5000回繰り返す
- まだ運び出されていない箱vを選び、そのvより上に乗っている箱をまとめて山iに動かす。このときコストは「動かした箱の数+1」
  - 山はm個より多くは作ることは出来ない
- 残っている箱のうち一番小さい番号がvであり、箱vが山の一番上にあるとき、運び出せる。このときコストは0
コストをできるだけ小さくなるよう、すべての箱を運び出す操作列を求めよ

一番単純には、取り出したい番号の上の箱をすべてどかして取り出したい
ただ、どかす先をどうするか、まとめてうごかすのか分けるのか1つずつか、取り出したい番号以外の場所を動かすか、動かす先を先に動かしてから動かすか、などいろいろ考えられる
1,356,657(426位)の貪欲
- 取り出したい箱iよりも上の箱の集合をまとめて動かす
- 山の中での番号の最小値が一番大きいところ、に動かす
  - その最小値を動かすタイミングで移動させた箱を動かすことになるので、できるだけそれが遅くなるようにしたいため
1,385,712(165位)の貪欲
- 取り出したい箱iよりも上にある箱の集合について、一番小さい番号の箱までを1塊で考える。その塊の上についても再帰的に考え、複数の塊として考える
- 各塊について、山の中での番号の最小値が一番大きいところ、に移動させる
移動先の選び方で、移動先の山での最小値が一番大きいところでなくても、どちらかというと動かす箱の最小値に一番近いほうが良いなどにすることでさらに改善(kotatsugameさん解, 解説放送)

貪欲解でプレイアウトしてそれを評価値として、各操作で一番よい操作を選ぶ
- 貪欲解ではなくランダム操作(例えば、最小値のひとつ上をランダムに動かすとか)での解とかも考えられる
また、ゲーム木探索の手法で工夫が考えられる
操作は、「移動したい箱iの上にある箱kについて、箱kとその上にある箱をまとめて山jへ動かす」ような感じで一番いいのを探す方法で1.4M点ぐらい出せる
更に拡張として、箱iの上の部分だけでなく他の山にある箱についても考えたいが、その場合、全部は制限時間的に厳しいので、いい感じに調べる箱を枝刈りする

最上位はこの方針だった模様
各山がソートされた状態にできれば、上から順番にコストなしで取り出していける
各山について、それ以外の山に移動させて、ソートした状態で元に戻すように操作
- 基本は、他の山に降順になるように置いて、大きいものから下に戻す
  - もともと降順になっている部分はまとめて動かせる
  - 連番的になっていれば、昇順で置いてまとめて戻す
- ソートしたい20箱に対し、他の山は9山あるので、平均2個ぐらい
  - 最悪戻せないパターンになったとしても、移動先の山がまだソートしてなければそちらのソート時に処理するでもよい
移動するコストのざっくり見積もり
- https://twitter.com/yunix91201367/status/1721110284545532075
- 1山が20箱で、1箱ずつ行って戻ってくるコストが4で、10山分だと見積もると、9200ぐらいは出る
操作回数を減らす工夫
- 取り出せる場合は即取り出す
- 移した後で他の山の箱を合わせて考慮
  - 移した先でソート済みならそれを利用(まとめて移動する、元に戻さない、など)
- 移動先や個数など、ランダム性を入れて山登り/焼きなまし
- 2山以上まとめて考える
- など
https://twitter.com/rsat__m/status/1721107743938084924
https://simanman.hatenablog.com/entry/2023/11/08/183631

見た目的には、ビームサーチが有効そうに見えるが、単純な「現在のスコア」を持ってビームサーチする方針だと結構難しい
- 移動させる箱の塊の作り方や移動先の良し悪しが結構後のターンにならないとわからないし、あまり明確でもない
ビーム幅というか、乱択でも、解候補を大量(数千ぐらい？)に作る感じでカバーなどで改善
山の高さ、転倒数、など

(50位まで&発言を見つけられた方のみ)