HACK TO THE THE FUTER 2026 (AtCoder Heuristics Contest056) 参加記
0. はじめに
2025/11/7 〜 2025/11/17 に開催された「HACK TO THE FUTURE 2026（AtCoder Heuristics Contest 056）」 に参加しました。 せっかくなので、参加記として記録を残しておきます。
HACK TO THE FUTURE 2026 （AtCoder Heuristic Contest 056） - AtCoder
まず、このような挑戦的で面白い問題を用意してくださった AtCoder さん、 そしてスポンサーとして支えてくださった Future さんに深く感謝いたします。
今回の実装に使用した言語は Python3（提出時は PyPy） です。 最終順位は 114位 でした。
成績詳細： https://atcoder.jp/users/LyricalMaestro/history/share/ahc056
※ キャプチャはseed=0にこのコードによる解法を適用させたものです。
1. 問題概要
問題文： https://atcoder.jp/contests/ahc056/tasks/ahc056_a
この問題では、内部状態を持つロボットを制御し、複数の目的地を順番に巡回させることが目的です。 ロボットは以下の 2つによって行動が決まります。
- 内部状態（inner state）
- 現在立っている床の色
この 2つの組み合わせに応じて、ロボットは次の動作（遷移規則）を行います。
- 床の色を塗り替える（同色でも OK）
- 内部状態を別の状態へ遷移させる（同一でも OK）
- 上下左右またはその場に留まる、のいずれかへ移動
◆ 設計するもの
参加者が設計すべきは以下の 2点です。
- 初期の 床の色
- 内部状態 × 床の色 → 動作 の遷移規則
これらを工夫して 決められたステップ数以内に、目的地をすべて巡回させる 必要があります。
◆ スコア
スコアは
内部状態数 + 色数
で決まり、これを なるべく小さくするように設計する のがコンテストの本質です。
2. 最終的な私の解法について
私の最終的な解法は、大きく次の 3 つのアイデアに基づいています。
目的地 N → 0 の逆方向に経路を構築する 色遷移の履歴を後ろから確定することで、前半区間の矛盾を防ぎ、 “序盤はまだ何も決まっていないので自由／終盤は確定した履歴に従う” という構造が自然に作れる。
進行方向は「内部状態」、曲がり動作は「色」で表現する 内部状態 = {上・右・下・左} 色 = {直進・左折・右折・バック} と分離することで、 同じ色＝同じ行動 を保証し、色数を大幅に削減できる。
ペナルティ付き BFS による経路の最適化 と “かさ増し” による状態・色の最適化 “色を増やしやすい行動” ほど重いペナルティを与え、ペナルティ最小の経路を BFS で探索する。 さらに、内部状態を方向 × かさ増し数 に拡張することで、同じ色を再利用しやすくし、スコアを下げる仕組みを作った。
この 3 つを組み合わせて
- 逆向き探索で矛盾のないルートを作る
- 色割り当てをシミュレーションして必要色数を見積もる
- “かさ増し数” を調整しながら内部状態で色変化の余地を確保
- 最後に遷移規則と初期の色を生成
という流れで最終提出に至りました。
以下では、この解法の詳細を説明していきます。
2.1 逆向きに経路を探索する方針
通常は 出発地 → 目的地1 → 目的地2 → … と順方向に作りたくなりますが、そうすると
- 最後に必要な色を先に知れない
- 序盤で決めた色配置が後半で破綻しやすい
- “最終的な色遷移履歴” を全部予測しながら実装する必要があり複雑化
と問題が多いです。
そこで今回は 目的地 N → 目的地 N−1 → … → 出発地 という逆方向で処理することにしました。
メリットは以下の通りです。
- 最後に必要な色がすでに確定している状態から構築できる
- 前の区間に対して “後の結果の矛盾” が起きない
- 序盤（出発地付近）は自由度が高いので楽
2.2 方向 = 内部状態、曲がり方 = 色 の分離
ロボットの行動は「進行方向」と「行動の種類（直進/曲がり）」が混在しており、それを色だけで表現しようとすると
- 同じセルでも進む方向が違うと色変更が必要
- 同じ色が別の意味を持ってしまう
- 色の増加につながる
という課題がありました。
そこで私は次のように分離しました。
● 内部状態：常に“どの方向へ進もうとしているか”
- 0 : 下
- 1 : 右
- 2 : 上
- 3 : 左
● 色：どんな動作をするか
- 0 : 直進
- 1 : 左折
- 2 : 右折
- 3 : バック
この分離により、 - 色を変えずに方向を維持できる（直進が色0だけで表現できる） - 曲がり方を変えたい時だけ色変更すれば良くなる
というメリットが生まれ最終的な必要な色数を減らしやすくします。
2.3 ペナルティ付き BFS による“色を増やしにくい経路探索”
基本方針は、 なるべく曲がらない・色を増やさない経路を優先する BFS です。 そのため、移動ごとに以下のペナルティを設定しました。
penalty =
+1 : 未塗り床で曲がる
+3 : 新色を使わないが、まだ規定していない内部状態での遷移
+6 : 新しい色が必要になる場合
- 直進 or すでに確定した色の行動 → ペナルティ0
- 変な動きをするとペナルティが大きくなる
この構造によって “自然と色数を抑えた経路” が BFS で見つかるようになっています。
さらに、最短距離 + 割り当て可能な余剰ステップ数を上限に設定し、最短距離より少し遠回りでも色の増えない経路を許容しています。
2.4 経路確定後の色割り当てシミュレーション
各区間の経路が決まったら、その経路に沿って
- 色が既定されているか
- 状態遷移が一定か
- 新しい色が必要か
などを 1ステップずつシミュレーション します。これにより 経路全体辿るのに 必要となる色数 が分かります。この情報を後の「かさ増し数」の決定に使います。
2.5 “かさ増し数” の導入（Key Idea）
スコア = 状態数 + 色数 なので、実は状態数を増やすことで色数を減らせる構造になっています。
そこで、内部状態 = 進行方向（4つ） × かさ増し数（X）
という形で内部状態を拡張し、
- 色変更のたびに「どのかさ増しindex」を使うか選べる
- 色の再利用性が上がる -結果としてスコアが下がる
という仕組みを作りました。
かさ増し数 X は X−3〜X の範囲で全探索 し、 最も良いスコアになるものを採用しました。
2.6 全体フローまとめ（図なしでも理解できる形）
最後に、解法全体をまとめると次のようになります。
(1) 全区間で最短距離を計算
(2) 余剰ステップを区間に割り当てる
(3) 目的地 N → 0 の逆向きで以下を実行 3.1 ペナルティ付き BFS で経路探索 3.2 経路に沿った色割り当てシミュレーション
(4) 必要色数から“かさ増し数”を推定
(5) 内部状態 = 方向 × かさ増し数 で遷移規則を構築
(6) 通らない床は0で塗る
提出コードはこちらになります。
3. 所感
今回は本当に最後の最後で 黄色パフォーマンス相当 の精度まで到達できてよかったです。
ただ、振り返ると
- もっと早く方向=内部状態という発想に気づいていればビームサーチや焼きなましなどと組み合わせて“重なりの少ない色割り当て” を探索できたのでは？
- 色割り当て部分はもっとヒューリスティックを入れる余地があった
- 終盤は睡眠が崩壊した（朝7時までやって3時間寝る生活…）
など、改善ポイントも多かったです。
なお、今回は 本番用コードの生成に AI エージェントは一切使いませんでした
また次回のAHCもいい成績を残せるように頑張りたいと思います。
GW5日目~平成から令和への橋渡し期間~
令和最初のブログ。
続きを読むGW2日目~平成から令和への橋渡し期間~
4/28(日)の記録。
お昼に起きてひたすら掃除でした。主に引っ越しのときに残していた段ボール整理。 成果としては7~8コ潰すことができました！
それのついでにいろいろ物を整理していたら2年前のGoogle I/OでもらったGoogleHome(技適通る前?)のものを発見。
結局大切に袋にしまったままで何も使っていません。 GW以外の機会にどこかで使いたい。。
