https://kiri8128.hatenablog.com/entry/2024/05/27/204353

AHC 033

プレテスト 47 位でした。

Seed 0 （83 点）

やったこと概要

雑貪欲です。

タスクの優先度を決めて、優先度が高い順に貪欲に動き方を決める
具体的には、時刻と位置の組 $(t, i, j)$ （以下、単に「 $3$ 次元テーブル」と呼びます）のうちどの部分を占領するかを決める
これをたくさん繰り返す

前提（自主制約）

問題を簡単にするために、自主的な制約として次を設定する。

各コンテナは、搬入場所と搬出場所を除く中間位置には高々 1 回しか置かない
25 マスのうち下図のマスを一時置き場にする
- これにより、搬入場所→一時置き場、一時置き場→搬出場所の移動が必ずできる
搬入場所から移動するときは、最初は必ず右方向に移動する（搬入場所内で上下には移動しない）
- 搬入場所（左端のマス）で上下に動くことを許すと、新しいコンテナが出現してほしくない場合に出現させないようにできるなどメリットがある
- 一方で私の方針だと実装がややめんどいのでラクすることにした

最適化方針

コンテナの搬出の順番（優先度）を決める
優先度の高いものから運び出すこととすると、「直接搬出場所に移動できる」か「一時置き場に避難する必要がある」かが自動的に決まる
8 個の一時置き場のどの位置に置くかを適当な評価関数で決める
これにより、やるべきことは「コンテナ $x$ を $(i_1, j_1)$ から $(i_2, j_2)$ に移動する」という形のタスクに分解できる
タスクの優先度は、適当な評価関数で決める
優先度の高いタスクから順に下記を行う
- 最適なクレーンを選び、そのクレーンでタスクをなるべく最短で行う（そのために必要な $3$ 次元テーブルを埋める）
- この判定は DP で簡単にできる
最初のステップ（搬出順）を変えて上記を繰り返す焼きなまし
- 近傍は、隣接タスクの入れ替えと、あるタスクを可能な限り早く・遅くする、の $2$ 種類
- 数百回しかまわらないし毎回一から貪欲してるので焼きなましと言えるかは謎

ビジュアライザ

現時点の状況だけでなく、各クレーンがどのように動いているか（止まっているか）を認識したかったので、現時点の状況と全体の動きの両方が見えるようにした。

ビジュアライザは、動くやつを見ても訳わかんなくなるので、コマンドを並べて無駄な動きをしていないか確認してた。

・止まっている
・不要に上下に動いている
・取りに行くときに右向きに動いている

が 3 大無駄な動きhttps://t.co/URTXxqwTIU pic.twitter.com/bh0MDb4Qnh
— きり (@kiri8128) May 27, 2024

相対スコア記事について

コンテスト前に相対スコアの立ち回り記事を書いていたところ。

kiri8128.hatenablog.com

ごめんなさいポイント

記事では、「相対スコアを導入する場合は、ケースによって得点の取りやすさが大きく異なることが多く、単純平均や絶対スコアは全く参考にならない」という話が趣旨のひとつで、その説明のために様々な理論や例を持ち出して説明しました。しかし今回の AHC 033 に限っては、実はどんなケースでも得点の取りやすさはそんなに変わらない（トップ勢のスコア比率は通常 10～20% 程度以内、どんなにひどくても 2 倍になることはまずない）設定だったので、実は絶対スコアの単純平均や対数平均でも十分良い指標になる回でした。

もちろん、記事の趣旨を正しく理解した方は、問題設定を読みどの指標が使えるかを考えることが重要と理解されているはずなので問題なかったかと思いますが、結論のみに注目するとややミスリーディングになったかもしれません。コンテスト開始 $5$ 分でやべーと思ったんですが、さすがにコンテスト中に記事を修正する訳にもいかないので残りの $239$ 時間 $55$ 分はごめんなさいという気持ちで過ごしていました。