# AHC033 2024/05/17 19:00 ～ 05/27 19:00

https://atcoder.jp/contests/ahc033/
「Container Handling with Cranes」

## 心がけ
休日はゴリゴリ実装する。
込み入った考察はちゃんと点数を取った後。
メジャーケースで通用する方針を。(コーナーケースばかり考えない)
なんだかんだ次元を落とすほうが強い(斜めが使えても縦横だけにする、など)
DFSを忘れない(制約厳しい系、乱択BFSが有効。)
特殊制約下での下界を考える。
インタラクティブはちゃんと1手1手で得られる情報を使うことを重視。(全体でぼんやり考えない)
状態に着目する。リクエストに着目と、盤面状態に着目、どちらも。

## 問題をみて
シンプルなgrid問題なので、ちゃんと探索を詰める。
ゴリゴリ実装、ミリミリデバッグ。
高速化よりも、強い貪欲。

## 1日目(金)
### ルール
コンテナをクレーンで運ぶ問題

■ルール
5x5マスなので、マス目自体は少なめ。
25個のコンテナを5台のクレーンを操作して、指定された順番で搬出する。
左端の列が搬入口、事前に運び込まれる順番が決まっている。
右端の列が搬出口、置くと搬出される。搬出口の行で搬出できる番号のコンテナが異なる。
各マスは1つだけコンテナを置いておける。

クレーンは2種類、クレーン同士は同居できない。すれ違えない(同時に移動/爆破は可能)。
- (0,0)のクレーンは大型。コンテナが置いてあるマスも無視して移動できる。
- それ以外は小型。コンテナが置かれたマスは、コンテナを掴んでいると移動できない。

クレーンは同時に操作し、ターン毎に以下の操作をできる。
- **P**：現在位置に存在するコンテナを掴む。すでにコンテナを掴んでいる場合や、現在位置にコンテナが存在しない場合は**WA**となる。
- **Q**：掴んでいるコンテナを離し、現在位置に配置する。コンテナを掴んでいない場合や、現在位置に既にコンテナが存在する場合は**WA**となる。
- **U, D, L, R**：上下左右に隣接するマスへ移動する。小クレーンかつコンテナを掴んでいる状態の場合は、移動先のマスにコンテナが存在してはならない。N×N マスの外へ移動するような操作を行うことは出来ない。
- **.**：何もせずにその場に留まる。
- **B**：クレーンを爆破する。コンテナを掴んでいる状態では爆破することは出来ない。爆破したクレーンは盤面から排除され、以後 . 以外の操作をすることは出来ない。

各ターンは以下の3ステップからなる。

1. 運び込まれてくるコンテナがまだ残っている各搬入口について、そのマスにコンテナ及びコンテナを掴んだ状態のクレーンが存在しない場合、次の順番のコンテナがそのマスに配置される。
2. 各クレーンの操作を行う。
3. 各搬出口について、そのマスにコンテナが配置されている場合、そのコンテナを搬出して盤面から取り除く。

できるだけ、短いターン数で指定された順番に近い順にコンテナを搬出する。

■スコア
低ければ低いほど良い。
- M1：正しい搬出口から搬出したコンテナの転倒数の総和
- M2：間違った搬出口から搬出したコンテナの総数
- M3：搬出されなかったコンテナの総数

Score = ターン数 + M1x10^2^ + M2x10^4^ + M3x10^6^

基本的にM1,M2,M3は全て0にした方が良さそう。
そうすると、小型クレーンいるか？爆破があるのはそのためか。

■その他
実行時間が3s。割と探索しきれちゃうのもありそうだもんな。
入力生成方法がランダムシャッフルして5個ずつにするとのこと。
なので各搬入口から5個ずつ出てくる。

### 所感
condingameっぽい。操作可能なものが複数あることにより、単純な探索だと爆発する。
こういうのは、各駒毎に貪欲出して調整するのが王道だけど、盤面が狭く互いの干渉が強め。
ターン進行による状態変化が大きいので焼くのも厳しい系。
あー、これソリティアか。

各搬出口毎に出せる順番が決まっている。なるべく早く消化しきれる搬入口のものを優先して展開して、他は止めて置きたい。
クレーンが干渉するので、バケツリレーをしたくなるが、掴んで下ろすのにそれぞれターンを消費するのでよく無さそう。ルートを固定してグルグル回るのが強いはず。

ただ、そうなると大型クレーンをどう使うんだ？ルート上にコンテナを置いても通れるくらいの強み？
あー、搬入口の列で上下に移動して搬入されるコンテナをコントロールできるかも。
コンテナを掴んでいると搬入されないが、大型クレーンは掴んだ状態ですでに搬入されたコンテナ上に移動ができる。移動によって空いたマスは搬入がされる。
小型クレーンが運び出すと同時にコンテナを掴んだ大型クレーンが移動すると、搬入させないようにできる。
いや、大型クレーンが搬入列(x=0)から、ひとつ進んだ列(x=1)に取り出して上げて、小型クレーンが搬出まで持っていくのがいいかも。小型クレーンが左右移動で済む。
うーん、バケツリレーは避けたい。あー、大型クレーンは配置されたコンテナを無視できるので、盤面によっては担当時の必要搬出ターンが小型クレーンより少なくて済む。

ターン序盤が一番複雑で、終盤はただ詰めるだけになる問題。

以前のHTTF「カードの回収」と似ているのでは？
https://atcoder.jp/contests/future-contest-2021-qual/tasks
→コンテナを取る順番と置く場所を同時に焼きなましする。
→駒が複数あるので、合わなそう。

■理論値
愚直にコンテナを運び出すだけ。同時に5クレーンを動かせるので1行だけ考えればよい。
搬入口で掴んで+1、4マス移動して+4、搬出口で下ろす+1 を5回。 = 6x5=30
搬出口から搬入口に戻るために5マス移動する+4 を4回。 = 4x4=16
合計：46ターン
Score=46、が最小値。

フル稼働して46ターンなので、クレーン個別のアクション数は46x5=230回。
コンテナが25個なので、ひとつあたり平均9.2回が必要回数。

■行動について
1ターン待機はよいが、2ターン待機はバケツリレーと同値になるので避けるべき。
出入り口はゴチャつく、特に出口側は指定があるので、その手前(X=3)はなるべく空けておきたい。

### 方針
強い貪欲を作って、搬出順序を変えながらやる感じかな。
最後搬出のボトルネックになる(最終ターンになる)コンテナから、優先度を変える感じで。
優先度は、単純に順序と、対象のコンテナの搬出口付近のコンテナ置きに依存する？

盤面の評価は、残りの必要ターンで出せそう。
盤面を1手毎に進めるのを探索するのは無駄が多い。
クレーンに対して目的を与え、その目的の解消までを評価するのが良さそう。★
目的を与えた時点でスナップショットを取って、探索の起点にするのがよい。★
→MCTS的なデータ構造でやるのがいいのでは。

目的の解消まで数ターン程度なので、ターン毎に盤面を持っておいて、
ターンを進めながらリボルビングしていくのがメモリ効率よいのでは？

大型クレーンは超えられるので、搬出口の目の前にコンテナを置いても飛び越えられる。★
→大型クレーンじゃなくても、2台のクレーンで共同でやると目の前のコンテナがあっても抜き出せる。

コンテナを一時的に置くときのパターンはちょっと多い。
→盤面がキレイになった時点でスナップショットをメモしておき、より早いものがあればそれを採用。

保留は、基本奇数行の2,3列の6マスが良さそう。帰りは保留コンテナ無視できるので、ルートは詰まらない。
stockが捌けた行の搬入口は好きに置ける。

### 実装
バッチ処理、done。暗黙パラメータなどがなくて楽。
各搬出口に対して、待ちがなくなる(先頭4つのコンテナを搬出完了)までの目安ターンを出す。
ターンが短いものから順に消化する。
ルールベースで愚直解を作る。
保留が難しい、とりあえず誤っても搬出してしまおう。

色々とバグる。ミリミリデバッグ。

**TODO**
~~バッチ処理~~
愚直解出力
順番厳守解
スコア計算(ベストを保存する機構)
最楽ケース(先頭から順に並んでいる)と最難ケース(逆順に並んでいる)の挙動確認
貪欲解の強化
　評価関数化
　　搬出可能数や盤面を評価
　目安ターンの精度向上
　移動の厳密化
　移動の効率化
　保留の高度化
探索可能にする

## 2日目(土)
### 実装
バグ取り続き。最後まで回った。81ターン。

今は掴んだものは搬出しちゃうので、保留を考える。
適当評価関数で保留を決定した。
seed=0 122turn

seed=1 NG バグでいきなりクレーン4台爆破されてしまった。。。

明らかな待ち状態とかを回避するルールを入れて、大体110turn前後で、8割くらい出せるようになってきた。
seed=9 95turn

大型クレーンがあるので、上下のどちらかに固めて保留しておく手もあるか？
上下ともに詰めても行きが一方通行で上手くいくはず。
もっと詰めてこうとか。

細かい衝突を色々ルールベースで頑張っているが、不毛になってきた。
評価関数の貪欲に切り替える。

実装しておくところやっておく。スコア計算と特殊ケースdone。

ルールベースをミリミリデバッグしてたら100ケース通った。Ave104turn。
投げてみる。33.6G。WAないので全部搬出仕切った状態。
満点から0.672%。Ave 104turnなので、Ave 70turnくらいにする感じか。

**TODO**
~~愚直解出力~~
~~順番厳守解~~
~~スコア計算(ベストを保存する機構)~~
~~最楽ケース(先頭から順に並んでいる)と最難ケース(逆順に並んでいる)の挙動確認~~
貪欲解の強化
　評価関数化
　　搬出可能数や盤面を評価
　目安ターンの精度向上
　移動の厳密化
　搬出を見越したpick
　移動の効率化
　保留の高度化
探索可能にする

## 3日目(日)
### 考察
待てよ、トヨタのコンテストでchokudaiさん直々の作問なんだから、ジャスト・イン・タイムがコンセプトなのでは？つまりバケツリレーが大事。
実際、搬入から搬出までを一気にやる時、クレーン移動が特に搬出口で詰まりがち。
搬出口は常に空くので、搬出口列を上下移動するクレーンが1,2台あればよいのでは。
搬入側は常にコンテナで埋まるので搬入後の整理が大事。小ロット生産のカンバン方式っぽさある。

搬出口列、置かなければ搬出されないのでクレーンで持っておくと搬出口列で待機できる。
→取り出せない所を掘れる。

搬入から搬出までの通路確保はしないでいいかも。
大型クレーンで越せるし、何より早くコンテナを展開するのが短縮のカギそう。

バケツリレー、搬入・搬出の二段階と、搬入・整理・搬出の三段階も考えられる。
流れとしては

1. 皆で搬入してコンテナを展開。
2. 少量の搬出できるものから搬出、スペースの空きがない(整理が重要そう)。
3. 色々と搬出できるため効率的に搬出していく。

搬入→整理→搬出、と徐々に仕事をシフトしていくのが良さそう。

搬入口、1,2,3行目のどれかでも搬入仕切ると、1列目まで展開できてよい。
0,4行目は効果が薄い。

コンテナの展開は搬出口の行から左に搬出順で並べたい。→左右だけの往復で搬出できる。前を搬出したら自ずと次の搬出が可能になる。
→クレーン移動の制約が厳しいので、キレイに整理するのは有効そう。

何処か１つの搬出口をやり切るより、並行して進められると良い。搬出口ひとつの効率に限界があるので。逆に搬入側は、上下端を除きひとつの搬入口を捌き切った方が良い。
→探索で自然とそうなりそう。

探索はビームサーチというか、ひとつのqueに突っ込んでデカくなったらスリム化する感じ？
順序は残りの目安ターンで決めるとよさそう。盤面の進捗ではなく、可能性を追求できる。
→解なしの回避は検討
→目安ターン、ひとつのクレーンで効率的に運んだ時の必要ターンを5で割るとか？

### 実装
評価関数化やっていく。まずは理想ケースで46ターンを出せるように。(保留不要)
同一盤面判定として、小型クレーンを区別しない方がよいか？
→クレーンの配置がそもそもパターン多い。コンテナ状況と残り最低ターン数で切るのがよいか？

搬入搬出はindexだけ覚えておけば、コンテナ番号は逆引きできる。★
出力は親に遡って繋げるか。
評価時、コンテナは同じ搬出口の番号の早いコンテナは無くなったものとして考えてよい。
大型クレーンがpickしたコンテナはgrid上で重複が可能。grid評価とは別に、大型クレーン分だけ追加評価。
→違う、大型クレーンも最後下ろす所までを合わせてアクション設定する。
アクションの単位は何かをpickして、どこかで下ろすまで。
アクションが解消するまで盤面シミュレートしたらよい。
pickまでと、下ろすまではアクション分けるか？→分けたくない。
どこかに待機してpick、待機したあと下ろす、がある。待機まで貪欲で上手く再現する。

クレーン起点でアクションを決めるのではなく、コンテナ毎に自身を運ばせる感覚。★→状態に着目
盤面に出たコンテナと大型クレーンの持つコンテナが起点。(搬入前は考慮しない)
コンテナ毎に誰に運ばせるかで選択肢、あまりに時間がかかるやつは除外する。(pickまで10ターンとか)

セットされたアクションによって発生する先の盤面を持っておく。
→先のシミュレートと合わせてアクションの評価をできる。
~~→探索の単位はアクションの設定毎だが、盤面シミュレートは継続してもっておくべき。~~
→盤面を個別で持つより、高速シミュレートを都度する方が早いか。
→シミュレート後のコンテナを起点にアクションを設定すると無駄がない。★

アクション同士の衝突が起きたらどうするか？
→先にセットされたアクションを優先。WAITして解消するまで待機。しなければアクションを対象外に。
→どのアクションでも先のアクションを阻害してしまうなら、回避アクションを入れる。
　どこどこに移動する、など。
→回避もできない時は爆破。
→こうすると、自然と搬入と搬出で役割分担しそう。

コンテナの搬入から搬出までの最短距離は明らかなので、ロスを計算できる。
→コンテナのロスを下げるためにクレーンのロスを上げることになるので微妙そう。
→保留場所の評価としてはいい。★

4近傍探索について、場外判定を都度やるのがもったいないので埋め込む。★
埋め込む時、横移動を優先して縦移動を次点、しかも中央に寄るのを優先したら良さそう。

最後がターンなので、ターンに帰着させたい。
→アクション回数？

高速化関連
・諸々の参照値を事前準備しておく。
→した。
・初動変に色んなクレーンに運ばせることはない。自身の真上のクレーンにさせる。

**TODO**
貪欲解の強化
　評価関数化
　　搬出可能数や盤面を評価
　　アクションとシミュレート
　目安ターンの精度向上
　~~移動判定の厳密化~~
　搬出を見越したpick
　移動の効率化
　保留の高度化
　アクションの高度化
　　二組じゃないとできないこと
　　搬出の待機
　　保留の待機
高速化関連
　4近傍の埋込み
探索可能にする
　解なし回避

## 4日目(月)
### 実装
理想ケース(搬出順に搬入)は動くようになった。
が、
- 出力機構が整っていない。Node毎にどこからどこまでを出力に含めるべきかが不明
- pickしてそのまま搬出しちゃう。保留ができない。
- 移動が厳密ではない。動くはずの前のクレーンが止まると狂う。

## 5日目(火)
### 考察
同一盤面削除はやはりいまいちかも。クレーンの場所大事。でも考慮するとパターン多すぎ。
→最序盤は同一盤面が発生しがちなので、そこを絞るだけでもやった方がいい。★

その分、コンテナ毎の最短搬出ができたとした時にかかる最低ターンを出して足切りにするのと、
具体何stepの操作が必要かで、クレーン台数で割って理想の動きでかかるターンを出せる。
→搬出後に戻るstepも考慮できるはず。搬出口の数と搬入口の数を対応させれば良い。
→もっと単純に搬出口から搬入口までの横移動だけが理想stepとして良さそう。
→grid場に保留した荷物も同様に、取りに戻るのは横移動だけを考慮。

これだけターンを詰める問題なら、loss数が同じNodeを固めたビームを作って、
lossの少ないビームから消化していくアプローチがかなり効きそう。★
lossは単調増加なので、ターンが進むほどlossが増えてしまったものが次のビームに脱落していく。
今のpick2dropの流れなら、荷物単位のstep消費も容易。(actionの完了次点でlossを記録)

### 実装
少しずつケースの難度を上げていく。
移動で避けられないので、ここで固まる。actionがなくなったクレーンは爆破するか？
爆破するようにした。
が、以下の問題で固まる。
- 移動が厳密ではない。動くはずの前のクレーンが止まると狂う。

目的地までの距離に、時間の概念を入れる。
→このターンはクレーンがいて通れない、など。waitの概念を入れる。
　何度もシミュレートしているので、一度通った所を覚えておけば良い。
→うーんbitで持つと、自分と他人の区別を付けられない。
　クレーン毎ターン毎にbitで持つか。座標持つより容量食わないし、or演算でcheckも容易。
→1ターン毎の移動計算なので、距離が1である事が保証されている。
　一時停止時は、距離を停止分だけ伸ばして上げれば良い。

これ目的地起点のいつもの距離計算じゃダメ。クレーン起点で目的にたどり着くようにする。
→ちょっと面倒だった。クレーン起点で道を出したあと、道順復元でいけた。
まだベストの動きではないが、これは貪欲だからだろう。
すれ違いとコンテナ変化に対応しないと。

んー、でも搬出が早いアクションを優先したいな。評価関数確認しよう。

あれ、最後終了タイミングがズレるとき、出力できないかも。。。
最後のnodeだけ特殊で、欠けありの出力にする。

## 6日目(水)
### 実装
出力機構を修正し、盤面評価を修正することで意図した動きになった。

次、保留不要だが、搬出行に対して搬入列の順番を入れ替えたケースを通す。
１列いけた。ロス無し。
うーん、ターンが進むと世界線が変わって、同時に異なる場所に存在する事になってしまう。
なるほど、搬出した後、盤面からいないことにしてたら、こういう時に矛盾が生まれるっぽい。
搬出後は搬入口に戻るようにする。

高速化として、一度動きを出しているので再度移動のシミュレートする必要は薄いはず。
前回の記録が残っていれば流用する。★

## 7日目(木)
あまりにも腹痛が酷くて病院に。胃の辺りから出血してるかも？お粥生活になった。
### 実装

搬出後も存在を維持するようにした。搬出後は搬入口に走るようにした。
まだ未来の存在がダブる。どうも先に決まった動きに対して、後から障害になるような指定によって起こる。
別クレーンを妨害するようなルートは取れないようにする。
→あー、pick/put 操作で待機するから、辿り着いた次のターンの存在が許されるかをcheckしないといけない。
デバッグ要にNodeに対してIDをつけよう→付けた。
搬入口まで戻ったら簡単のため盤面から除外する。

おー！いったー！かわいい。ただ、これはまだ最短じゃないな。

全探索したら出ないかなと思ったが、out of memory。
適当にまわして59turnになった。こんなもんかな？
→途中最後バケツリレーするとまだ縮まりそう。やはり保留加えないと完成しないか。
→ちなみに、1投目のやつだと77turnだった。妥当な割合そう。

## 8日目(金)
お粥あきる。。。紅茶も飲めないの辛いなぁ。
### 実装
次、保留が必須のパターンをする。先のパターンの1行目を入れ替えただけ。
適当に空きますに保留するようにしたら、ちゃんと動いた。
エラーが出るので潰しこむ。
→あー、Nodeのターンの開始時からしか移動履歴を持っていないから、初手すれ違いが発生するとダメそう。
→一つ前の位置から保持することにした。

格納後に消えない。最後の出力調整時に変えるか。
変えた。最後までいった。62turn。→60turnも見つかった。
→ちなみに、1投目のやつだと83turnだった。お、かなり短縮効く。

比較的簡単なseed=9で動くようにする。
→こういうのが解消できないので、pick対象とするものは目的地まで道が通ることを確認。

できた。79 turn。

seed=0,seed=1 などは解を見つけられない。
評価関数周りを整えていく。
整えた。seed=0が86 turn。おー！
評価関数いじって、seed=0が78 turn。おー！

seed=0～9は解は出る。
時間が5sくらい要するので、そもそものベース速度を上げる必要がある。
すでにちょっと使ってるし、gridの1次元化やるか。
→やった。単純に置き換えただけで倍は早くなった。
→1次元化によってもっと絞れるところはありそう。

あ、seed=1はエラー出てる。コンテナ変化考慮ができてなさそう。
なおした。

大体3秒ちょいでこんくらい。
> 0=0.98 s= 80 T=3844
1=1.00 s= 77 T=4159
2=0.98 s= 81 T=2862
3=1.00 s= 80 T=3410
4=0.96 s= 80 T=3453
5=0.96 s= 83 T=3751
6=0.98 s= 87 T=5090
7=0.99 s= 75 T=4025
8=0.99 s= 75 T=3070
9=0.99 s= 78 T=4075
TSum=796.0
Ave=79.6

時間10倍(30秒こえ)でこんくらい
> 0=1.00 s= 78 T=43847
1=1.00 s= 76 T=32146
2=0.99 s= 80 T=30617
3=1.00 s= 76 T=39822
4=1.00 s= 76 T=35132
5=0.98 s= 82 T=34670
6=1.00 s= 84 T=42759
7=0.99 s= 75 T=40140
8=0.99 s= 75 T=33246
9=1.00 s= 77 T=41013
TSum=779.0
Ave=77.9

移動履歴をまとめて更新するようにすると、スコアが下がった。
更新漏れがありそう。

> 0=0.98 s= 80 T=4812
1=0.99 s= 77 T=4198
2=0.98 s= 81 T=2911
3=0.94 s= 80 T=3406
4=0.94 s= 80 T=3495
5=0.94 s= 83 T=3883
6=0.97 s= 87 T=5188
7=0.99 s= 75 T=4209
8=0.99 s= 75 T=3204
9=0.99 s= 78 T=4275
TSum=796.0
Ave=79.6

バグ取れたと思う。
長回しも2倍は早くできた。
> 0=1.00 s= 78 T=22685
1=1.00 s= 76 T=16705
2=0.99 s= 80 T=16209
3=0.99 s= 76 T=19689
4=0.99 s= 76 T=18027
5=0.95 s= 82 T=17699
6=1.00 s= 84 T=21559
7=0.99 s= 75 T=18599
8=0.99 s= 75 T=16845
9=1.00 s= 77 T=19164
TSum=779.0
Ave=77.9

同一盤面除去をしたい。
雑にactionを実施後の盤面でいいか。
雑にやったが割といいやん
> 0=0.96 s= 81 T=3573
1=1.00 s= 75 T=2845
2=0.99 s= 80 T=2112
3=0.99 s= 76 T=2790
4=0.97 s= 77 T=2411
5=0.95 s= 82 T=2625
6=1.00 s= 82 T=3542
7=1.00 s= 73 T=2704
8=0.99 s= 75 T=3112
9=1.00 s= 77 T=2731
TSum=778.0
Ave=77.8

長回し、ちゃんと上がってる。
> 0=1.00 s= 77 T=21517
1=1.00 s= 75 T=23266
2=0.99 s= 80 T=22345
3=1.00 s= 74 T=25436
4=0.97 s= 77 T=23752
5=0.95 s= 82 T=21880
6=1.00 s= 78 T=23965
7=1.00 s= 73 T=26629
8=0.99 s= 75 T=22095
9=1.00 s= 76 T=27367
TSum=767.0
Ave=76.7
RAve=0.9899412152887763

うーん、topは手元bestからさらに平均7ターン削ってるな。。。

大型クレーンだけ、搬出できるものも途中保留してもいいかも。
→10ターンくらい下がった。やはりムダは良くない。

特別な動きと言うよりは、まだ探索が足りてない印象。
loss毎ビームの実装をするか。
chokudaiサーチでやるのが、足切りターンも分かって良さそう。★

初期の保留がイマイチかも。
コンテナによって配置位置の優先度を決めてしまう。
最初は決め打ちでいいのでは？無駄にパターン数増える。★
→事前に初期盤面からの順番の効率を見て、パターンを決め打つ。
→初期盤面自体は構築順序がほぼ決まる。
→初手足元のを動かすなら自分で拾う。
→最初の搬入を取るのは、初手を取らない最寄のやつ。
→保留場所、優先度の低さから順番に埋まって行き、後で具体の配置決めたい。
→何処を空けるかも後決めできる
→そもそも配置パターンをいくつか決めておいて同時並行で評価がいいかも。パターンに応じたすべての保留場所を指定する。★

残りコンテナ数が5個になった時点で、終了ターンの算出、足切りが出来る。

高速化ネタ
・grid上のものを動かす時は、必ず距離が縮む方向に動かす制限を入れる。

**TODO**
貪欲解の強化
　評価関数化
　　搬出可能数や盤面を評価(途中)
　　~~アクションとシミュレート~~ ←搬出と保留ができたのでOK
　目安ターンの精度向上
　移動判定の厳密化
　　~~未来の動きを考慮した動きの作成~~
　　~~すれ違いの考慮~~
　　~~搬出待機の反映~~
　　~~搬出後も存在する事を表現~~
　　~~gird上のコンテナ変化の考慮~~
　~~搬出を見越したpick~~
　移動の効率化
　　~~前回移動の流用~~
　保留の高度化
　アクションの高度化
　　二組じゃないとできないこと
　　搬出の待機
　　保留の待機
高速化関連
　~~1次元化~~
　1次元化によってさらに高速化できる所の対応
　　~~通路判定の事前実施~~　←もう少し詰めれそうだが。。。
　~~4近傍の埋込み~~
探索可能にする
　~~残り必要手数が少ないものから実施~~
　loss毎にビーム

## 9日目(土)
妻のお粥作りが上手で生き延びてる。
### 実装
初手足元のを動かすなら自分で拾うようにした。→スコアは変わらない
　→100ケースだと微悪化している。
　seed=33が71→73turn、ただ、初動盤面は全く同じ。
　→実行時間倍にしたら枝刈りした方が71→70turnによくなった。採用。
100ケース回したら3ケース落ちた
seed=53,56,80 →全て長回しで解が見つかった。探索不足。

初動のコンテナの配置を限定する
→あんまり良くならなそう。計算対象は絞れているっぽいが。(先の落ちるケースも拾える)
真ん中は基本的に使えないようにする
→これも確実によくなるわけでは無さそう。
全部入れ：77.65、真ん中含め固定空け：76.75、素のまま：解無しが出る、

ちゃんと前に進む改善をしよう。loss毎のchokudaiサーチする。
まずは雑に搬出数に応じたchokudaiサーチをするか。
した。まじか、露骨に上がった。アルゴリズムってすげー。
> 0=1.00 s= 75 T=3079
1=1.00 s= 72 T=2405
2=0.97 s= 73 T=2161
3=0.94 s= 79 T=2344
4=0.96 s= 72 T=2848
5=0.96 s= 78 T=3316
6=1.00 s= 76 T=1670
7=0.99 s= 74 T=2435
8=0.97 s= 76 T=2367
9=1.00 s= 75 T=2748

100ケース、Ave=73.36 turn、3 turnは短縮した。
素のままだと、まだ解なし。真ん中のみ固定あけで 73.59、全部入れ73.35、お？
ちょっと全部入れの方針で考える。要素多めにして73.3。採用。

長回し、ええやん。
> 0=1.00 s= 74 T=19686
1=1.00 s= 71 T=20875
2=1.00 s= 71 T=20912
3=1.00 s= 74 T=21359
4=0.97 s= 71 T=23469
5=1.00 s= 72 T=26784
6=1.00 s= 75 T=16774
7=1.00 s= 72 T=21113
8=1.00 s= 73 T=22670
9=1.00 s= 74 T=24666

長回しをさらに倍回しても改善しない。今のアクションだと不足がある。
評価関数いじっても悪化するだけだった。
→運び中のコンテナを補足するようにした。
→まだgird上に無い時は手前で待機するようにした。
→seed0のminが74→72turnには縮まった。ただ、全体あまり改善ない

保留の2次？でも状態数が爆発するなぁ。。。
連続搬出は良さそう。順番が後のものをどかして初めて搬出可能になるもの。

3倍長回しでAve71台は出た。探索力も足りないか。
> 0=0.99 s= 73 T=57485
1=1.00 s= 71 T=64173
2=1.00 s= 70 T=64116
3=0.97 s= 74 T=62470
4=0.97 s= 71 T=69607
5=1.00 s= 72 T=80479
6=1.00 s= 73 T=51082
7=1.00 s= 71 T=62420
8=1.00 s= 72 T=69447
9=1.00 s= 72 T=72898
TSum=719.0
Ave=71.9

終了ターンを簡易に求めて足切り
→ちょっと改善。長回しの結果は変わらず。

visualizerを眺める。seed=4、67 turn。

seed=4、67 turnで終わる時は 0番を掘り起こしてる。
→特定の番号の重さを変えてみる？
→悪化するだけ。
→配置に恣意的な重みを付けてみたけど悪化。
→初期保留の決め打ち、バグってるやんと思ったら、謎の定義のままが一番よかった。

seed=10～99を長回し。Ave=71.36。
seed=0～9がちょっとむずかし目？

探索力で殴るしかないか。

ん？そもそもどこに時間がかかっているかよくわからない。
simulationじゃないっぽい。memo化は少しかかっている。
queでもない、ビーム全体でほぼイコール実行時間なんだけど、なんだろう。
→ガベージコレクションを強制的に発生させたらほぼ揃った。なるほど。。。
→ガべージコレクションが支配的で、2秒の実行で実処理は0.2秒程度しかない。。
→メモリ節約したいが、そんなに無駄ない。。。
AtCoder上だと、8秒くらいかかってる。厳しい。
→手元で10,000ループがAtCoder上で1,600くらい。ちょっと戦えない。

色々調べた。とりあえずオブジェクト型を減らす。
→actionを配列にした、AtCoder上だと2.9sの実行で実処理が2.2sなので、まぁそこまで。
→一応Craneもやっておく。
→もしかして、BitSetもオブジェクト判定か。。。
　→頑張ってもAtCoder上が改善する傾向もないのでいいや。
~~→元のオブジェクトのに戻す。時間めちゃ無駄にした。。。~~
→int でindex取り出さずに、全部配列参照にしたらオブジェクトよりは早くなった
loop 1400→1700回くらい。1turnくらい削れるっぽいので採用。
→BitSetもbit演算でやるかぁ。。。
参考になる。
https://www.torutk.com/projects/swe/wiki/Java%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_%E3%83%93%E3%83%83%E3%83%88%E6%93%8D%E4%BD%9C#32bit%E5%B9%85%E3%81%AE%E3%83%87%E3%83%BC%E3%82%BF%E3%81%A7%E4%BB%BB%E6%84%8F%E3%81%AE1%E7%AE%87%E6%89%80%E3%81%AE%E3%83%93%E3%83%83%E3%83%88%E3%81%8C0%E3%81%8B1%E3%81%8B%E3%82%92%E5%88%A4%E5%88%A5%E3%81%99%E3%82%8B
→やってみた。置換だけなので案外いけた。ちょっとbit演算と仲良くなれたかも。
loop 1700→2100回くらい、やってよかった。
→いっそ全部オブジェクトなくしてみた。
loop 2100→3000回くらい、わお。

AtCoder上相当でAve=77.1
ちょっといじって、100ケースでAve=74.86。

130倍回せたらこれが出るらしい。
> 0=0.97 s= 74 l=400001 T=55595 q1=46440 q2=1277
1=0.99 s= 72 l=400001 T=51608 q1=42520 q2=989
2=1.00 s= 70 l=400001 T=65171 q1=56401 q2=1307
3=1.00 s= 72 l=400001 T=54836 q1=45530 q2=1111
4=0.96 s= 70 l=400001 T=64717 q1=55869 q2=1442
5=1.00 s= 70 l=400001 T=66565 q1=57555 q2=1684
6=1.00 s= 72 l=400001 T=46334 q1=37705 q2=836
7=1.00 s= 70 l=400001 T=56374 q1=46411 q2=1135
8=1.00 s= 70 l=400001 T=70572 q1=60448 q2=1843
9=0.99 s= 73 l=400001 T=50903 q1=41536 q2=1021
TSum=713.0
Ave=71.3

3000lpで、seed=100～1000ケース、Ave=74.036。
失敗ケース、意外とあるな。。。
10149,10468,10524,10648,11311,11521,11548

seed=10149、よくわからない。どういうことだ？
あー、搬出時に待機できないから余ってるのかな。
→10524を除いて、待機できなくて解なしになっている。対策する。★
→10524は難しすぎて見つかっていない。9000回回れば見つかるが。。。

別枠で、やはり搬出後の戻りと搬出で行くのとで被って失敗している。
→あれ、これ解消難しいな。
→んー、でもaction後に盤面から除去するとスコア下がる。戻りも大事っぽい。そのままに。
→最後のターンはすぐ除去でいいのでは？★

**TODO**
貪欲解の強化
　評価関数化
　　搬出可能数や盤面を評価(途中)
　~~目安ターンの精度向上
　　→足切りに~~
　保留の高度化
　　保留先の決め打ち
　最終盤面の特殊処理
　　最後はaction後にすぐ除去する
　アクションの高度化
　　二組じゃないとできないこと
　　搬出の待機
　　保留の待機
　~~初動強化
　　保留の決め打ち~~
高速化関連
　~~1次元化によってさらに高速化できる所の対応~~
　~~全配列化~~
　~~bit演算~~
　筋悪のシミュレートを途中打ち切り？
探索可能にする
　loss毎にビーム
解なし回避

## 10日目(日)
胃カメラで半日飛ぶ。
### 実装
seed=11521がシンプルなので、これで解無し回避する。
→なるほど、状況はわかった。やはりものがなくなった時はaction後に除外でいけそう。
→そもそもactionとして解体を入れたほうがいいかも。最後邪魔になるので狙って除外もあり。

この状態で待機するようになり、解を得た。解決。
盤面に搬出可能なものと、その次のものがあって、搬出可能なものが搬出先に近い場合、
その次のものを先に取りにいくのあり。搬出のactionとして取りにいくのがいい。★

長回しして、ちょっと悪くもなった？
> 0=0.97 s= 74 l=500001 T=65527 q1=0 q2=0
1=1.00 s= 71 l=500001 T=61688 q1=0 q2=0
2=1.00 s= 70 l=500001 T=79657 q1=0 q2=0
3=1.00 s= 72 l=500001 T=64314 q1=0 q2=0
4=0.96 s= 70 l=500001 T=82233 q1=0 q2=0
5=1.00 s= 69 l=500001 T=78913 q1=0 q2=0
6=1.00 s= 72 l=500001 T=55314 q1=0 q2=0
7=0.99 s= 71 l=500001 T=66809 q1=0 q2=0
8=0.97 s= 72 l=500001 T=84189 q1=0 q2=0
9=0.99 s= 73 l=500001 T=60606 q1=0 q2=0
TSum=714.0
Ave=71.4

難しくて見つかってなかった10524は、初期盤面の保留不可マスを減らすと通った。
seed=0～9だとAve=76.1とかなり下がるが、採用しよう。
seed=0からの100ケースでAve=74.3だから大丈夫。

もいっかい2000ケースまわす。
11372、解が見つかっていない。
17が取れないのはわかるけど、まだ仕事はあるのになぁ。
→保留したものは2度目の保留禁止の条件にバグがあり、動かせなくなっていた。
→判定を直して解消。
→選択肢が増えたのかちょっと点数下がった。

改善案
保留中に搬出が見えたら切り替えていいかも。★
終了したNodeの傾向から、どの優先順位で搬出されるかを逆算して、初期盤面に反映するとか？

2000ケースでこけなかったな一度提出しよう。
またこけた、seed=10861。
この4番が保留するが、保留中のため受取手がいないみたい。
解消。

途中で解体しちゃうことで、最後の出力ターンがズレるようになってしまった。
→結構直すの面倒だった。1ターンずつ解体しちゃう場合に、出力の保存がズレてた。
100ケースでAve45.08まで下がっている。

もっかい2000ケース、10782、また失敗。
一度出したものしか残っていないからっぽい。
→違う、クレーン3のルート上だからだ。
えー、めんどう。これ解見つかるやろ。2倍回したら見つかる。
→最後空きクレーンの数より残りコンテナ少なくなったらアクション後に除外するか。
やった、おー！横待機じゃなくて後ろ待機にちゃんと変わった。ターンも縮まった。

もっかい2000ケース。
またあった、11168。
→あー、同時に複数クレーンが消えちゃうことで解無しになる。
→解消
もっかい2000ケース。あれ、2回目だ。10782
クレーン消去がされなくなったっぽい。うーむ。

Ave=76.7まで悪化してきている。うーん。
100ケースだとAve=75.15。
→AtCoder上でloopが3000→2300まで落ちてる。ちょっと落ちすぎ。
→シミュレーションターンの足切りを早めて、2500くらいまでは戻した。
多分これのせいで状態数が増えてしまった。
> →保留したものは2度目の保留禁止の条件にバグがあり、動かせなくなっていた。

→解が見つからない時のみ解禁したい。★
→解がない時のみに限定。3000回にもどった。元の問題ケース11372もOK。

上記の対応で、10782が通るようになった。
→でももとの問題はそのままかも。ちょっと見てみる。
→条件不備だった。直したらOK。11168も大丈夫。

別のエラーもあり。10450。
こういう状態からコンテナ0が解体される。
→残りの数の除去は頭からなので、複数人数存在時は必要人数がなくなってから切る。
→うーん、元問題があったケースで再現ができなくなった。。。でもそれとなく考慮はされてそう。
0～9でAve=75.7 とちょっと回復

エラー、10149。これ意外は通った。
前も出てたが、今回はもう少し難しそう。やはり自ら解体を入れたい。
→自ら解体を入れると、このケースはいけるが大体のケースで点数がめちゃ悪くなる。
→2倍回れば解が見つかるがうーん。。。
→解が見つからない時だけ、自ら解体してみる？

いいや、提出しよう。29位かぁ。。。Ave=74.5なのでローカルとほぼ同じ。
逆算して、上位Ave=64turn弱か、想定よりも遠かった。

NGケース
~~15773、16231~~
11168

がっつり探索絞ろう。
今は搬出後引き返しているけど、真ん中は避けて帰ろう
上は大型クレーンのためにおくので、真ん中搬出は下を通す。
→100ケースでAve=73.21、おっと露骨に効いた。

暫定ケースで解が見つからないやつがある。
→一部条件ミスがあった。提出のものに後で差し替える。★
→まだミスがでる、時間があれば解はでるやつかなぁ…。手元でもごちゃごちゃした時に上手く出ないんだよな。
→解無しはまずいので、回避策入れる。★
→bestの途中解に対して、貪欲で出す？

搬出後の戻りが結構重要だ。
適当にルールで決める。
真ん中を通ってくるので、すぐに上下に逃げよう。お、効いてそう。

lossを出す。pick→搬出までの理想ターンから、増えたターンだけloss。
pick時：wait、不要な上下移動
put時：wait、不要な上下移動、保留するとしたら+pick&putの2ターン、
　　　　最短経路から増えた分
最後、クレーンが何もしないターンもloss。
大型クレーンは、スコア上lossを大きめに見積もってもいいかも。
→ダメだ、そんな時間ない。

**TODO**
貪欲解の強化
　評価関数化
　　搬出可能数や盤面を評価(途中)
　保留の高度化
　　保留先の決め打ち
　最終盤面の特殊処理
　　最後はaction後にすぐ除去する
　アクションの高度化
　　二組じゃないとできないこと
　　搬出の待機
　　保留の待機
高速化関連
　筋悪のシミュレートを途中打ち切り？
探索可能にする
　loss毎にビーム
解なし回避
　~~pick対象がない時にすぐに除外~~

## 11日目(月)最終日
### 実装
解無し時の回避だけいれておくか。
11168これだけまだ落ちる。
入れた。最後一人だけ残して頑張る方針。

seed=10498、これだけ残ってる。これはだめだー。→AtCoder上だと意外と回って解が見つかった。よし。

最後、パラメータ調整していく。
時間に直してcheck。意外とループが回らないやつもある。

あれ？seed=60こけた？
→わからん。再現しない。いいや。
100ケースでAve=72.93。72台になったえらい。

あれ、やばそうなの見つけた。消えてない。
→対応。

2000ケースでAve=72.5745。

10749、NG→保留不要だが保留を許すラインを上げる。
Ave=72.2365
背後にコンテナがあるときは背後から帰りたい。

NG、15416、10269。うーん、時々落ちるがもういいや。

2994 ms、ちょっと時間こわい。
打ち切り増やそう。

2000ケースでAve=71.9595、終了！

記念の30秒回し、あーちゃんと70ターン切れるんだな。
> 0=1.00 s= 72 l=226303 T=30011 q1=0 q2=0
1=1.00 s= 70 l=233364 T=30004 q1=0 q2=0
2=1.00 s= 69 l=183989 T=30006 q1=0 q2=0
3=1.00 s= 70 l=247931 T=30004 q1=0 q2=0
4=1.00 s= 67 l=196820 T=30005 q1=0 q2=0
5=1.00 s= 68 l=195461 T=30005 q1=0 q2=0
6=0.99 s= 73 l=289992 T=30005 q1=0 q2=0
7=1.00 s= 69 l=237305 T=30004 q1=0 q2=0
8=1.00 s= 69 l=204518 T=30006 q1=0 q2=0
9=1.00 s= 70 l=232226 T=30004 q1=0 q2=0
TSum=697.0
Ave=69.7

終了直後でこんな感じ。

## 反省
システスで大コケしなければ橙だけど、私の結構コケるんだよな。。。周りの傾向次第。
探索するにはちょっとまともな回数回らなかった。
ローカルと提出環境の差異がここまであると思ってなかった。
BitSetじゃなく、bit演算を有効に使えたのは収穫。(今更だけど)

あー、上位陣の見ていると、真ん中2の行を空けるのと、1と3の2行を空けるのとの使い分けっぽい。
2段階の探索をしてもよかったな。

コンテナを保留する数の最小がDPで求まる、なるほど。。。
適当に評価関数で組んだりしたけど、絶対こっちだ。アルゴ力不足。

今回の振り返り結果
・言語☓ ：いい加減Rustを使う。
・根本アルゴ◯ ：ビーム系、pick&putで1手であってそう。
・前処理☓ 　　　：コンテナ保留数、保留場所の事前計算ちゃんとできた。
・学び△ 　　　　：bit演算できてよかった。今後も使おう。オブジェクトの悪影響もよくわかった。

システム結果、3つほど失敗してた。
3つを除いてAve=72.7、ローカルより悪いなぁ。。。

### 賢者達の解法

saharaさんの、方針はシンプル。待機は許す方針なのかな？

Montさんの、道が固定じゃないのか。賢そう。

4etaさんのおしゃれ！

暫定2位のJiroさん、ビムサで評価関数作り込み？
https://x.com/Jiro_tech15/status/1795034155803099597

暫定1位のbowwowさん、3次元探索とは？→あー先読みっぽい。
https://x.com/bowwowforeach/status/1795033980015640708
この移動方法管理、絶対使える。
https://x.com/bowwowforeach/status/1795063661502873628

すごい回ってる。

terryさんの、経路を真ん中固定にしたのがいまいちだった様子。
soumatさんの、コンテナを不平等に扱うのかー。
tanakaAさんの、賢い決め打ち。
へー！