AHC 038

 

 

AHC038 に参加しました *1 。

プレテスト 8.6B で暫定 318 位です。

 

ぱっと見解法

• 見るからに Robot Arms
• フローっぽいがいろんなフローがある
• 点集合が固まっていたらルールベースでも強そう？

 

 

最初のアイデア

 

上位勢の最終解法を想像すると、かなり無駄がないだろうと予想。「持ち上げる」→「回転・移動」→「置く」は基本的に 2 ターンで行うぐらいを目指す必要がありそう *2 。これは逆に 2 ターンで行けるやつをマッチングすればある程度いけるはず。

 

限定

クレーンの形状

このままだと考えづらいので、まずはクレーンの形を次のものに限定する。

• 根から直列にいくつか関節点をつなぎ最終点を「基準点」とする
• 基準点から直接行ける点に子（葉）を配置する

これにより、「基準点とその子たち」を移動する問題だと考えることができる。

 

タスク分解

• たこ焼きを持ち上げる・置く操作は最小限にする
  • つまり、「初期配置にありかつ最終配置にないもの」のみを移動させる
  • 各たこ焼きは（途中置き場に置くことはせず）直接最終配置まで持っていく
• 「持ち上げる」→「回転・移動」→「置く」を 1 セットとして、この単位で行動する
  • つまりあるたこ焼きを持っている状態で追加で別のたこ焼きを持つことは考えない *3
  • 複数のたこ焼きを持っている状態から一部だけを置くこともしない

 

また最後の限定により、やるべきことが小タスクに分解される。これらは任意の順番で行うことができるので、（有向） TSP に帰着できる。

 

平行移動

• 基準点および子たちは、平行移動のみを考える

言い換えれば、各タスクでは基準点から先の子側の形（基準点からの相対座標）は持つ時点と置く時点で変えない。これにより、移動前後の点集合が固まっている場合など、無駄なくきれいに移動できる可能性が上がる（全体を平行移動できるので） *4 。

 

 

 

なお、根は定義上は葉になるが、根で持ち上げる・置く操作は行わないこととした。

 

最初の実装

最初のサブミッションでは上述に加えさらに次の条件で実装した。

• クレーンの根から基準点までの辺を 2 つとした
• 基準点から各子までの距離は、可能な数を として とした

 

2 辺の長さを決める

基準点までの辺 2 つの長さ（ ）を決める。

辺の長さを固定すると、移動前の各点から移動後の各点までの移動回数が求まる *5 。移動前のたこ焼きの集合と移動後のたこ焼きの集合のマッチングのコストを最小費用流で求めることができる。 を全探索してマッチングコストが最小になるものを選んだ。

 

移動ベクトルごとに分解

上述の限定では、移動ベクトル（ ）が同じものは一気に運べるので、最もよく使われている移動ベクトル（これはひとつ前の結果を使用）に属する点が多い方が嬉しい。

これを考慮して最小費用流でマッピングする。

 

図示すると以下の通り。

各文字 X に対して、黒文字 X から白文字 X の移動は平行移動になっている（のでまとめて移動できる）。

 

A だけ見るとこんな感じ。

各移動ベクトルを 1 回で運べる量に分割しタスク化

例えば A の点たちを、いくつかのグループに分け、各グループの点はそれぞれある代表点から の長さであるようにする。

すると、問題は代表点の移動というタスクに分解できる。

 

TSP

各タスクはタスク開始時・終了時の状態（根の位置および各頂点の相対角度）が分かっている。

よってこれは有効辺 TSP に帰着できるので、適当に焼けば良い。

 

 

フローでできそうなこと

 

いろんな段階でいろんなフローが使える。使えなかったものも含めてめも。

• どの点をどの点に持っていくかというフロー
  • 点から点へのコストを決めれば最小費用流で厳密解が出せる
  • 点と点を結ぶだけでは直接解法にならないので、本稿で紹介したようにマッチングの際などに使う
• どの代表点をどの代表点に動かすべきかというフロー
  • 代表点から代表点への移動のターン数を前計算することで、マッチングした際に動かすターン数は最小費用流で厳密解が出せる *6 
• 基準点の動きを決めたあとに、どの点を移動させるべきかを決めるフロー
  • 基準点の動きを決めた際に移動させられる点の個数は最大流で厳密解が求まる
    • これは上述の平行移動限定に限らずできる
  • 他の解法で作ったあとも、最後に 1 つ除いていけるかなど使えるかも

 

 

感想

今回はいい解法がなかなか思いつかず、後半に予定があったこともあり、モチベが上がらなかった（言い訳）。

 

どちらかというと今後にも使えることをやろうと思い、いろいろ試していた。

• 提供されているツールの使用
  • 「Windows用のコンパイル済みバイナリ」を使って Score を計算することにした
• Copilot
  • これまで競プロには Copilot を使っていなかったが、使うようにした
  • アルゴだとあんまりいらない気もするが AHC だとかなりラクになった
• クラス化
  • いつもよりクラス化して書いてみた（途中迷走したのできれいではない）
• ChatGPT
  • Python から聞けるようにした（けど AHC に使うところまで行けなかった）
  • 実行環境と連動させるのをやろうとしていた（断念した）

 

最初に上位を狙える方針を考えてからその方向に進むというのをやりたいところだが、今回はそれが見つからず何もできず終わるというパターンになってしまった。（1 手で結べるものをマッチングするのはワンチャンあるかと思ったけど実装したらダメなことが分かった。）

コンテスト後に TL で上位解法を見るとビムサなどの探索が多いのでどのみち苦手回だったか・・・。

 

End