AHC065参加記・1位解法

本記事はAtCoder Heuristic Contest 065(AHC065)の参加記です。
今回、初めて念願の1位を取ることができたので、記念も兼ねてコンテスト中に考えていたことを書いてみようと思います。

問題概要

$N\times N$マスの倉庫にベルトコンベアを設置・操作し、倉庫に置かれた箱を番号順に搬出口に運ぶ問題です。

• 各ターンで1つのコンベアを1マス回転
• 搬出口に最小番号の箱が来ると自動で搬出
• 長さ2以上のベルトコンベアを最大$N^2$個まで設置可能
• 各マスを通るベルトコンベアは高々2個まで

上記条件のもと、できるだけ少ないターン数ですべての箱を番号順に搬出することが目的です。詳細は問題ページを参照してください。

コンテスト序盤

問題についての第一印象

ベルトコンベアの「設置フェーズ」と「操作フェーズ」の2つを考える必要があり、短期の割には複雑な印象を受けました。
まずは確実に全部を運び出す解法を考えてみました。
以下のように縦移動用と横移動用のベルトコンベアを、2行・2列単位で設置し、小さい番号の箱から順番に縦コンベアで0行目に移動したあと、横コンベアで搬出口に移動する方法を考えました。

この方針を考えながらベルトコンベアの設置条件を読み返していると、以下の2点が気になりました。

• 最大設置数は$N^2$個
• 最小の長さは2

縦横コンベアの方針だと、コンベアは$N$個しか使っていません。最大設置数は$N^2$個ということは、各マス専用のコンベアを作れるくらいの制約に見えます。しかし各マスに最大2個しか設置できないことを考えると、その場合は「長さ2のコンベア」を大量設置することになります。
長さ2のコンベアは、動きとしては2マスのswapになります。swapを繰り返して最短手数を目指す問題なのだろうか、でもそんなことができるのだろうか、というのが第一印象でした。

縦横コンベア方式の実装

他に良いアイディアも思いつかないため、まずはこの縦横コンベア方針を実装することにしました。コンベアのローテーションや倉庫の状態管理を部品化しつつ、単純なルールベースの実装をしました。

• まずは箱の列にある縦コンベアで0行目に移動
• 0行目に到達したら、搬出口方向に横コンベアを動かして搬出

横コンベアは全行設置していましたが、一番上のコンベアしか使わない解法が完成しました。ここまでで55分かかりました。
昨今のAHCでは生成AIを使いこなして短時間で実装する方も多いようですが、筆者はあまりうまく活用できておらず、いつも中途半端に使おうとして失敗するので、今回は人力コーディングに徹しました。

コンテスト中盤

方針再検討

作成した縦横コンベア方式をテストしてみると、ターン数は5800〜6100程度、提出時点では200位前後でした。
箱は1個ずつ平均約15手かけて搬出口に運んでいる計算ですが、特定のベルトコンベアを動かした際、半数の箱は搬出口に近づく一方、残り半数は遠ざかってしまうのがいかにも無駄っぽいです。ここからどう進めるか、いくつかのアプローチを考えました。

アプローチ1：搬出ルートの工夫による手数節約

中盤以降に箱が減ってきたタイミングで、搬出口から遠ざかる箱がなるべく少なくなるように動かすコンベアを選んで節約を図る方法です。
搬出口までの総距離を評価値にして、ビームサーチ等で効率的な搬出順を探すような方向が浮かびましたが、結構実装が大変そうなので一旦保留しました。

アプローチ2：ソート方式

次に、近い番号の箱をまとめて一気に運べないか、という方向性を考えました。例えば、盤面全体にハミルトン路の長いコンベアを1本作っておいて、それとは別に隣接レーンの箱を入れ替える「長さ2のswapコンベア」を大量に設置します。このswap操作をうまく使って、ハミルトン路上の箱をソートするイメージです。
距離2,4,6くらいの近い位置のswapだけでなく、半周くらい先とのswapもできるようにハミルトン路やswapコンベアをうまく設定できれば、比較的短手数でソートできるのではないかと考えました。
ただ、この方針だといい感じのコンベア設置を考えるのも大変そうですし、どのswapコンベアを使って入れ替えるのが得かのビームサーチみたいなことが発生しそうで、短期コンテストの中で実装できそうな気がしませんでした。ソートも完全にはできないことも想定されるので、最終的にメインコンベアを進めつつたまに戻る、みたいな操作も必要になりそうなのも複雑そうです。
最近の短期コンテストでは欲張った方針を立ててしまって実装しきれずに終わるということが続いており、この方針はやめた方が良さそうと判断しました。

アプローチ3：巡回搬出コンベア方式

ソート方式だと、メインコンベアに全部載せたまま、設置したswapコンベアのみを使ってソートを目指すということで、制約が強すぎる感覚がありました。
もう少し制約を緩めて、より安定して一括搬出できそうな方法を模索しました。
そこで思いついたのが、盤面の外周に巡回式の搬出用コンベアを設置し、そこに番号順に箱が並ぶように載せていくというアイディアです。搬出用コンベアの各マスに何番の箱を載せるかをあらかじめ決めておき、搬出口に向かって少しずつコンベアを動かしながら、各番号の箱の最寄りに載せるべきマスが来たら載せる、という動きができれば手数を大きく節約できそうです。

アプローチ4：改良版巡回搬出コンベア方式

「アプローチ3」が仮に完成した場合、箱1個あたりにかかる手番は巡回路である外周までの平均距離(想定：4〜5手)になることが期待されます。（それに加えて、巡回路を回すのに箱1個1手かかることになります）

この見積もりを考えたとき、「巡回路までの距離をもっと短くできればもっと良い解になるのではないか」と思い至りました。
ハミルトン路のように全マスを通るのではなく、少し隙間を空けた巡回路を作れば良いのではないかと思いました。

そこでExcelを起動して、すべてのマスから1手で巡回路にたどり着けるような配置を検討しました。

この方式がうまく実現できれば、どの箱も1手で巡回路にたどり着けるので、相当なスコア改善が期待できます。

方針の深掘りと実装

上記で考えた巡回路は全マスを距離1でカバーできています。ということは、コンテスト開始時におぼろげに思っていた「長さ2のコンベア」を大量配置する方向性が見えてきて、想定解に近づいている手応えもあります。
そこで試しに長さ2のコンベア設置案も書き足してみます。

このコンベア配置を元に、具体的な操作アルゴリズムを詰めました。
基本的に、巡回路は長い電車のようなものとみなし、電車には各箱番号に対応する「指定席」のようなものが設定されていると思うことにします。指定席は先頭から番号順に設定することにします。
指定席に各箱を積むことができれば、電車を搬出口に向かって1マスずつ進めることで、搬出口から次々と自動搬出できます。積み込めていない箱は、目の前を自分の指定席が来た時に長さ2のswapコンベアで入れ替えれば、電車に載せることができます。

基本方針は良さそうな感覚ですが、最初どのようにスタートすれば良いのかをもう少し整理する必要がありそうです。
以下の図は、便宜上巡回路を一直線に展開して描いています。搬出口が-1周目・0周目・1周目と複数描かれていますが、実際には同じマスを指しています。

この図で、初期状態では暫定的に一番上のように「-1周目の出口」が先頭車両の位置にあると仮定し、「0周目の出口」で順次箱を下ろしていくことを目指します。

• -1周目の出口を通過後、巡回路を1周して0周目の出口に到達するまでの間に各指定席の箱を正しく積む
• 0周目の出口を通過すると、その指定席は次の周(現在の番号＋巡回路の長さ)の箱の指定席に切り替わるものとする(この図の場合、0→8、1→9等)
• 0周目の出口を通過後、1周目の出口に到達するまでの間に更新された次の周の指定席の箱を正しく積む

この方針で進めようとした場合、0周目の出口通過までうまくいったと仮定すると、その後は指定席が空席になり、次の周の箱は巡回路の外に待機しているはずなので、目の前に達したタイミングで積めば良く、特に問題はなさそうです。

難しそうなのは、どうやったら0周目の出口までに正しく積むことができるか、です。
-1周目の出口を通過してから0周目の出口に到達するまでの間に、以下のような状況が生じたとしましょう。

• 箱3(指定席3)：指定席通りなのでOK
• 箱5(指定席2)：本来載せるべき箱2の前に来たときに箱2と入れ替わって下ろされ、その後指定席5が目の前に来たときに載せられる。したがってOK
• 箱1(指定席4)：既に自分の指定席は通り過ぎており、ここから一度下ろしても電車を逆走させない限り指定席1に載せることができないのでNG
• 箱10(指定席1)：まだ対応する指定席が存在しないが、箱1が来たときに箱1と入れ替わって下ろされ、その後指定席10ができて目の前に来るまで待てば良いのでOK (実質的に箱5と同じ状況)

つまり、指定席に乗り遅れている箱1のようなケースのみがNGであることがわかります。-1周目の出口通過後にこの状況が発生してしまうと復旧不可能なので、このような乗り遅れ箱は-1の出口を通過する前に下ろす必要があります。まだ対応する指定席の存在しない(図だと8番以降)箱と入れ替えるのが良さそうなので、乗り遅れ箱については退避側にいるそのような箱と貪欲に入れ替えることにします。
状況によっては、-1周目の出口付近に入れ替え可能な箱が少ないなどうまくいかない可能性もありそうですが、一旦この方法でどの程度うまくいくか実装してみることにしました。

細かいところはある程度割り切って、短期コンテストでも実装可能そうな方針にうまく落とし込めた感がありました。それでもそこそこ時間はかかりましたが開始2時間半を過ぎた頃に実装が終わりました。
バグを取り終わると、まずseed=0は期待通りに-1周目出口の前に乗り遅れ箱を下ろすことに成功していて、想定通りの一括搬出ができていました。
では、100ケースだとどれくらい失敗するのだろうと思って恐る恐る100ケースで実行したところ、意外にも1ケースも失敗しませんでした。ターン数も平均1060〜1070と、期待通り箱1個あたり約2.7ターンになっています。

100ケースで失敗しなかったので、失敗時のリカバリー処理も特に作らずにそのまま提出しました。

するとなんと一気に暫定1位に躍り出ました。しかもスコアは1126Mで、2位に約40Mくらいの差をつけています。何か今までにないくらいの当たり方針を引いた感触がありました。短期コンテストでは1位はおろか20位以内にも滅多に入ることはないので急にドキドキしてきます。

コンテスト終盤

終盤方針検討

この時点で残り時間は1時間15分ほど。既にかなりの当たり方針を引いたようなので、ここから大幅な改善は難しいような予感はありましたが、今の方針の枠組みで、かつ残り時間でできそうな改善案をいくつか考えました。

• 電車の開始位置は-1周目出口からにしていたが、今の様子だと乗り遅れを下ろすのにまだ余裕がありそうなので、もう少し前から発車しても良いのではないか
• 電車の進行方向を逆方向とすることで、初期の箱配置との相性で改善することがあるのではないか

開始位置の調整

まずは効果の大きそうな前者から取り組むことにしました。
現在のアルゴリズムは一瞬で実行が終わるため、実行時間はまだまだ余裕がありました。しかし巡回路の長さは約200あるため、開始位置を全200パターン試すのは間に合わない可能性もありそうです。
おそらく、開始位置を前にしすぎると乗り遅れ箱の退避場所が不足して破綻することになるので、どこかに成功〜失敗の境界ができると予想しました。もしかしたら境界は1箇所でキレイに分かれるわけではないのかもしれませんが、一旦キレイに分かれると仮定して二分探索で成功可能な最も前の位置を探すことにしました。
これは思ったよりも時間がかからずに実装することができ、スコアは1126M→1137Mに改善しました。

逆回転パターンの追加

この時点で残り1時間、2位はまだ1080M台でかなりの差をつけています。できればすぐコンテスト終了して欲しいところではありますが、先ほど考えた電車の進行方向を逆にするのを試すことにします。
これも10分ほどで実装完了し、1137M→1138Mと微改善しました。

コンベア配置パターンの追加

順調に改善が進んだので、さらに改善できそうな作戦を考えます。実行時間は依然として170msくらいでまだまだ余裕があります。
安直ですが、コンベア配置を縦往復的なパターン以外に横往復パターンも追加してみることにします。初期に配置するコンベアを変えるだけでメインのロジックはそのまま使えるので、実装は割と楽そうです。
Excelで配置パターンを下書きした後、縦往復の実装も整理しながら実装を進め、残り23分の時点で実装ができました。改善効果は0.7Mとわずかでしたが、着実にスコアを伸ばすことができています。
しかし、順位表を見ると2位のKiri8128さんが1128Mまで迫っており、早くコンテストが終わってほしい願望がより強まってきます。

まだ残り時間はありますが、複雑なことを追加する時間はなさそうなので、単純に増やせそうな左右反転パターンも追加することにしました。これも残り14分で完成し、1139Mに到達しました。しかし、2位のKiri8128さんも1130Mまで差を縮めてきています。

逃げ切りを図るべく、さらに配置パターンの追加を試みましたが、時間内にデバッグが終わらずここでコンテスト終了となりました。

結果

最終的に逃げ切ることができ、初めて1位を取ることができました。赤パフォも初だった上、入赤も同時に達成することができました。
赤パフォを取ることを目標にしてきたので、かなり上振れで達成することができ、非常に感慨深いです。

コンテスト後にXのタイムラインを見たところ、似たような巡回路アプローチ(回転寿司と呼ばれていてなるほどと思いました)の方は何人かおられました。何が勝負を分けたのかはよくわかっていませんが、勝ち切ることができて非常に誇りに思います。

コンテストを振り返って

最近の短期AHCでは、複雑な方針のまま実装を進めて完成できないとか、複雑な方針をシンプル化する努力が足りずに諦めるというパターンが続いていました。しかし今回は、欲張りすぎずちょうど良い具合に単純化した方針に落とし込むことができたのが勝因だったと感じています。

良いスコアが実現できそうなアイディアであっても、実装が終わらなければ意味がありません。実装可能なシンプルな方針に落とし込んでから進める、という今回の教訓を今後も実践できればと思います。