AHC033 参加記

AHC033

トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）お疲れさまでした。

プレテストが49,558,778,478点で暫定2位でした。

5x5の盤面上で5台のクレーンを同時に操作して、左列の5つの搬入口から右列の5つの搬出口へ荷物を指定された順番で運ぶ問題でした。

荷物は5種類x5つの数字があり、各種類が各搬出口に対応していて、それぞれ数字が小さい順に運ぶ必要があります。

中央の3列は、荷物を一時的に退避するスペースとして使用することができます。

詳しくは公式の問題文を参考にしてください。

https://atcoder.jp/contests/ahc033/tasks/ahc033_a

seed=2 (seed=0は見栄えが悪かったので...)

おおまかな方針: ビームサーチ

クレーン1体の行動を1手とし、搬出完了までに必要な手数の下限をベースとした評価を行うビームサーチを行います。*1

ビーム幅は7000です。*2

行動

クレーン1体の行動を1手とし、番号が小さいクレーンから順に決めていきます。

本来は同時に行動するところを1クレーンずつ行動するため、

  • 自分より番号が大きいクレーンの居る位置への移動を許容
  • 他のクレーンと重なっているクレーンは、そのクレーンが来た方向とは別方向への移動を強制

とします。

爆破コマンド’B’は使用しませんでした。 必要になる場面はごく限られているのに対し、 評価関数の設計・状態遷移の実装が複雑になるのを嫌ったためです。*3

評価関数

評価関数は「搬出完了までに必要な手数の下限」とします。

極論、この評価関数が常に0を返したとしてもそれは「下限」ですが、それでは評価関数としては役に立ちません。

この「下限」は大きければ大きいほど真の残り手数との差分が小さくなり、評価関数として優れているといえます。

そのため、「互いに排反な」「将来確実に必要な手数」をなるべく多く足し合わせていくことで、下限を高めていくことが重要です。

搬出完了に必要な手は以下に分類されます。

  • 荷物を持っているクレーンが搬出口に近づく
  • 荷物を持っていないクレーンが次の荷物に近づく
  • 搬出可能な荷物を掴む、荷物を搬出口に置く
  • 退避が必要な荷物を搬入口から掴む、中央列に置く

上記は同時に1つまでしか実行できない、すなわち排反です。そのため、それぞれの必要回数を計算し、それらを足し合わせたものも下限となります。

荷物を持っているクレーンが搬出口に近づく

すべての荷物の搬出口までのマンハッタン距離の総和が下限となります。

クレーンが次の荷物に近づく

現在のクレーンから荷物までの距離のみではなく、各搬出口に将来発生するクレーンから荷物までの距離についても考慮したほうが良いです。

各搬出口に将来発生するクレーン数は、その搬出口の未搬出数となります。

例えば、以下のような状況の場合、

"以下のような状況"

各搬出口に上から順に4,4,3,4,5回ずつ搬出することになります。

搬出口に将来発生するクレーンたち

さて、「すべての荷物」に対して「現在/将来のクレーン」を最適に割り当てた時の、そのマンハッタン距離の総和が下限となります。

しかし、これを高速に求める方法は思いつきませんでした。

そのため、以下の2つの緩和をします。

  • X方向の距離だけ考えて、Y方向の距離は無視する
  • 全ての荷物を搬出後、全てのクレーンは左端まで移動することとする
    • すなわち、X=0に疑似荷物を5つ追加する

先ほどの図の状況の場合は以下のようになります。

搬入口の列にあるのは14個だが、疑似荷物5個を追加して19個になっている

この緩和の下で、全クレーンに対して左または同列の荷物を割り当てることができるならば、Xの距離の和は最小となります。*4

実際、現在のクレーン5つ(X≥0)には搬入口の疑似荷物5つ(X=0)を割り当て、将来のクレーン(X=N-1)には実在の荷物(X≤N-1)を必ず割り当てることができます。

その総和は、クレーンのX座標の総和 - 荷物のX座標の総和 で求められるため、差分更新も容易です。

ここでは、2つの緩和をしました。

1つ目の緩和はできればしたくないですが、高速な方法が思いつかなかったので仕方ありません。*5

2つ目の緩和については、緩和前の問題における最適解において、搬出完了後に左に動き続けるようにした解が緩和後の最適解になり、その逆も言えます。(多分)*6

搬出可能な荷物を掴む、荷物を搬出口に置く

未搬入の荷物の個数 * 2 + 置かれている荷物の個数 * 2 + 搬出準備済み*7の荷物を持っているクレーン数 * 1 + 搬出未準備の荷物を持っているクレーン数 * 3

を下限とします。

「未搬入の荷物」「置かれている荷物」は、最低でも掴むと置くの2手が必要です。

「搬出準備済みの荷物を持っているクレーン」は、最低でも搬出口に対する置くの1手が必要です。

「搬出未準備の荷物を持っているクレーン」は、退避の置くを行った後で、搬出準備ができてから掴むと置くの計3手が必要です。

退避が必要な荷物を搬入口から掴む、中央列に置く

「必要な退避の最小回数 * 2」を下限に加えます。

必要な退避とは、簡単な例だと「ある搬入口にに同じ種類の荷物が2つ存在し、数字が大きい → 小さい順に搬入される場合の、大きい荷物の退避」があります。

荷物2の退避をして、荷物1を搬出してからでないと、荷物2は搬出できない

より複雑な例だと、2つの搬入口が絡む場合もあります。

順序の依存関係がループしている

7を搬出するためには6の搬出必要で、6の搬入には2の搬入が必要で、2の搬出には1の搬出が必要で、1の搬入には7の搬入が必要で…と実行順序の依存関係のループができてしまっています。*8

これは「各搬入口から荷物を回収した回数」による65通りの状態に対して、「最小退避回数」をDPで求めておけばよいです。

「遷移先の最小退避回数 + 掴んだ荷物の退避が必要か」 から 最小退避回数を求めるDP

まとめ

以上をまとめると、評価関数は以下の総和になります。

  • 荷物
    • ゴールまでのマンハッタン距離 - X座標 + 掴む離すの必要回数
    • 掴む離すの必要回数は、
      • 置いてあるなら2
      • 掴まれていて、搬出準備済みなら1
      • 掴まれていて、搬出未準備なら3
  • クレーン
    • X座標
  • 搬入の状態
    • 最小退避回数 * 2
  • 搬出の状態
    • 未搬出の荷物数 * (N-1)
      • 将来出現するクレーンのX座標に対応

多様性確保

状態のハッシュ化にはZobristHashを使用しています。 その際、厳密には違う状態であっても、 似た状態はあえて区別しないことで、 状態の多様性を確保しています。

各状態について、以下の要素が一致する状態には同一のハッシュが割り当てられます

  • 各行ごとの(大クレーンの個数, 小クレーンの個数)
  • 各搬入口ごとの搬入した個数*9
  • 各搬出口ごとの搬出した個数
  • 中央列(0列目と4列目以外)の置かれた荷物の有無

以下は考慮・区別していないことに注意してください。

  • IDの異なる2つの小クレーン
  • クレーンのX座標
  • 0列目に置かれた荷物の有無
  • 各位置に置かれた荷物のID

「各搬入口ごとの掴んだ個数」「中央列(0列目と4列目以外)の置かれた荷物の有無」の良さが評価値に反映されるまでには遅れがあるため、ビーム幅の多様性はなるべくこれらに当てたいです。

*1:正確には下界でしょうか。

*2:幅8000でもACしていたんですが、提出ごとの分散が激しく、1位とも点差が開いていて逆転が難しそうだったため、日和ました。

*3:要するに面倒だったということです。ここまで僅差ならやったほうが良かったんだろうか。

*4:証明略

*5:例えば横方向と縦方向を独立に考えて、縦方向も貪欲な割り当てをやろうとすると、「荷物が左上と右下にある」「クレーンが右上と左下にある」というケースが評価値良くなって困りました。

*6:例外あったら教えてください。もちろん、適宜上下に移動する前提です。

*7:同じ種類の自分より小さい荷物がすべて搬出された荷物のこと

*8:「運んでいるうちに追いつく」というケースもありますが、考慮してないです。

*9:盤面に出現したうえで、クレーンが掴んだら、搬入したとみなしています