今回は「経路を固定して C+Q を圧縮 → 色 0 と状態を複製してさらに圧縮 → 経路そのものを焼きなましで調整」をしました。

---

経路固定での圧縮

まずは経路をいじらず、状態遷移だけを圧縮した。

• 「ある時点以降二度と踏まれないタイル」は色 0 にする
• 色 0 のタイル上では
  
  • 状態 0 → 上
    
  • 状態 1 → 下
    
  • …
    のように、連続した直進を 1 つの遷移で表現できる
    
• これで C+Q を削減

可視化：

---

後ろからの圧縮

各タイルについて、後ろから見ると

• そのタイルの次の色
• そのタイルからどの向きへ動くか
• 動いた先でどの状態になっていてほしいか

が一意に決まる。
前から決めると「次にどの色になってほしいか」の情報が次に同じタイルを踏んだタイミングでしか分からなかった。

---

色 0 と状態の複製

C+Q をさらに削るため、色 0 で動く状態も複製した。

• 色 0 で自己ループしている状態から抜けるには、別の色のタイルが必要
• そのために色を増やすと C が大きくなる
• 代わりに「色 0 で特定方向に進む状態」を複数用意した

イメージ：

---

経路の焼きなまし

ここまでは経路を固定していたが、経路自体も焼きなました。

方針メモ：

• 「これから角（曲がる移動）として踏まれるようなタイルを踏んでしまうと嬉しくない」
• 「角は少ないほど嬉しい」

そこで評価関数として

任意の時刻 t で、
「時刻 t 以降に角として踏まれるタイル」を踏んだ回数

を最小化するように焼いた。

結果：

---

雑感

• 移動回数が余り気味で、経路構築をあまり最適化できていない感じがした。
• 角として使うタイルの最小化も焼いてみたが、1000 回くらいしか回せずやめてしまった。
• 上位を見てるとやはり経路というか角タイルの決定方法が大事で、ここをいろいろ試せていればなぁと思うなど。