はじめに
コンテスト開始2時間前くらいからそわそわしながら待機していました
4時間は長いようで短いので、無理せずバグなく書き上げることを頑張ろうと思っていました
1.問題
1~200まで番号の振られた箱が、10個の山に均等な高さに積まれています
小さい数字の順に取り出すことが目的で、箱は任意の数をそのままの並びで他の山に積み上げることができる
最大で5000回の操作が可能だが、適当に実装しても十分間に合う
コンテスト中
2.~0h30m
1から順に箱を取り出す関係上、まず1より上の箱をどうにかすることを考えました
正の得点を得るために、取り出したい番号より上の箱を、となりの山へそのまま置くことにしました
バグなくACコードを書き上げるだけで、30分経過していました...
とりあえず、初提出して1.22Mの得点を得ました
3.~0h45m
焼いたりすることを考えてみましたが、何も浮かばないため貪欲解を最適化する方向で動きました
初期解では、隣の山へ置くとしましたがこれを工夫します
各山の最小番号を見ると、次にその山を操作したいタイミングがわかります
そこで、各山の最小番号の最大値の山へ移動させることにしました
この提出で1.35Mを得て、順位表を見ると同じ点数の人が大量に並んでいたので、この提出でようやくスタートラインに立ったようでした
4.~2h00m
次の案を考えるために、ここまでの提出でのビジュアライザを見ました
seed=0で、次に3を取り出したい場面です
貪欲解では一つ右の山へすべて積み上げますが、山の中にある9や19,20という小さめの数字の箱が気になりました
全て一括で動かさずに、小さい数字の箱があるときは分割して運ぶことを考えました
動かす候補の集合内の最小値で2分割して（例で言うと、9より上を運んだ後9から下を運ぶ）、各山の最小値の最大値の山へ移動させる処理を書いて提出すると、1.37M
分割数を増やして移動させる処理を書いて、1.38Mまで上がりました
5.~4h00m
上で書いた貪欲解から、別解も考えて試したりしました
・1箱ずつ、各山の最小値の最大値の山へ移動させる ⇒ 微悪化
・移動先の山の選び方に、箱の数も重みづけに加えてみる ⇒ 微悪化
貪欲解から抜けられずに微妙な工夫を加えて、最終得点1.386Mでフィニッシュしました
6.コンテスト中の最終提出
延長戦
終了後に、上位の方々の解法が流れてきて衝撃を受けました
似た方針でより上位の方もいましたが、各山をソートする方針が非常に強いようでした
各山ソート方針で、本番3位相当の得点まで出すことが出来ましたので、やった内容を解説したいと思います
7.最終ビジュアライズ
見た方が内容を理解しやすいと思い、最初に出します
虹色に綺麗な山が積みあがっていく様子が見えて気持ちいいですね
8.貪欲解
最終的には山登りをしますが、ランダム性を加えるだけなので貪欲解から説明します
まず、取り出したい番号の箱がある山を選びます
その山の箱をソートするために、空になるまで箱を他の山へ分けていきます
赤線が、元の山の高さです
一番左や一番右の山を見てわかるように、上に行くにしたがって数字が大きくなるように積み上げます(差が小さい場所へ積んでいく)
右から3番目のように、連番で積めるところは昇順で積みます
ソートする山へ戻す際に2箱一緒に持っていきたいからです
上の状態から、ソートした山を作ったものが下の画像になります
各山の最上位置を見て、大きい数字から元の山へ戻していきます
また、更に下の段を見てより大きい数字&ソート山の最上段より小さい数字な時、一緒にソートする山へ持っていきます
そうすることで、元の山にはなかった数字を巻き込んで帰ってきたり、元の山にあったのに戻らない数字が発生したりします（改善の余地あり？）が、結構高いソートの山を積み上げることができます
ソートした山は、今後移動する必要がないため序盤は高ければ高いほど良いと思っています
また、箱を移動させる毎に各山の最上位置を確認して、取り出せる箱があれば取り出すようにしています
元の山の箱を、他の山へ分けていくフェーズで、置き場所が見つからないことがあります
その時は、一番近い数字の上へ置きました（一緒に運べる期待を込めて
細かい工夫として、山へ箱を戻していく際にすでにソート済みの山を崩してしまうことがあります（無駄な操作
戻す箱を選ぶ際に、完全にソートされた山かどうか判定を行うことで、小さい数字の箱を無駄に運んでしまう操作をなくしています（上から昇順かを愚直に書いています
9.山登り解
貪欲解ではどの山をソートするかを選ぶ際に、取り出したい番号の箱がある山を選んでいましたが、ここにランダム性を加えました
ソートする山を選ぶ際に、60%で貪欲解を、40%でM個の山からランダムに選ぶことを繰り返します（確率はseed=0で試しての適当な値です
最も良いスコアの回答を保存しておき、1.8秒経過したら打ち切り出力します
pypy3で書きましたが、大体4000回以上は回りました
10.延長戦提出コード
おわりに
コンテスト中は、良い解が出せずにちょっと悲しい感じでしたが、延長戦で新しい知見も得られて結果的にはかなり楽しめました
この記事が参考になる方がいれば幸いです
2回以内で黄色になることを目標に引き続き頑張ります
