解法概要

好みの色列と頭から連続で一致している範囲が1つ伸びるまでを1ステップとし，ビームサーチを行いました．

ビームサーチでは，ステップごとのビーム幅までの状態をテーブルとして保持し，各ステップで評価値の良い数個の状態をそれぞれ数パターンで展開して次のステップの状態集合へ加え，次のステップの処理に進むということを繰り返しました．
そして，ヘビが完成したか行き詰まった場合には最初のステップに戻り，前回のテーブルをそのまま利用して同じことを行う，ということを制限時間まで繰り返しました．

評価値としては，\((操作列の長さ)+\frac{1}{2}(盤面中心から各餌までのマンハッタン距離の和)\) を用いました．
また，各状態は展開した回数に応じて評価値にペナルティを加え，有望な状態は複数回展開しつつ同じ状態ばかりが展開されることを避けました．

状態の展開については，最初に数パターンの行動列を適用して分岐させた後，それぞれで1パターンの行動列を確率的に選ぶことを繰り返し，次のステップまで進行させました．

（AtCoder のシステムテスト（2000ケース）では32ケースで同率1位，4ケースで単独1位でした．
盤面サイズ \(N\) にはあまり依存せず，好みの色列の長さ \(M\) の大きいケースがやや苦手だったようです．）

解法詳細

情報の管理

ヘビ

ヘビの体1マスごとの情報として，それぞれのインデックスと場所を管理します．
ヘビ全体は両端操作を持つ deque 的なデータ構造を用いてそれらを並べ表現します．
（ビームサーチの際に状態を丸ごとコピーしていたため，高速化を目的として実装は vector を用いリングバッファの要領で行いました．）

インデックスは頭に近いほど大きくなる通し番号とし，1歩進むごとに+1したものを先頭へ追加します．
餌を食べなかった場合は最後尾を削除することでヘビ全体が1マス進みます．

盤面

配置されている餌の色番号の他，\((ヘビの体のインデックス)\times(-1)\) を配置します．
これにより，噛みちぎりが発生するかを簡単に判定できます．
また，その位置がヘビの体の何番目であるかや，餌を食べない移動の際に各マスを何ターン後に通れるかについて，簡単に求めることができます．

行動列

まとめて受け取り1つずつ消化していけるよう，保留中の行動列を（逆順で）持たせておきます．
探索で得た行動列はここに保存しておき，後に述べるように噛みちぎった際もここに情報を移すことで体を復元します．
また，これが必ず実行するべきものなのか，より良い行動列を探索して更新すべき仮のものなのかも分かるようにしておきます．

盤面の探索

以下の4種類のパスの探索を行います．
（好みの色列と頭から連続で一致している範囲の末尾を「正しいしっぽ」と呼び，各ステップで付け足したい好みの色列に対応する色の餌を「ターゲット」と呼ぶことにします．）

1. 餌の無いマスのみを通る，ターゲットまでのパス．
2. 頭から正しいしっぽまでの範囲で自身を噛みちぎるパス．
3. 他の色の餌を食べても良い，ターゲットまでのパス．
4. 1マスだけ進むパス．

探索の際，方向インデックスの順番は基本的に毎回ランダムなものを用います．
（ \(4!=24\) 通りのテーブルをあらかじめ用意し，毎回ランダムな1つを選択しました．）

1. 餌の無いマスのみを通る，ターゲットまでのパス

しっぽが正しいしっぽのときにのみ探索します．
また，この探索でパスが見つからなかった場合，次に餌を食べるか噛みちぎるまではこの探索を行いません．

移動距離の短い順にいくつかのターゲットまでのパスを探索します．
1つを選ぶ場合には，その中で一番短いものとの移動距離の差を \(d_i\) として，\(1/\sqrt{1+d_i}\) を重みとする確率で選択します．

探索の際，ヘビのインデックスと対応した盤面のインデックスを元に各マスを通れるようになるタイミングが分かるため，それも考慮します．
（実装が複雑になるため，時間を稼ぐことで通れるようになるパターンは考慮せず，最短路のみを対象としました．）

2. 頭から正しいしっぽまでの範囲で自身を噛みちぎるパス

ヘビの体の色は頭から順に餌を食べた順で並んでいます．
そのため，ある場所で噛みちぎった後，そこからしっぽに向かって自身の体のあった位置を辿ることで同じ順で食べることができ，体を復元できます．

また，仮にある状態から \(t\) ターン移動して噛みちぎったとします．
このとき，元の状態で「正しいしっぽのあった位置から \(t\) 個前（頭側）の位置」を始点とした，ターゲットまでの探索 \(1\) のパスが存在している場合，「噛みちぎり → 正しいしっぽまで復元 → 探索 \(1\)」でステップを進めることができます．
加えて，正しいしっぽから \(k\) 個後ろにターゲットの色を取り込んでいる場合，元の状態で「正しいしっぽのあった位置から \(t\) 個前」を始点として，「正しいしっぽの \(k\) 個後ろの \(t\) 個前」を終点とする探索 \(1\) のパスが存在している場合も同様にステップを進めることができます．
（ターゲットの色を取り込んだ位置 \(k\) の集合を管理しておきます．）

ある程度の移動距離までの噛みちぎりを対象とし，ステップを進めるまでに必要なターン数がより少ないものを探します．
複数列挙する場合はターゲットの違うものを選択し，パスの存在確認と終点での分類とに使用する探索 \(1\) の探索は，ここでのみ固定の方向順で行います．

なお，行動列として予約するのは噛みちぎり（と復元）までで，そこからは復元後に行われる探索 \(1\) に任せます．

3. 他の色の餌を食べても良い，ターゲットまでのパス

探索 \(1,2\) で見つからなかった場合に仮行動として設定し，途中でそれらが見つかった場合は中断します．
探索 \(1\) と同様にいくつかのターゲットまで探索します．

4. 1マスだけ進むパス

優先度の高い順に 餌の無いマス → 餌のあるマス → 噛みちぎり とし，1つを設定します．
（その他いくつかの優先度付け（外方向，より長く空きマス（あるいはそれと餌のマス）を移動できる方向，空きマスとその他との境界を辿る方向など）も試しましたが，あまり手を加えない方が良い結果になるようでした．）

ビームサーチ

ステップごとのビーム幅までの状態をテーブルとして保持し，各ステップで評価値の良い数個の状態をそれぞれ数パターンで展開して次のステップの状態集合へ加え，次のステップの処理に進むということを繰り返します．
（ビーム幅は20，展開対象は10個としました．）
そして，ヘビが完成したか行き詰まった場合には最初のステップに戻り，前回のテーブルをそのまま利用して同じことを行う，ということを制限時間まで繰り返します．

評価値としては，\((操作列の長さ)+\frac{1}{2}(盤面中心から各餌までのマンハッタン距離の和)\) を用います．
（中心にまとまっていた方が餌がまばらになった後取りに回らなくて良いため嬉しいという思いで，係数は大雑把な調整の結果です．）
また，各状態は展開対象となるごとに評価値を \(1.1\) 倍し，有望な状態は複数回展開しつつ同じ状態ばかりが展開されることを避けます．

状態の圧縮については，「ヘビの頭，頭の1つ後ろ，体長の中央，しっぽ」の4箇所の位置のみを基準に行い，同じ場合は評価値の良いものを残します．

状態の展開については，最初に数パターンの行動列を適用して分岐させた後，それぞれで1パターンの行動列を確率的に選ぶことを繰り返し，次のステップまで進行させます．
具体的には，探索 \((1+2)\) → \(3\) → \(4\) の優先度順（見つからなかった場合のみ次へ）で初期行動列を設定し，その後 \(1\) → \(2\) → \(3\) → \(4\) の優先度順で探索と実行を繰り返して次のステップまで進めます．
（分岐はそれぞれ 4+2，3，1 パターンとし，噛みちぎりの探索は移動距離15までとしました．）

状態は丸ごとコピーしており，ビームサーチが回ったのは seed 0 では 600周程度，seed 2 では40周程度でした．