Skip to content

HACK TO THE FUTURE 2026(AHC056)

問題概要

  • N*Nマス(N=10〜20)の盤面があり、各マスには色を塗ることができる
    • 盤面には壁がある可能性があり、その場合、壁を超えて移動はできない
  • 盤面上にはロボットいて、K個の異なる目的地の列と上限ステップ数Tが与えられるので、Tステップ以下ですべての目的地に順番に訪れたい
    • Tは、最短距離で移動したときの総距離をXとして、X〜2*X
  • ロボットは、内部状態を表す変数を1つ持ち、現在のマスの色cと内部状態qから次の行動(A(c,q),S(c,q),D(c,q))を決定する
    • A(c,q): 現在のマスの色をA(c,q)に塗り替える
    • S(c,q): 内部状態をS(c,q)に更新する
    • D(c,q): D(c,q)方向(上下左右)に1マス移動、または、移動しない
  • 必要な色数と内部状態数をC、Qとして、C+Qができるだけ小さくなるような「遷移規則(A(c,q),S(c,q),D(c,q))」と「盤面の色の初期状態」を設計せよ

時間

  • 240 時間

個人的メモ

CQ表の形

  • 遷移規則の色cと内部状態qの表を、仮に「CQ表」と呼ぶことにする
  • スコアがC+Qになっているので、CQ表の要素数が最大になるのはC=Q(正方形)になるときで、正方形の方がよさそうに思われる
    • 例えば、C+Q=10だとして、C=1,Q=9だと要素は9個だが、C=5,Q=5なら要素は25個
    • また、正方形と考えた場合、スコアを1点減らすためには、sqrt(C)要素程度減らす必要があるので、結構減らさないとスコアが改善しなそうなことも予想される
  • アプローチによっては、同じ内部状態にしたい場合など制約があるので、正方形にならない可能性もある

後ろから構築

  • 移動経路が決まっている場合、経路の最後から考えると、次の色A(c,q)、内部状態S(c,q)、向きD(c,q)が確定しているので、機械的に決められる
  • ここで、割り当てる(c,q)をどうするか？には自由度がある
  • 色の割当によっては使いまわしができる可能性があり、スコアが改善しうる
    • qが最終的に0で終わるとは限らないが、適当に他の0以外のものと0を交換すれば良い

アプローチ

団子解

  • コンテストの初期から順位表で同じスコアで固まっているところがあった(順位が団子になっていた)
    • 最終順位だと365位あたり
  • 目的地へは最短経路で移動し、マスの移動では、毎回、色と内部状態を切り替える(かつ、使い回さない)
  • 最短経路での総距離をXとすると、2*sqrt(X)ぐらいのスコアになる
  • (解説放送) システムテストでは分裂してたみたいで、最終目的地付近での操作をいれるかどうかなどで微妙にスコアに違いがでてたみたい

後ろから構築をビームサーチ

  • 後ろから構築する時、割り当てる(c,q)には自由度があるので、「既存の規則を使う」「新規に規則を追加して使う」「CかQを拡張してそれを使う」などで探索
    • 未確定を許して、過去改変的にする感じが良いみたい
    • 評価関数は、C+Qや遠回り具合だけでなく、未確定マスの数やabs(C-Q)なども考慮すると良いみたい
  • 単純なビムサだと、盤面とCQ表を持つ必要があって重いので、差分更新ビムサでやる、など
    • (解説放送) mapを永続データ構造(rustはrpdsというライブラリがあるらしい)などで差分を持つなども

ベルトコンベア

  • 同じ経路を何度も同じ向きで通る場合、同じルールを使い回せる可能性がある
    • たとえば、壁の切れ目付近などは行ったり来たりで同じルートを通りやすい、など
  • そこで、ある程度の長さのパスをベルトコンベアと考えて、まず、色固定・向き固定で設置することが考えられる
    • 発展として、状態を変えて訪問ごとに向きを変えたりなども考えることができる
  • 向き固定の場合、ベルトコンベアを横切るような経路は取れないので、作るとしてもあまり長いベルトコンベアは作れない可能性がある
  • ベルトコンベアの形状や位置などいろいろ探索させたいところだが、全体のターン数が条件を満たすか？などは全目的地について最短経路を計算し直す必要があり、かなり重い
    • また、ベルトコンベアの設置数や利用回数が少ないと、たいしてスコアに影響しないので、見込みがあるか判断しにくい
  • 今回は、ベルトコンベアの設置として考えるより、後の「市松模様」や「氷の床」などで考えるのが考えやすく、上位では多かった模様

市松模様

  • 盤面を市松模様で考えて、片方を色0固定、もう片方は自由マスと考える
  • 色0マスでは、次も色0にしたいので、状態qの方を変えて侵入するようにすると、違う向きに移動できるようにできる
    • 「(0,q)->(0,q,向き)」のようなルール
  • 色0マスに目的地がある場合でも、次に動きたい方向になるように内部状態を指定すればよいので、ターン数は増えないような移動ができる
  • 移動経路中の半分ぐらいが色0固定マスになって、必要C,Qが抑えられる
    • 最短経路での総距離をXとすると、2*sqrt(X/2)=sqrt(2X)ぐらいのスコアにできる

氷の床

  • 市松模様の発展形で、盤面のほとんどを色0マスにして、少数のマスを切り替え用に使う
  • 移動経路中の多くが色0固定マスになるので、色0の利用率がかなり高くなり、かなりC,Qが抑えられる
  • 重要な点として、(市松模様での話と同様に)、あるマスから氷の床へ入るとき「進入方向」「滑る方向」が変えられるので、結構自由度(16パターン)がある
  • 切り替えマスの探索
    • 市松模様の場合と違って、ターン数を満たす、できるだけ訪問回数が少なくなるような切り替えマスの配置を見つける必要がある
    • ターン数は、前計算で、全マスについて他のマスまでの距離をBFSで求めておけばO(1)で求められる
    • 切り替えマスの訪問回数が少なくなるような移動は、ダイクストラしたいが、愚直にやると時間がかかるため高速化が必要
      • SIMD/ビット並列などで高速化
      • 移動可能なマスだけでグラフを作ってそれで探索
      • 01BFS
      • 到達可能か？の判定を先にしておく
      • など
  • 遷移規則の圧縮
  • その他
    • 色0だけでなく色1やそれ以上も固定マスとして使う
      • 複数の役割を用意する(反射、通過、回転)
    • 途中から固定マスにする

最大C,Q固定でビームサーチ

解説

(50位まで&発言を見つけられた方のみ)