解法概要

全体の流れ

ボールを1つずつカゴへと運びました．
移動途中で S は使用せず，マクロにも使用していません．

使用するマクロと片付けるボールの順番の探索はどちらも焼きなまし法を用いました．

\(\sim 1\)s では\(4\)回ごとにマクロに変更を加え， \(\sim 1.7\)s では\(128\)回ごととし，その後は順番変更のみを行いました．
ただし，ボールの数 \(M\) が \(10\) 以下の場合は bitDP によって順番を決めました．
また，マクロを変更した後は順番について何回か山登り法による改善を施した後，焼きなましの判定へと進みました．

評価値

\((出力する操作列の長さ)\pm(マクロの各要素による微小量)\) です．
微小量についてはマクロに F や P（=FF）が含まれる方が他より嬉しいとしました．
（スコアのブレに飲まれてしまい，あまり効いているかは分かっていません．）

マクロ変更後の前処理など

順番探索の高速化のため，マクロを変更するたびに以下の前処理を行いました．

• 盤面の各マスとロボットの方向とに対応した \(4N^2\) 状態について，マクロでの移動先を求める．
  
• 開始地点，ボール，カゴに対応する \(2M+1\) 状態について，BFSで状態間の最短路を求める．
  

ボールとカゴについてはそれぞれ4状態が対応しますが，ボールからカゴへの最短路を求めた際に（軽くランダム要素を入れつつ）1つに固定してしまい，それを元に他の最短路を求めました．

この固定により損をしてしまう場合がありますが，焼きなましの際にいくつか（マクロ，順番）ペアの候補を残しておき，最後にそれらを固定し向きを考慮したDPを行って，より良い移動方法が無いか確認しました．

その他の工夫

前処理結果は2つの保存場所を切り替えながら記録し，マクロの変更が棄却された場合には1つ前の結果をそのまま利用して順番の探索を続けられるようにしました．

また，開始時に固定で MFFM という操作を行い，それを併用してマクロを構築しました．

解法詳細

パラメータ調整

今回初めて Optuna を使用しています．
以下の説明で中途半端な値となっている部分は Optuna によって出力された値です．
一方，どの近傍を選択するかの重み付け部分は，手で調整したものよりその後改めて試した際にスコアが下がってしまったため，自分で大雑把に定めています．
（その他のパラメータの最適化も同時に行っていたため，重みだけに絞っていれば良いものが見つかったかもしれません．）

マクロの探索

開始状態

FFRFFLF とします．
後述の近傍への変更を行いやすくしたいという意図です．

マクロの変更

以下の近傍を使用します．
（ L, R を反転させたものは記載を省略します．）

• 1点削除
• 操作が異なる隣接2点のswap
• F の挿入
• FF の挿入
• RFL の挿入
• R の挿入
• RR の挿入
• RFR の挿入
• R の末尾挿入

削除確率については，マクロの長さを \(l_{macro}\)，展開後の基本操作回数を \(l_{expand}\) とし，以下のようにします．
（前半のパラメータは \(l_{expand} = 0.9 T\) で \(50\)%，\(T\) で \(70\)% となるように定めました．）

\[ \max \left( \frac{1}{1 + \exp \left( k (n_0 - l_{expand}) \right)}, \frac{l_{macro}}{70.65} \right) \]

前半はシグモイド関数で，\(l_{expand}\) が大きくなるとある場所で急に値が大きくなり，\(1\) に漸近するようなS字型の関数です．

それ以外のどの近傍を使用するかの確率は重みを付けておきます．

挿入のうち，R，RR，RFR は大きくマクロでの移動を変えてしまいます．
そのため，挿入位置は以下の式によって，実行時間制限に対する実行時間の割合 \(t\) が大きくなるほど端に近い位置が選ばれやすくなるようにします．
（\(r,r'\) は \(0 \sim 1\) で生成される一様乱数）

\[ \begin{cases} r^{1+1.023 t} & \left( \text{if } r'<0.5 \right) \\ 1 - r^{1+1.023 t} & \left( \text{if } r' \geq 0.5 \right) \end{cases} \]

マクロ変更後

マクロ変更後はボールを運ぶ順番との噛み合いが悪くなってしまうため，そのままでは受理されることが難しいです．
以下の近傍で山登り法によってある程度順番を整えた後，焼きなましの判定に進みます．

• ランダムな長さ \(7\) の区間で bitDP（確率 \(80\)%）
• 後述の順番近傍（確率 \(20\)%）

この変更は \(30\)回を上限として行い，\(5\)回連続で改善がなかった場合は中断しました．

順番の探索

マクロ変更後の前処理によって，\(2M(+1)\) 地点での方向や間のパスは固定しています．

順番の変更

以下の近傍を使用します．

• ランダム1点ランダム移動，ランダム区間ランダム移動
• ランダム1点選択移動，ランダム区間選択移動
• 選択1点ランダム移動，選択区間ランダム移動
• 選択1点選択移動，選択区間選択移動
• ランダム1点交換，ランダム区間交換
• 隣接区間交換
• 長さ \(5\) のbitDP

どれを使用するかの確率は重みを付けておきます．
重みはマクロと同じく自分で大雑把に定めましたが，選択移動は局所最適に戻してしまう力が強いと考えられるため，確率を下げました．
また，bitDPはそれに加えて時間もかかるため，より確率を下げました．

ランダムではなく選択する場合の変更場所については，そこで切断した際や挿入した際などの手数変化が最も良い場所を貪欲に選択します．

（マクロ，順番）ペアを固定した改善

探索において，\(2M\) 地点での向きは前処理の際固定してしまっています．
そのため，良かった（マクロ，順番）ペアをいくつか保存しておき，実行時間の最後で向きを考慮した DP をそれぞれで行い，より良い移動を探します．

また，最初の MFFM を FF に置き換えたものも確認します．
（といってもこちらの方が良いのはマクロに FF が1箇所しか含まれていない場合のみです．）

元々はベストだったペア1つのみでこの確認を行っていました．
複数保存しておくことを試したのがコンテスト終了の直前であったため，重複除去は行っていません．
しかし，そのままでは似たような出自のもので埋まってしまうことが予想されるため，候補を保存する際，ソート基準となる出力の長さに小さな乱数を加えています．

保存は\(20\)個までとしました．
急遽複数回行うことになったということもあり，実行速度にあまり気を配っておらず，実行時間制限を超える恐れがあったためです．
実行時間の最後の \(1.9\) s～ で行っており，実際，保存が\(10\)個の場合でも時間制限を超えているシードがありました．
しかし，結局時間を見て中断するようにしたため，より多く保存しておいても良かったかもしれません．
（中断処理を入れたにもかかわらず評価値の悪い方から確認してしまっているというほどに，ぎりぎりでの変更でした．）
（この複数への変更により，コンテスト終了1分前の段階で暫定順位が42位辺りであった所から36位に上がっています．）