Skip to content

estieプログラミングコンテスト2026(AHC068)

問題概要

  • https://atcoder.jp/contests/ahc068
  • N*N マスの盤面があり、外周は壁に囲まれていて、隣接するマスの間には壁が存在する場合もある
  • 各マスには、0からN^2 - 1の番号が書かれたカードがランダムに並び替えられて置かれている
  • 以下の操作を繰り返して、すべてのカードが順番に並ぶように並び替えたい
  • 操作は、「向き」と「長方形」を選び、長方形内部を2つのブロックに分けてブロックを入れ替える(注: 線対称ではない)、ような感じ
    • 向きは縦か横で、その方向にブロックを入れ替える
    • 向きに応じて、高さか幅が偶数であるように指定する必要がある
    • 長方形は、盤面内、かつ、壁がないように選ぶ必要がある
  • できるだけ少ない操作回数で目的の配置を達成せよ

時間

  • 4 時間

個人的メモ

端から揃える

  • 基本的には、壁がないケースで考えると、途中に動かせない(動かしたくない)マスが存在してしまうと、使える長方形が減ってしまうので、できれば端から揃えていきたい
  • また、端からでも、実際には壁があるため、一旦揃ったら確定させて動かさない、みたいなことをしてしまうと非連結になって詰むケースがある
  • おそらく(個人的には)結構重要なポイントで、「盤面真ん中付近からBFSして逆順に揃える」的なのが一番良かった模様
    • 適当にやると壁などによって細長い道みたいなのが残ってしまって、そこが効率的に動かせなくなってしまうので、できるだけ大きな塊が残るようにするのが良かった模様
    • https://x.com/terry_u16/status/2078425766824735126
  • また、距離タイ(か、同じぐらいの距離)のマスのどれから処理するか、とかの自由度もある
  • 中心の選び方
    • 適当に壁を考えずに真ん中付近のマスを選ぶ
    • 各マスについて、「最も遠いマスまでの距離」が一番小さいマスを選ぶ
    • など

アプローチ

1x2で移動させる

  • 長方形は最小で1x2で隣接swapができるので、目的のカードを1つずつ移動させることができ、全部揃えることはできる
    • サンブルがこれの0と1だけ揃えたものになっている
  • ただ、手数がかかるため、あまりスコアはでない

1xnで移動させる

  • (解説放送)
  • カードを目的位置まで動かすとき、1xnの長方形を考えると、1手で縦方向か横方向に長距離移動させることができる
  • これは単純にBFSなどすれば最短手順が求められるので、順番にそれを繰り返す

カードの目的地への移動方法を評価関数+ビームサーチ

  • 未確定のあるカードを目的の位置に動かす時、長方形の位置や形など自由度があり、それによって巻き込まれる目的のカード以外の動きに変化がある(副作用がある)
  • これを評価関数で評価しつつ、ビームサーチで一番よい動かし方を選ぶことを考える
    • 操作回数、目的カードの位置などに加えて、近い内に確定させる予定のカードの位置などを考慮することで、将来の操作回数が減るようにする
  • 使用可能な長方形を全部列挙したり、1xnベースの最短経路の長方形を拡張させて考える、など

過去改変貪欲

  • (解説放送)
  • 上記の1xnの拡張で、すべて操作列をそれまでの操作列の後ろに追加していく形にしていたが、これをこれまでの操作列の途中にも操作を挿入できるとした場合を考える
  • どこにどういう操作を挿入すると操作列の長さが抑えられるか？が問題になるが、それは「時空間BFS」で考えることができる
    • 長方形は1xnで動かす場合のみを考える
  • 時空間BFS
    • これまでの操作列に対して、今回動かしたいカードについて、dp[t][y][x]:=元の操作列での時刻tで目的のカードを(y,x)に持ってくるまでに必要な挿入数、を考える
    • ある時刻で、新しく操作列を追加する場合は移動先に+1で更新する、もし既存の操作列で移動する場合は+0で更新する、ことになる
      • これは01BFSなので効率的に処理できる
    • ただし、条件として、すでに確定させたカードが挿入によってズレてはいけないので、それが変わらないこと
  • 実際やってみると、盤面によっては、ターンが進むと使えるマスが減るとはいえ、ターン数が伸びるとBFSの探索量も増えてしまうため、TLEする可能性がある
    • 最後の方は途中に挿入しなくてもあまり末尾のみでもあまり操作列が多くならないため末尾追加のみで処理する、とか、挿入できるのは直近の500操作以内のみにする、など
mxnで移動させる
  • (解説放送)
  • 「1xnの長方形で動かす」を「mxnの長方形で動かす」に拡張したい
  • 1xnをベースに考えると、あるカードを移動させるとき、同じカードの移動を実現する長方形は移動方向とそれの垂直方向それぞれに自由度がある
  • そこで、既存の操作列の長方形で、目的のカードが含まれる/含まれないを考慮できるよう、長方形の形について自由度を持たせる
  • 「操作列への末尾追加のみ」で考える
    • 過去の長方形の形が変わると目的のカードの位置が動いたり動かなかったりするので、操作を追加する盤面において、複数の開始地点があり得る感じになる
    • 一番操作回数が少なくなるような、過去の長方形の修正＋新しく追加、を考えれば良い
  • 「過去改変」で考える

その他

盤面全体を評価関数で揃えるアプローチ

  • 単純に、各カードのターゲットとの距離(の2乗)とかの合計を評価関数として、最小化するように長方形を選ぶ、みたいなことは考えられる
  • 実際試すと、ターゲットマスの近くまでは移動させられるが、きれいに揃えるのが難しい
    • 揃える部分での"文脈"が強いので、探索が必要
  • そこから微調整をするとさらに手数がかさんでしまい、手数を下げるのは難しい
    • 行だけ揃えて、その行内は最短で揃える、みたいなこともできなくはないが、同じ行に揃えるのもあまり簡単ではないし、揃えるのに数手はかかってしまう
  • また、途中で揃ったカードがあると、それを含む長方形の操作は評価関数を悪化させる方向になりやすいので、自由度が減ってしまい扱いにくい

話題に出ていた類題

生成AI利用のルール

  • 今回は、生成AI利用ルール20250616版適用の最後の短期コンテストとのこと
  • これまでのに加えて、問題文の一番下や、(わかりにくい気がするが)コンテストのトップページの一番下に、AGENTS.mdなどへの追加指示文が追記されていた

ブロックswapではなく反転だった場合

  • (解説放送)
  • もし、ブロックswapではなく、反転(線対称に入れ替える)だった場合、壁がなければ、同じ行・列の任意の2点が2手でswapできる
    • 交換したい2つを端に含むブロックを反転し、その2つを除いた内側を反転する
    • 一応、ブロックswapの場合は、3手かかる
      • 交換したい2つを端に含むブロックをswapし、真ん中にその2つがくるのでswapし、もう一度最初と同じswapをする
      • 最初、ここらへんを考えてたけど3手が結構重く、使える感じではなかった

お絵かき

解説

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