- 0.はじめに
- 1.ルールの再利用（本番230位相当）
- 2.ルールの再利用を行い、BFSで既存のルールがあるものを優先する（本番237位）
- 3.市松模様（2マス1セットでの移動）と再利用マス（内部状態はmodで移動方向管理）（本番94位）
- 4.市松模様：ルールの配置を効率的に再度割り当てる（本番83位）
- 5.市松模様：modでの割り当てをやめる（本番79位）
- 6.終わりに
0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴5年11か月のかえでです。
これは、2025年11月7日金曜日19時から11月17日月曜日19時までの約10日間開催された「HACK TO THE FUTURE 2026 （AtCoder Heuristic Contest 056）」の復習記録になります。
復習にあたっては、公式の解説放送を参考にしています。
1.ルールの再利用（本番230位相当）
１ターン１規則を利用し、正方形になるようにCとQを利用した解のルールの再利用をします。
再利用の条件です。
- (a,s,d) が同じである
すなわち、
-
a … そのマスに来たとき 何色に塗り替えるか
-
s … 次の 状態 をいくつにするか
-
d … 次に どの方向に動くか（U/R/D/L/S）
が同じときです。プログラムとしては、
-
マスごとに「行動パターン」
(a,s,d)を計算する -
そのパターンが 既出なら、そのとき使った (c,q) を 再利用する
-
初めてのパターンなら、新しい (c,q) を割り当てて記録する
を行います。既出判定には、C++のunordered_mapを使いました。
また、C+Qの最小化のため、追加する規則は、1列終わったら1行、1行終わったら1列といった形で、CとQを交互に増やして正方形に近い形になるように、新規に使う(c,q)を割り当てました。
これにより、seed0では、再利用前のスコア64からスコア57に改善しました。
ローカルで試行すると、100ケース中2ケースほどバグっていました。提出した際も絶対スコアは389200と悪いものでしたが、相対スコアは本番230位相当まで上がりました。
2.ルールの再利用を行い、BFSで既存のルールがあるものを優先する（本番237位）
BFSで同距離の場合、既存のルールを使用できるものを優先します。しかし、結果は少し悪化しました。
3.市松模様（2マス1セットでの移動）と再利用マス（内部状態はmodで移動方向管理）（本番94位）
自己ループを複数回規則として使用していたので、色0に統一します。
と書いたものの、なかなかうまくいかずに苦労しました。
BFSのパスを作った後、ルートを後ろから2マスずつ処理していきます。
- 片方のステップは「色 0 用のベースルールだけで動かす」こととし、mod4で方向を制御する
- もう片方のステップだけ、個別の (c,q) を割り当てる（規則の再利用は行う）
色0マスに行ったとき、q%4 ベースルールで正しい方向に進み、さらに次の 2 手目の特殊ルールで再び戻ってくることを行います。
規則を割り当てる場所が足りなくなったら、色と内部状態のどちらを増やすかはCとQの数を比較して決めます。CがQ以下ならCを増やし、そうでなければＱを4つ（URDL分）増やします。
絶対スコア：3033
4.市松模様：ルールの配置を効率的に再度割り当てる（本番83位）
seed0の初期位置位置とルール使用回数のビジュアライザです。ビジュアライザを見ると、使用回数が0の灰色の部分が存在します。4列の状態q（4方向の移動）のうち、1列がいっぱいになると新しいCが足され、そこから他の列も開始するのが原因でした。
修正をします。下右図の使用回数を見ると、上詰めになっているのがわかります。
seed0のスコアも41から1減り、40になりました。
1列全体を使っておらず、スコアが悪くなっているテストケース（seed17）がありました。
修正をします。
提出をします。
絶対スコア：2910
5.市松模様：modでの割り当てをやめる（本番79位）
seed0のビジュアライザのルールの使用回数を見ると、下の方に灰色が多くあります。modで行き先を割り当てていますが、移動方向によって、使用ルール数にばらつきがあるようです。
modで4列ずつ足すのをやめて、足りなくなった移動方向だけ列を足すように修正します。
seed0はスコア37になりました。
絶対スコア：2827
6.終わりに
ここで一旦復習を終えたいと思います。解説放送の中で説明されていた市松模様での解法が、簡単でとても賢く見えました。しかし実際に実装してみると、想像以上に大変でした。何とか再現できてよかったです。なお、復習をしたのは解説放送で105位と書かれていた「市松模様+ルール再利用」です。
この問題は、「ルールの再利用」と、「C+Qが小さくなるようにルールを割り当てる」という2つの問題が解けないとスコアが伸びないという、とても難しい問題でした。ルールを再利用できる状態を把握するのが難しく、また、ルールを割り当てる方法も難しかったです。後ろから解を構築するというところまでは思いついていたので、コンテスト中、もう少しうまく立ち回れなかったのだろうかと思います。
とはいうものの、復習を重ねていけば、良い結果にめぐまれることもあるので、これからもこつこつとがんばっていきたいと思います。
