解法概要

• 移動経路の決定
• 遷移規則の割り当て

を順に行いました．

各マスでは「（長さ1のものを含め）これ以降は規則的な移動パターン」というタイミングが訪れます．
その際の移動に固定で対応させる色数を \(0,4,8\) の3パターンで試し，一番スコアの良いものを出力しました．

遷移規則の割り当ては後ろ（経過ステップ数の大きい方）から順番に行い，不規則な移動に対して \((c,q)=(*,Q-1),\dots,(*,0)\) を順番に割り当てました．
このとき， 同じ \((A,S,D)\) が既に現れている場合は，（最初に現れる不規則移動ステップを除いて）それと同じ \((c,q)\) を再び割り当てました．
また，規則的な移動においては直前の内部状態を維持させました．

移動経路の作成では，この不規則な移動ができるだけ短くなるように経路を構築しました．

解法詳細

移動経路の決定

固定色について

各マスでそれぞれあるタイミング以降に現れる規則的な移動パターンに対して，全マスで共通するルールで固定色を割り当てます．

割り当てる色数は3パターンで試し，

• \(0\)：割り当てなし
• \(4\)：「それ以降そのマスでは上移動のみ」などの4方向
• \(8\)：上に加え「上下上下…」「左右左右…」

とします．

8色パターンについては，

• 壁の生成方法が「壁に接していない場所から壁に接するまで伸ばす」というものであるため，細長い通路が生成されやすい
• 今来た経路を戻る経路を採用しやすくなる

と考え導入しましたが，採用されたのはほとんどが4色パターンでした．
（最適な経路では各目的地間で同じマスを複数回通ることはない，という勘違いを元にした実装をしていましたが，考え直してみると8色パターンにおいてはそうとは限らないため，正しく実装できていれば8色パターンの選ばれるケースが増えていたかもしれません．）

経路の構築

後ろから順に経路を決めていきます．

一部のマスに固定色が割り当てられている状態に対して，できるだけその色を崩さないような経路を求めます．
各目的地間で，「経路の長さ」「固定色に沿った移動」「固定色を配置されていないマスでの移動」「固定色を潰した移動」にそれぞれ重みを付け，ダイクストラ法を利用します．

重みについては，

• 余分に使えるステップ数がその区間の最小移動回数以上：\((1,1,10,100)\)
• それ未満：\((10,1,10,100)\)
• それらではステップ数制限を超えた場合：\((1000000,1,10,100)\)

としました．

最終盤面の構築

経路の構築で使用するために，各マスへ最終盤面の固定色を配置していきます．

まだ決まっていないマスの中から，後ろの規則的な移動パターンが長い順に数マスへその色を割り当てます．
そして，その状態で全体の経路を構築し再び固定色を割り当てる，ということを区切った時間内で繰り返します．
一度に割り当てる個数については，高速化のため \(T/1000\) を基準に \(2\) 以上 \(10\) 以下で定めました．

また，移動経路に含まれるマスのうち，まだ固定色の決まっていないマス数が一定値以下（ \(5\) 以下としました）となった場合，

• ランダムな連続する2列か2行の固定色を初期化
• 固定色の決まったマスからランダムに数マス（ \(5\) マスとしました）の固定色を初期化

のいずれかをランダムに行います．

そうして，各マスの規則的でない部分の長さの総和をスコアとし，再び一定値以下となるまでの最小スコアを基準に焼きなまし法を行い，全体で一番良かった経路を採用します．

遷移規則の割り当て

固定色以外のステップ

後ろから順番に，固定色を割り当てられないステップに対して \((c,q)=(*,Q-1),\dots,(*,0)\) を順番に割り当てます．
このとき，同じ \((A,S,D)\) が既に現れている場合は，（経路順で最初に現れる割り当て対象なステップを除いて）それと同じ \((c,q)\) を再び割り当て圧縮します．
また，その確率を増やすため，そのマスを経路順でその前に訪れる際の移動方向と \(c \bmod 4\) とが対応するような \(c\) を優先して割り当てます．

使用する色数としては，割り当て対象のステップ数を \(x\) として各固定色モードで \(\sqrt{x} \pm 5\) を全探索し，一番 \(C+Q\) が小さくなったものを採用します．

使用する内部状態数は圧縮できたステップ数によって異なるため，自由に割り当て後その最小値が \(0\) となるよう全体をずらします．

固定色のステップ

内部状態を常に維持します．
（後ろから固定色以外のステップで割り当てられた \(q\) を引き継ぐ．）