本番519位解法備忘録
Haru_mb（はる えむびー）と申します。解説か怪しいですが、良かったら見て行ってください。
問題
マクロを持つ、向きがあるロボットでボールをかごに片付けてね
私の提出：
提出にある整数の除算方向の変更テンプレ：
私の解法の要約：
直進マクロ、最短経路限定のマクロ長DPのビームサーチ
0. 考えたこと
0.1 この問題は2種の最適化があるなー
マクロの最適化という順序依存
ルートの最適化という可換性の塊
0.2でもたぶん「マクロ育成ゲー」だよね→ビームサーチ
今回の私の失敗 ビームサーチがしたかっただけともいう
0.3 ルートからマクロをうまく作り出そう→とりあえず直進でやってみよう
ちなみにこのあと、F^a R F^bでやってみましたが、計算量をうまく削れず、お蔵入り。
1.やったこと
- BFSで全点間最短経路前計算
- 移動経路復元（移動列生成＋壁衝突検知）
- マクロ長を状態にしたDP
- DP評価を用いたビームサーチ
- 最終順序で再DPして出力生成
1.1 全点間最短経路前計算
102行-140行
開始地点と向きに対して、各地点への最短経路を単純にBFS
1.2 移動経路復元
142行-156行
ただし、ここで壁衝突が発生すれば、後々のDPで生かすためにそれ込みの移動記録
1.3 マクロ長でDP
160行-212行、226行-247行
DPに現在のマクロ長（Fの長さ）での最短ターン数を状態として持たせる。
なお、ここで壁衝突を考慮する
マクロの成長と既存マクロの再利用の遷移のもらうDP
1.4 そのままビームサーチ
214行-267行
ロボットの位置→ボールの場所→対応する籠で1操作
評価関数はDPリストのmin
ただ、ビームサーチ内の評価値と、最終的な出力が一致せず苦戦
1.5 ビームサーチからもらった最適な順序でもう一回DP回して解を生成
269行-417行
ここのDPを先に書いて、ビームの中身はより最適な実装にしているので、結果として中身が別物です。そのせいで、ビームサーチ内の評価値と出力値が相関はあれど違う値になってしまった...
2. 振り返り
2.1 枝刈りには根拠が必要とは限らない
「乱択」があまり発想として結実せず、効果的な探索ができなかった
2.2 DPを評価関数とするビームサーチをしっかり実装できた
完全手動実装でビームサーチ×DPを形にできた
2.3 BFS, DFS, A*, 01BFS, DP周り、ビームサーチに慣れることができた
レートとしては上がってませんが、経験値はものすごく高かったと思います。