- 0.はじめに
- 1.問題文の概要
- 2.ビジュアライザ
- 3.「何もしない」解を提出する
- 4.「ロボットをBFS通りに動かす」
- 5.コンテスト初日「トップ集団の貪欲」に少し足りない
- 6.解法アイデアメモ
- 7.コンテスト2日目：貪欲集団に並ぶ
- 8.トップ集団の貪欲から少しでも抜け出したい
- 9.デバッグに時間を費やす
- 10.コンテスト3日目：ついに集団からほんの少し抜け出す
- 11.デバッグを続ける
- 11.共通の規則を使用する（うまくいかない）
- 12.コンテスト4日目：1回しか通らないマスを共通のルールを使う
- 13.うまくいかない時間
- 14.コンテスト5日目から7日目：問題文に戻り、必要な色数と状態数について考える
- 11.考察を進め、seed25のオートマトンを完成させる
- 12.コンテスト9日目：BFSのルートを改善する
- 13.試行錯誤を続ける
- 14.コンテスト9日目：うまくいかない
- 14.得点源
- 15.うまくいかない時間
- 16.コンテスト10日目：うまくいかない
- 17.コンテスト最終日
- 16.最終結果
- 17.終わりに
- 18.復習
0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴5年11か月のかえでです。
これは、2025年11月7日金曜日19時から11月17日月曜日19時までの約10日間開催された「HACK TO THE FUTURE 2026 （AtCoder Heuristic Contest 056）」の参加記になります。
この参加記はコンテスト期間中に書いています。そのため、冗長で、毎回長文となっています。読む人のことを考えればもう少し簡潔に書きたいものの、失敗したところが自分にとって記録しておきたい内容になるため、なかなかカットすることができません。どうぞお許しいただければと思います。コンテストの雰囲気を感じたい方に読んでいただければ幸いです。
さて、今はコンテスト開始1時間前です。コンテストが始まる19時を待ちたいと思います。
1.問題文の概要
問題文を読みます。ロボットの動作例のアニメーションを見ます。ロボットがいて、複数の目的地に順番に移動するようです。
2.ビジュアライザ
問題文の「例を見る」のリンク先からビジュアライザを見た後、seed0から順番にseedをめくり、パラパラとビジュアライザの初期盤面を眺めます。壁はそこまで密ではないようです。
今回はビジュアライザに力を入れてくれているとのことで、見た目がきれいだなあと思いました。
3.「何もしない」解を提出する
順位表をチラ見すると、同じ得点が並んでいます。順位表の下はサンプルコードの提出だと思いますが、それ以外の同得点は貪欲解法を疑います。
相対スコアなので、サンプルコードからの相対的な位置で、貪欲のスコアを予測するのに使いたいと思います。
とりあえずメモ。
ん－、複数の貪欲方法がありそうです。
とりあえずメモ。
さて、自分でプログラムのひな型を書きます。最初は
- 何もしない
プログラムを提出しました。無事ACしました。
コンテスト開始から40分が経過しています。
あ、また貪欲っぽい得点でトップの得点が上書きされています。自分の提出との相対位置をメモしておきます。
うーん、問題を読んではみたものの、何色あればいいのか、見当がつきません。
散歩をしながら考えます。
状態を作ってBFSを行いましたが、思ったように動きません。WAをLLMに修正させる嫌なパターンにはまりそうだったので、一旦やめることにしました。
4.「ロボットをBFS通りに動かす」
- まずは、ロボットを思った通りに動かすことを考えます。
次にそのマスを通るときにしてほしい動きになるように色と状態のセットを変えておきます。
- スタートから目的地を順にBFSで回っていきます。
- そのマスにどこから入ってどこへ行くかをマスごとに記録しておきます。
- そのマスに来た時の１回目と２回目の動きにグラフの辺を貼ります。
- グラフの辺を状態として持つように色と状態を割り当てていきます。
- 途中で数が足りなくなるかもしれませんが、途中まで意図したように動ければ全部の目的地をまわらずに終了することにします。
LLMを使って実装します。
seed0ではスコアが1247になりました。100テストケースの平均は1749。最大は9904、最小は180になりました。
コンテスト開始から2時間経過しています。絶対スコアは 133972 になり、何もしなかったときの9259744から大幅に減りました。
一番スコアが良かったseed180を見ると、Rule Usage Heatmap に斜めの赤い点が見えました。今回のビジュアライザは多機能のようなので、使いこなしたいものです。
5.コンテスト初日「トップ集団の貪欲」に少し足りない
1ターンに1規則を割り当てて、BFSどおりに移動します。最後にC+Qが小さくなるように割り当てを変更します。規則の数が決まっているときに、CとQの差が小さい、正方形に近い形が最もC+Qが小さくなりそうということは、1×10、2×5、3×3といった簡単な例（C+Qはそれぞれ11、7、6になる）からも想像がつきました。
実際行ってみると、この解法のスコアがとても良いということがわかりました。seed25ではスコア25が出ました。
提出をすると黄パフォがでました。
これ、もしかしてトップの貪欲にたどり着いたのではないだろうか。
提出すると、絶対スコアはほぼ半分になりました。
しかし、先頭集団の貪欲の相対スコア、35,316,152,440にはほんの少し足りないようです。単純に計算誤差な気がします。今はまだ最適ではないCとQなのかもしれません。
ビジュアライザを見ると、最後に停止色として独自の色を割り当てていましたが、無くても良かったので削ります。
まだ、集団には届きません。
余りが0になると、停止に1色多く使っていそうです。修正をします。
今度こそと思って提出をします。
貪欲集団と同じ 29,936,139,185 になれば17位になれますが、集団の下なので、73位になりました。
6.解法アイデアメモ
行き詰ったので他の解法を考えます。
たとえば市松模様とかはどうかと思うものの、目的地の多さからうまく使える気がしません。
別アプローチを考えることます。
たとえば、交差点とベルトコンベアに分けることを考えます。自由に動ける場所と一定の方向にしか動かない場所に分けたいものです。
グリッドに固定のベルトコンベアを作ってみます。
うーん、難しい。
7.コンテスト2日目：貪欲集団に並ぶ
ふと、先ほどまでの貪欲集団に少し足りないプログラムの不要な個所に気づきます。
終了するフラグも状態に入れる必要はないと思ったので、修正して提出をします。
無事、上位の貪欲集団の仲間入りができました。コンテスト2日目、土曜の午後のことでした。
8.トップ集団の貪欲から少しでも抜け出したい
まだ、ルールは１回ずつしか使えていません。複数回使う方法を考えます。
まとめられそうだと思うものの、アイデアが思いつきません。
相対位置にすればよいのでしょうか。
実験します。
バグっているのだけど、解法の方向性は良さそうです。
最後まで到達するプログラムになりましたが、スコアが悪かったので一旦ストップします。
元の解法に戻って、ベストの遷移（どのマスから入ってどのマスに移動するか）をビジュアライズします。
今はseed0で1023ターン、全ての遷移を記録しているのでC×Q=32×32=1024となっています。どうみてもまとめられそうなものがあります。
まとめてみると、1023を950にできました。
問題文にUDLR以外に「移動しない=S」があることに気づきました。
これ、使うと良いことがあるのでしょうか。
9.デバッグに時間を費やす
コンテスト3日目、2025年11月9日の朝です。複数回同じ（色，状態）ペアを使う方法を考えていました。時系列IDを振るのがあまりに良すぎてそこから抜け出せずにいました。
- 同じ色でRを状態0からN-1まで持っていたらどうだろう。直線の途中に有向辺を貼って終端を同じにすれば使いまわせるだろうか。→分岐したくなって、重複ルールを作ってしまうだけだった。
- 一番最後の目標だけなら、すでにたどり着いていれば相対位置が同じ位置からループすればたどりつけるはず。→スコアを縮めるほどの効果がない。複数目標をやろうとすると、合う部分を見つけるのが難しい。
うーん…
と一日頭をひねっていたのですが、朝ベッドの中で試行錯誤をしていたら、あ、そうか、と思い出しました。
問題文の例で、同じ規則を繰り返し使用して目的地にたどり着いていたではありませんか。
これを実装すればよいのかも。
問題文を読み返して、初めてサンプルプログラムを見ました。ん、これ、一手をルールとして記録するタイプだ。これをマンハッタン距離からBFSに変えれば、今のトップ集団の貪欲にたどり着けそうです。（C、Qの長さを正方形に近くなるように記録を割り振りなおせばよい）
んー、問題文は何度でも読むとよいですね。
自分が探していた該当箇所はここ。
規則1を繰り返し使っています。
これを素直に実装します。同じマスを通らないときは順調です。しかし、一度通ったところにゴールがありました。
私はといえば、集団から抜け出せずにいます。集団には100人以上います。1点でも上になれば黄パフォになるのですが…。
トップとの相対スコアを見ると、絶対スコアは2391、平均47.8くらいのスコアが出ていそうです。
連続した部分の規則をまとめることができれば…。それだけでいいのに、できません。
目標地点が少ないテストケースなら今よりも詰めることができるかもしれません。
狙いはseed25、自分のベストスコアは24です。
例えばこの場面。上に移動するごとにルール１個追加していますが、一つにまとめることができそうです。
(8,2)のC=11から(3,2)のC=3までは全てUで1個ずつ別のルールが割り当てられているが、その後一回も再訪がないので、一つにまとめても問題ない。余分なルールを削除して詰めるイメージ。
実装するとルールが143個から113個に減りました。単純に考えてスコア24をスコア22に減らせそうです。
Cの色のみで規則を作ったので、CとQの数が近くなるような最適な数にルールを振り分けたいと思います。IDをつけかえるだけでしょと思ったのもつかの間、それがなかなかうまくいきません。
何で…？
デバッグ出力とビジュアライザを見ながら、悪戦苦闘しているうちに、やっとほしかった解が出ました。
初めて複数回同じルールを適用してスコアが１減りました！
おー、できるよね。やっぱりそうだよね。
絶対できると思っていたのになかなかうまくいかなくて、心がすり減っていたので、あー、やっとできた、とホッとしました。
10.コンテスト3日目：ついに集団からほんの少し抜け出す
まだバグっているものの、スコアを1減らしたものができたので、これまでのプログラムを解法1、今回のプログラムを解法2として、解をそれぞれ作成後、シミュレーションを行ってエラーが出なくて、これまでよりスコアがよければ解法2の解を採用、そうでなければ解法1の解を出すプログラムとして統合します。
100テストケースを試すと、ほんの少しですが平均スコアが良くなったので提出をします。
ついに、絶対スコアが3減りました。50個のテストケースのうち、3つのテストケースで、スコアを1減らせたということなのでしょう。
長かった…。
提出前の順位は88位でしたが86位に上がりました。そして推定パフォーマンスは1833から2042に上がりました。
やったぁ！
そして、疲れました…。
コンテスト3日目のことでした。
11.デバッグを続ける
バグをつぶすために、デバッグを続けます。
やっとバグを発見できました。
目標地点の記録が抜けていたせいでした。
と思ったけど、なんかまだずれていそう…。
これでいい？
ダメでした。
バグがなくなってもたいしてスコアが改善しなそうなので、別のアイデアを試したいと思います。
11.共通の規則を使用する（うまくいかない）
- 高速レーンを作っておく
あんまり短縮できなそう…
- 複数のルートを共通で使う
まず現在地を相対位置（0,0）として、目的地をプロットする。たとえばseed0ではこんな感じ。
マンハッタン距離の最小の頂点の距離の2倍未満に入る頂点をできるだけ多く入ったルートを作ること。出来上がったルートは少ない方が良い。
頂点を回る順番も関係ありそうだから、もう少し減らしてみようかな
プロットを見ていたらだんだんわかって気がします。
直線を同じ規則で繰り返して短縮することは点の圧縮、ジグザグを繰り返して短縮することがルートの短縮、そんな風に考えると、同じ規則のループを繰り返して移動するということができるような気がしてきました。
複数回そのマスを通るときは、次に通るときの（色、状態）に塗り替えておく必要があるので、追加で必要な規則になります。
これまでは盤面上で巡回ループを考えていたので見つからなかったようです。時間軸でのループを見つければよいのかもしれません。
そのマスでの時間経過で、1回目R→2回目L→3回目Rといった再訪パターンが一致するものは同じ遷移を用いることができそうです。
- 再訪がないマスは全て進行方向によって全て自己ループを使う
0 0 0 0 U
1 0 1 0 R
2 0 2 0 D
3 0 3 0 L
これを取り入れてみます。seed25の規則は143ターンが93個のルールであらわせました。10×10にできるので、スコア20になりそうです。
左右を繰り返す、上下を繰り返すものも、それぞれ一つの規則で済みそうです。
- R→L→R→L→…
最初の状態が0からなので、
- L→R→L→R→…
タイプもあった方が良さそうです。良く考えると再訪のないマスと合体できそう！
このアイデアは勝ったかもしれません。
まとめると、
- RLRLRLを繰り返す（Rだけも含む）ときは下記の規則を使用する。
- 0 0 0 1 R
- 0 1 0 0 L
- LRLRLRのときは下記の規則を使用する。
- 1 0 1 1 L
- 1 1 1 0 R
- DUDUDUのときは下記の規則を使用する。
- 2 0 2 1 D
- 2 1 2 0 U
- UDUDUDのときは下記の規則を使用する。
- 3 0 3 1 U
- 3 1 3 0 D
- 上記以外は１手１規則を使用する。
このようにしたいと思います。
seed25で各マスの訪問時の向きを調べた結果です。
[visits per cell: directions only]
cell(0,3) : D | type=DUDU
cell(0,4) : L | type=LRLR
cell(0,5) : L | type=LRLR
cell(0,6) : L | type=LRLR
cell(0,7) : L | type=LRLR
cell(0,8) : L | type=LRLR
cell(0,9) : R L | type=RLRL
cell(0,10) : R | type=RLRL
cell(0,11) : D | type=DUDU
cell(1,3) : D | type=DUDU
cell(1,9) : U U | type=bespoke
cell(1,11) : D | type=DUDU
cell(2,2) : R | type=RLRL
cell(2,3) : L D D | type=bespoke
cell(2,4) : L | type=LRLR
cell(2,9) : U U | type=bespoke
cell(2,11) : D | type=DUDU
cell(3,3) : D D | type=bespoke
cell(3,4) : U | type=UDUD
cell(3,5) : U | type=UDUD
cell(3,9) : U D R U | type=bespoke
cell(3,10) : L L | type=bespoke
（以下省略）
ほら、すごいまとまりそう。
（時間経過）
ダメでした。Dが連続するときに上に戻ってしまう…
DUDUDUになってしまった…
あ、なんかわかりそうな、わからなそうな…。
【まとめ】
- RLRLRLを繰り返す（Rだけも含む）ときは下記の規則を使用する。
- 0 0 1 0 R
- 0 1 0 0 L
- LRLRLRのときは下記の規則を使用する。
- 1 0 1 1 L
- 1 1 1 0 R
- DUDUDUのときは下記の規則を使用する。
- 2 0 2 1 D
- 2 1 2 0 U
- UDUDUDのときは下記の規則を使用する。
- 3 0 3 1 U
- 3 1 3 0 D
うーん、状態のつじつまが合いません。
12.コンテスト4日目：1回しか通らないマスを共通のルールを使う
先に
- 1回しか通らないマスを共通ルールにしたもの
を提出することにします。絶対スコアはベストを更新し、4545になりました。
順位表のトップを見ると、PrussianBlueさんがトップになっていました。
13.うまくいかない時間
先ほどウォーキングに行っている間に考察を続けていたのですが、自分の間違いに気がつきました。というか問題設定をわかっていませんでした。
- 状態は次に持ち越される
ということを。というわけで正しく書き直すとこれでよいのかな。
【まとめ】
- RLRLRLを繰り返す（Rだけも含む）ときは下記の規則を使用する。
- 0 0 1 0 R
- LRLRLRを繰り返す（Lだけも含む）ときは下記の規則を使用する。
- 1 0 0 0 L
- DUDUDUを繰り返す（Dだけも含む）ときは下記の規則を使用する。
- 2 0 3 0 D
- UDUDUDを繰り返す（Uだけも含む）ときは下記の規則を使用する。
- 3 0 2 0 U
Qの状態は全て0で行います。コードを修正しましたが、思ったより採用されません。
ビジュアライザを見ると、壁もないのに、今来た道と違う道で戻っていくのがわかりました。
- BFSで同距離のときは、前ターンと同方向優先、その次は、引き返す（180度反転）ことを優先するようにします。
seed25は63の規則にまで減りました。
これをC+Qが小さくなるようにするのですが、うまくいきません。qの状態を変化させると、衝突が起きてループができてしまいます。
Cの0から3までを全てベースに使用することにして、やっとバグが取れました。
しかし、上4行分、使っていないマスが多くでき、スコアを悪化させています。
q=0のベースのみを使うようにします。だいぶイメージに近くなってきました。
Cが小さいときは、Cを増やした方がC+Qが小さくなりそうです。右側にあるHeatmapビジュアライザがわかりやすくて、ありがたいなあと思います。
BFSのルートを
- 最短距離の中で一番ベースマスを多く通る
ルートにします。
うまくいかなかったので、
- q=0のみ状態から再スタートし、一列ができたら、q=0以外に振り分けます。
ベース（RL反復、DU反復、q=0でC=0からC=3に入れた）を使うために、その前でq=0にし、終わったらqを元の数値に戻すようにします。だいたい規則の数のルートくらいに振り分けて、C×Q-4が規則数以上になるようにします。
バグっています。
なかなか改善できないので、これ以降は、まずseed25のスコアがよくなることに全てを費やそうと思います。
順位表をみます。私は得点を更新できていないので、844人中170位に下がっています。
さて、下記で改善するかを試します
- ブリッジ規則 (c_bridge, 0) -> (a_next, s_next, d) は、(a_next, s_next, d) が同じなら色を共有できます。
- 非ベース規則 (c_here, q_in) -> (a_next, s_next, d) についても、(a_next, s_next, d, q_in) が同じなら 色 c_here を共有できます
- 橋やベースで q=0 に戻る境界ごとに分割し、各セグメント内の q_in 値を 1.. の連番に圧縮します。
（等価関係「次ステップが参照する q_in として同値」のみ保ち、値は自由にリネーム可）
14.コンテスト5日目から7日目：問題文に戻り、必要な色数と状態数について考える
全く理解が進まないので、問題文を読み直します。チューリングマシンとオートマトンについて読んでもう一度色と状態について考えます。
そして必要だと思った推移が下の20個。Cが5色、状態が4つです。
# ベース（色0自己ループ：URDL）
0 0 0 0 R
0 1 0 1 L
0 2 0 2 U
0 3 0 3 D
# 色1：右へ（どの状態で踏んでも R 状態=0 へ）
1 0 0 0 R
1 1 0 0 R
1 2 0 0 R
1 3 0 0 R
# 色2：左へ（どの状態で踏んでも L 状態=1 へ）
2 0 0 1 L
2 1 0 1 L
2 2 0 1 L
2 3 0 1 L
# 色3：上へ（どの状態で踏んでも U 状態=2 へ）
3 0 0 2 U
3 1 0 2 U
3 2 0 2 U
3 3 0 2 U
# 色4：下へ（どの状態で踏んでも D 状態=3 へ）
4 0 0 3 D
4 1 0 3 D
4 2 0 3 D
4 3 0 3 D
ビジュアライザを見ながら手でseed25の初期盤面を作ります。
（9,9）に来た時左に曲がりたいと思いますが、そういえば、ここは2回目なので、そのまま入れるとダメだと気がつきます。
このマスには、別の状態か色を定義して再訪の規則を作る必要がありそうです。
下記規則を入れて、あとは衝突しないように割り振りを行えばよいのでしょうか。同じ遷移（色、状態のペアが同じ）をするマスは共通の色セットを用いることとします。
- 自己ループ
- RL
- DU
- 交差点
- UL、DL、UR、DR
実装したプログラムを提出すると、絶対スコアは4541になりました。相対スコアは21.209,530,750、930人中211位になりました。
11.考察を進め、seed25のオートマトンを完成させる
seed25の規則は39個まで減らせています。C=39 、Q=1なので、スコアは40です。このCを状態遷移にうまく割り当てることを考えます。
かなり理想的な形になってきたので、ひたすらビジュアライザとデバッグ出力とにらめっこをしています。
さらに周期性からCを31まで減らすことができました。
これをCを減らしてQに振り分けます。
まずは、30ターンずつ重複しないように規則を取り出し、Qを1ずつ増やしていきます。境目の境界ではQを1増やす規則にします。
手で作った解になりますが、Qを5個に分けました。
12.コンテスト9日目：BFSのルートを改善する
コンテスト9日目、11月15日の朝です。順位表のトップにRafbillさんがいました。
私は228位。下がるのが早くなっている気がします。
- BFSの探索順を D, R, L, U に変更してみます。
良くなったり、悪くなったりしました。
- 順列で全通り試して、一番良いものを出力するように変更します。
思った以上によくなりました。提出をすると、久しぶりにほんの少しベストを更新しました。順位も少しだけ上がりました。
13.試行錯誤を続ける
夜のウォーキングに行って来たら、頭がすっきりとしました。
やっと、連続した規則の追加の仕方がわかったかもしれません。
- 今、状態１で３マス連続して左に進むとします。その後、状態２で、その３マスは連続して右に進んで戻ってくるとします 。
- これまでは（色５、状態１）→（色６、状態２）move「L」、（色６、状態２）→（色５、状態１）move「R」という規則を追加して、エラーが出ていました。
- しかしよく考えると、（色５、状態１）→（色６、状態１）move「L」という規則と、（色６、状態２）→（色５、状態２）move「R」という規則を追加すれば、 この３マスは同じ色とルールを適用できます。
- 例）連続して 状態１で右に進み 状態２で右に進む 箇所があります
- 15 1 3 1 R
- 16 1 4 1 R
- 17 1 5 1 R
- 18 1 6 1 R
- 19 1 7 1 R
- 3 2 15 2 R
- 4 2 16 2 R
- 5 2 17 2 R
- 6 2 18 2 R
- 7 2 19 2 R
- これは
- 3 2 15 2 R
- 15 1 3 1 R
- の２個にまとめることができます。手でビジュアライザの規則を修正します。無事ACする解に書き直すことができました。
これをプログラムで実装したいと思いますがうまくできませんでした。
14.コンテスト9日目：うまくいかない
2025年11月15日の朝です。コンテスト9日目、最後の週末がやってきました。もう一度整理しながらプログラムを書きます。
seed25を、周期をまとめて、ターンごとのデバッグ出力を出します。
==== Cyclic-merged pattern -> cells ====
PatternClass "D": 16 cells (0,3) (0,11) (1,3) (1,11) (3,3) (3,11) (4,3) (4,11) (5,3) (5,11) (6,3) (6,11) (8,3) (8,11) (9,11) (10,11)
PatternClass "DDL": 1 cells (2,3)
PatternClass "DDR": 1 cells (7,3)
PatternClass "DL": 1 cells (2,11)
PatternClass "DR": 1 cells (7,11)
PatternClass "DRL": 1 cells (9,3)
PatternClass "DU": 4 cells (10,2) (10,3) (11,2) (11,3)
PatternClass "DUL": 1 cells (9,2)
PatternClass "DULU": 1 cells (8,9)
PatternClass "DUU": 3 cells (5,9) (6,9) (9,9)
PatternClass "DUUR": 1 cells (7,9)
PatternClass "L": 11 cells (2,6) (2,7) (2,8) (2,9) (2,12) (10,5) (10,6) (10,7) (10,8) (11,10) (11,11)
PatternClass "LR": 10 cells (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (8,7) (8,8) (9,1)
PatternClass "LS": 1 cells (2,5)
PatternClass "LU": 3 cells (2,4) (2,10) (10,9)
PatternClass "R": 13 cells (2,2) (7,2) (7,5) (7,6) (7,7) (7,8) (7,10) (8,6) (9,0) (9,5) (9,6) (9,7) (9,8)
PatternClass "RU": 3 cells (3,9) (7,4) (9,4)
PatternClass "U": 19 cells (1,4) (1,10) (3,4) (3,10) (3,12) (4,4) (4,9) (4,12) (5,4) (5,12) (6,4) (6,12) (7,12) (8,2) (8,4) (10,4) (11,9) (12,2) (12,3)
シミュレーションを行います。
==== Per turn detail ====
t=0 pos=(5,9) dir=D
(5,9) raw=DUU, pattern="DUU" t=0, 残りの再訪ターン: 46 86
t=1 pos=(6,9) dir=D
(6,9) raw=DUU, pattern="DUU" t=1, 残りの再訪ターン: 45 85
t=2 pos=(7,9) dir=D
(7,9) raw=DUUR, pattern="DUUR" t=2, 残りの再訪ターン: 44 84 128
デバッグ出力を見ながら、自分の中でルールの追加方法を考えます。
- ターン１からルールを追記します。
- パターンが今の状態で登録してあるかを確認します。
- スタート地点は内部状態が0です。
- t=0 パターン”DUU”の場合、色０内部状態０ D ということで
- （０，０）（１，０）D というルールを追加します
- t=０の初期盤面は０を入れます
- ｔ＝１ パターン”DUU”なので すでに登録があります。
- 初期盤面には０を入れます
- ｔ＝２ パターンは”DUUR”なので 初期盤面は使用していないカラー１を使用して
- （２，０）（３，０）Ｄ というルールを追加します。
- ｔ＝３、パターンは”DULU”とまた新しいパターンなので 使用していないカラー （４，０）（５，０）Ｄ のように追加します。
- スコアを良くするため、途中で内部状態を変えます。Cの上限は、後から複数試す予定ですが、とりあえず、V=ルートTとします。使用カラー数がＶ以上になったら、
- （４，０）（５，１）と状態を変えたルールを追記します。
- その次からはカラー０に戻って、 （５，１）（０，１）のように足していきます。
- すでに登録したパターンでも 内部状態が変わって、そのまま使えないときは （１，１）（２，１）Ｄのように足します。
- 内部状態１でもカラー数がＶ以上になったら内部状態を２に変えます。
- 最後のターンまで行い 初期盤面の登録と 全ての規則を登録します。
- 使用したＣの個数、状態のＱの個数、ルールの個数Ｍを数えて、作成した初期盤面と Ｍ行のルールを書き出します。
- Ｖの値は、デフォルトをルートＴにします。
わりとよく考えたつもりだったものの、バグります。最初の訪問の移動と周期の開始位置はずれるので合わせる必要があります。
まずは
- ２つに分割することを考えます。
- 今ターン数が143なら、たとえば72手までを状態0、73手以降を状態1に割り当てます。
- 1回目、2回目が72手までなら1回目から2回目の状態遷移は0のままとします
- 1回目が72手まで、2回目が73手以降で出現するなら1回目は状態0、2回目は状態1とします
そんな風に状態を割り当てれば、衝突したり、状態のミスマッチが起こらずに、ルールの遷移を正しく書くことができそうです。
R、RR、RRRは自己ループにすると状態が変わることがあるので、最大の長さのRをパターンとすると良さそう。状態0の自己ループ、状態１の自己ループ等、全て用意しないとだめかも。
あー、論理破綻があると出力がWAになるのがつらい…。
しんどいなぁ。
ほぼ考察はできている気がするので、あとはプログラムが実装できれば…。
14.得点源
上位との差がついてきたので、50テストケースの相対スコアを調べました。貪欲集団のプログラムでトップと比較しました。
- N
- K
- 壁あり・なし
あまり差異はなさそうです。自分のプログラムが書き終えたら、また比較したいと思います。
15.うまくいかない時間
バグっていました。最初の訪問が状態0だったら、状態0への遷移を入れないとバグりますね。正しく遷移をする方法をもう一度書き直します。
- 前半は状態0から状態0へ遷移する
- 半分に分けた個所で１回だけ状態0から状態１への遷移を入れる。
- あとは状態１から状態１への遷移する
これで直ったはず！どうだ！
できました。（手で出力を修正）
２つの状態遷移がうまくいっています。
あとはプログラムを修正して、未使用の場所を詰めればCが31になり、スコア33になるはず。
これがうまくいけば、Cの色数を調整できるはずです。Cの色数はターン数の平方根にしたいと考えています。そうすれば、今のベストよりスコアをだいぶ縮められるはず。
違いました。
状態0だけど後から状態1で通る規則がある場合は色の変更NGですね。
まず、１文字はどこに動かしても良さそう。
うん、できました。
1 1 1 1 D
初期盤面の
色1を色2に変えて、規則を
2 1 2 1 Dに変更してもOK。
そうか。
- 遷移パターンが状態0と状態１をまたいでいるかどうか
で動かせるかどうか決まりそうです。
- 遷移パターンが状態0（前半ターン内）で終わる
ならばどこに移動しても良さそうです。
- 遷移パターンが状態１（後半ターン）で開始する
ならば、それもまたどこに移動してもよさそうです。
ああ、こんな複雑に考えなくても良さそう。「遷移パターンの最終の色」が変更しても影響がない色ですね。全て色0に移動させても良さそう。
全然色が減りません。
たとえば、パターン「DUU」と「RU」の「U」を同じ色が使えるようにしないといけないのかもしれません。まとめます。
- 色１を最終U、 色２を最終R、 色３を最終D、 色４を最終L として使います。
- これは自己ループを入れておきます。
- （１，０）（１，０）U
- （２，０）（２，０）R
- （３、０）（３，０）D
- （４，０）（４，０）L
- 色５から新規色として使います。
- パターンDは（３，０）（３，０）を使えばよいです。
- パターンDDRは色５→色６→色２にします。
- パターンDLは色７→色４にします。
- パターンDRは色８→色２にします。
今度こそ良さそうです。seed25は状態0のみですが、色の数は32個です。
16.コンテスト10日目：うまくいかない
コンテスト10日目、2025年11月16日、日曜日になりました。順位表のトップはbowwowforeachさんです。
私の順位は277位まで後退しています。青パフォも怪しくなってきました。
一番ターン数の短いseed93に変更して考察することにします。
初期盤面のスタート座標の色21が1回使ってその後全く使われていないことに気がつきます。
- １回しか使用しないルールである
- 連続したターンで使われている
- そのルールが使い終わりその色が再度出てこない
- 使い終わった色を再利用し、そのかわり状態を使っていないところに使用するルールを追加する
使用していない色を詰めます。
完成。
あ、UとUUを別パターンとして新規の色を割り振っていました。
全て同一色にします。
完了。
次にルールを4つ固定で足します。
- 1 1 1 1 U
- 2 1 2 1 R
- 3 1 3 1 D
- 4 1 4 1 L
これにより、さらに色の削減ができるはずです。
たとえば
- [sim] t=3 pos=(3,4) c=15 q=0 -> rule#15 (depth=3) : (15,0) -> (9,0) R
- [sim] t=4 pos=(3,5) c=2 q=0 -> rule#1 (depth=1) : (2,0) -> (2,0) R
- [sim] t=5 pos=(3,6) c=2 q=0 -> rule#1 (depth=1) : (2,0) -> (2,0) R
- [sim] t=6 pos=(3,7) c=23 q=0 -> rule#24 (depth=5) : (23,0) -> (22,1) R
- [sim] t=7 pos=(3,8) c=23 q=1 -> rule#29 (depth=4) : (23,1) -> (26,0) U
これですが、rule#15，rule#24、rule#29は１回だけの使用です。
このように変更すると、色23の使用をカットできます。
2つの連続したターンで行いましたが、3つ以上にも拡張できそうです。
- １回しか使用しないルールである
- 2つ以上連続したターンで使われている
- そのルールが使い終わるとその色は2度と使用されない
- 使い終わった色を再利用し、そのかわり状態を使っていないところに使用するルールを追加する
17.コンテスト最終日
コンテスト11日目、2025年11月17日月曜日です。今日がコンテストの最終日になります。順位表のトップはmontplusaさんです。
私は307位。悲しい。
最後まで、少しでも改善できるようにがんばりたいと思います。
- BFS経路を変えて、複数のマスで同じ訪問パターンができるようにする
経路を遠回りもＯＫにするようにしたのですが、うまくいきません。コンテスト時間は残り5時間半です。
状態を２つに分けることを考えます。
- まずはスタート地点は「S（移動しない）」を使って、状態0から状態1へ遷移します。
- 今あるルールを状態1にして移動を行います。
- 半分くらいの長さまで来たら、１回しか使っていないルールで状態１から状態０に戻します。
- 元からあった状態0のルールで移動します。
- 前半、後半ともに使われていたルールがあったら、状態１と状態０と両方に追加します。
ルール数は増えましたが、状態を２つに分けることができました。
２つにやる方法がやっと確立したので、パスの長さの平方根くらいに状態を分割することを試します。しかし、色を減らせる見通しが立ちません。
焼きなましでBFSのルートのswapを入れたらほんの少しだけスコアがよくなりました。
コンテスト残り時間が少なくなってきたので、2000テストケースを試します。
全てACしました。スコア平均は79.54でした。今の100テストケースの平均は71.38なので、軽いケースが100テストケースの中には多いのかもしれません。
残り時間、別のものを考えることにします。
seed25では17が出ました。
しかし、もう時間がありません。これまでのプログラムに統合する時間もなさそうです。疲れてしまったので、この参加記の公開もコンテスト終了時と同時にするのも間に合いそうもありません。
力尽きたのでここで終了します。この後は、体力回復に努めたいと思います。
お疲れ様でした。
16.最終結果
システムテストの結果が出ました。2000テストケース中、1ケースWAが出ていました。結果は、パフォーマンスは1589、順位は暫定時と変わらず322位でした。なお、参加者は1105人でした。
公式の解説タブにある詳細順位表をNで比較したグラフです。Nが小さい方が得点源でした。
17.終わりに
コンテスト期間中は根を詰めて取り組んでいましたが、結果が振るわなかったこともあり、精神的にも体力的にもすっかり消耗してしまいました。全てを放り出したい思いに駆られたので、気力と体力が戻るまで、しばらく競プロから離れることにしました。
では、なぜそんなにつらい思いをして続けているのかと問われれば、それでもやはり好きだからなのだと思います。今回のコンテストに取り組んでいた時間は、楽しかったかと聞かれれば、決して楽しい時間ばかりではなく、苦しい時間の方が多かったかもしれません。
それでも、マンガを読んだり、おいしいものを食べたりといった「何も考えずに楽しむ時間」だけで、自分の人生の残り時間を埋めたくはないと考えています。苦しかったとしても、コンテストに向き合っていた時間は、やはり自分にとって、とても大切な時間なのです。
少し時間が経つと気持ちも落ち着き、体調も戻ってきました。そして、やっぱり競プロから離れたくないと思い、またこの場所に戻ってきました。
これからは、こつこつと復習を進めていこうと思います。
18.復習
解説放送が2025年11月21日に行われました。これをもとに、復習を進めたいと思います。
