Skip to content

BrainPadプログラミングコンテスト2025(AHC046)

問題概要

  • N * N (N=20)のマス目からなるスケートリンクがある
    • リンクの外側へは移動できない
  • 初期位置から、順番に、与えられた目的マスに訪れるようにしたい
    • 初期位置を含め、全部でM(=40)地点が与えられる
  • 各ターンでは、以下の操作のいずれかを行える
    • 移動: 上下左右へ1マス移動する
    • 変更: 上下左右のマスにブロックを設置、または、ブロックを除去する
    • 滑走: ブロック、または、リンクの端にあたるまで滑走する
  • できるだけ少ないターンになるような操作列を求めよ

時間

  • 4 時間

個人的メモ

問題固有の性質

  • 「滑走」を使うと長距離移動ができるので、できるだけ滑走を使ってターン数を減らしたい
  • 「ブロックを設置」すると、滑走で滑りすぎないようにできるので、目的地までのターン数が減る可能性がある
    • ブロックの設置の仕方によっては、ブロックの除去なしでは目的地に辿り着けない配置になる可能性もある

最短経路の計算

  • ブロックの追加・削除を考えない場合、ある時点での目的地への最短経路は、4方向に「移動」か「滑走」をするBFSで求められる
  • 今回、ここにはいくつか高速化の余地があり、性能やアプローチの幅に影響する
    • 高速化については後述

ブロック設置なしでの最適解

  • ブロック設置を考えない場合は、順番に目的地へ最短経路を移動すれば、ブロック設置なしでの最適解が求まる
  • 順位表での204,033点解

ブロック設置について

  • 今回は、「いつ、どこに設置すると良いか？」が考察で進めるのが難しく、さっさと探索する方向でアプローチを考えるのがよかった
  • が、いくつかは改善に活かせる考察ができる

設置のタイミング

  • ブロックは基本的には早めに設置したほうが、活用できる機会は増える
    • 後半に設置しても、それを活用できる機会は少ない可能性
  • 最初に設置してからスタートするのがいいか、経路をたどりながら近くを通ったときに置くのがいいかなど、あまりどのタイミングで置くのが良いかは判断しにくい
  • 「目的地に到着したタイミング」は、必ずそのマスに止まっているはずなので、そのときに設置するなどはわかりやすいが、置ける位置が限られてしまう

設置の仕方

  • 「今いるマスの隣接マスに設置する」のが、設置のために1手増えるだけなので、効率が良い
    • 次の移動方向に設置してしまうと、移動の邪魔になる可能性もある
      • 同手数の迂回路がある場合は邪魔にはならない
  • 「今いるマスに設置」とか「狙ったマスに設置」は、移動(避ける)→設置と2手かかってしまったり、狙ったマスのどの4近傍から置きに行くかなどが増えてややこしい
    • 「移動経路上に置く(移動後に後ろに置く)」とかは、置ける箇所がかなり限られてしまう問題もある

設置場所、設置個数

  • 一応、以下などは考えられそうだが、あまり明確に良し悪しはわからない
  • 固定配置
    • 外壁付近へは「滑走」で一気に移動できる一方、盤面の真中付近へは「移動」で1マスずつ移動する必要があるため、中間や盤面中心あたりに配置したほうがよさそうに見える
    • ただ、盤面によって訪問点が異なり、使わない可能性のあるブロックをわざわざ移動経路から離れて置きに行くのは効率がよくない
  • 目的地の付近
    • 目的地は必ずそのマスに止まるので、その周辺に設置するのはわかりやすいが、置ける箇所は限られてしまう
    • また、どちらかというと、将来訪問する目的地の付近にブロックを設置できる方がうれしい
  • 連続した位置の配置
    • 隣り合うように配置した場合、どちらかだけでも、1手ずらせば使える可能性が高いので、あまりくっつく配置にならないほうが良い可能性がある
  • 同じ行・同じ列に並ばないように配置
    • 滑走を連続して使うなら、ブロックが同じ行・列にない(ずれて配置されていた)方が良い可能性がある
  • 設置個数
    • 滑走で止まれる位置が増えるのでブロックは多いほうがよさそうだが、設置にコスト(手数)がかかったり、滑走の邪魔になるので、そんなに配置はしないほうがよい可能性もある

ブロックの除去

  • 一度設置したブロックを除去するのは、除去にも1手かかるので、できればほとんど除去しないほうがよさそうに思われる
  • ブロックの配置によっては目的地に辿り着けない場合もあり得るので、そういう場合は除去は必要
    • 目的地のマスにブロックを置いていたり、周囲をブロックで囲ってしまっていたり、など

アプローチ

「これ以降ブロックを設置しない場合の最短手数」を評価値に貪欲/ビームサーチ/Chokudaiサーチ

  • 現在の状態からの操作としては、ブロックの除去を考えない場合は、移動(4方向) + 滑走(4方向) + ブロックの設置(4方向) = 12通りがある
  • それぞれの操作後の状態について、なんらかの評価値が得られる場合、ゲーム木探索が考えられる
    • 操作後の状態で一番よいものを選ぶ貪欲ができる
  • 今回、「これ以降ブロックを設置しない場合の最短手数」を考えると、これはBFSで求められるので、これを評価関数として利用できる
  • 前半に置きまくってしまったり、後からブロックの方が使われて前に置いたブロックが使われない、などが発生しうるため、設置数の制限や不要ブロックの除去、ビームサーチ化、BFSの同手数の別経路で試す、など改善の余地がある

設置位置を局所探索

  • ブロックの設置(したい)位置を決めて、移動中に設置できるときに設置する、というのを考えると、設置位置で局所探索ができる
    • BFSで最短経路を求めれば、各操作後に4近傍を確認して、置けるなら設置を追加すればよく、全体の手数が求められるので、これを評価値として使える
    • BFSでは同じ手数になる最短経路が複数でうると思われるので、できるだけ設置できる経路を選ぶほうが良さそう
  • 置こうとしたけど置けなかった、置いたけど使われなかった、などは除去しておくのが結構重要っぽい
  • BFSの計算がボトルネックになるので、高速化は考える必要はある
    • 探索回数が稼げないので、複数回山登りとか、無駄な配置をしない、など重要そう

中継地点を局所探索

  • 各目的地に行くまでの途中に、中継地点として＜位置, 設置方向＞を入れて、「中継地点に移動→設置」するようにすると、局所探索できる
    • 「中継地点にブロックを置く」と考えてしまうと、どのタイミングで置くかや置いた後の動き、滑走時の処理、などややこしいので、中継地点に移動後、その4近傍のどこかに置く、とするのがよかった
  • 中継地点への移動も同様にBFSできるので、最短経路で移動した場合の手数が求められ、評価値として使える
  • 近傍
    • ブロック設置の追加・削除
    • ブロック設置位置の移動
    • 設置タイミングの入れ替え、変更、swap
    • など
  • このアプローチの場合、他のブロック間の関連性や最後までの手数を見るので活用され具合が考慮されている
  • こちらも、BFSの計算がボトルネックになるので、高速化は考える必要はある

過去改変

  • 最上位はこのアプローチが多かった模様
  • ある地点にいるときに、「ここにブロックがあれば滑走が使えてよかったのに、、、」というのが考えられるので、過去改変したい気持ちになる
  • 任意のマスでブロック挿入を考えると、そこまで行って設置して戻るなど過去改変操作がややこしそうに思われるが、「過去の経路で置けたマス、かつ、その後の経路で通ってないマス」に限定すると、そのようなマスはメモしておくことができ、過去改変操作もそのタイミングで設置操作を追加するだけでよい
    • 遅延配置
    • 移動(4方向) + 滑走(4方向) + 過去改変ブロック設置 (+ブロック削除)を1手として貪欲/ビームサーチができる
  • 評価値はBFSでの最短手数以外にも、ブロック設置数(置いた数, 置ける数)、目的地までのマンハッタン距離/Astar、なども考慮できる

BFSの高速化

手数だけ必要な場合

  • 評価関数として使う(手数だけわかればよい)場合、最終出力以外は経路復元は不要
  • 山登りなどなら、現在手数よりも多くなる事がわかった時点で打ち切る

滑走先の前計算/メモ化

  • slide_to[y][x][dir]:=停止位置のような、(y,x)から方向dirに滑走したときの停止位置を前計算しておくと、BFSするときに滑走先をO(1)で求められる
  • ブロックを設置した場合は、そのブロックの4方向に伸びるマスの値のみ影響があるので、差分更新ができる

ビットボード/ビット並列

  • ビットボードを使うと、各地点における次の移動先をビット演算でまとめて並列計算できる
  • 「滑走」も、4方向について移動できなくなるまで動かすというのもビット演算可能で、移動は高々N回までなので、高速に求められる
    • 各行・各列をビット列で持って、clz(count leading zeros)/ctz(count tailing zeros)などでも

その他

AI利用

お絵かき

解説

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