【要約】AHC065参加記・1位解法 [Qiita_Trend] | Summary by TechDistill
> Source: Qiita_Trend
Execute Primary Source
// Problem
筆者がAHC065のベルトコンベア搬出問題に取り組んだ際、以下の技術的課題に直面した。
- ・単純な縦横移動方式では、特定の操作が他の箱の移動を妨げる。
- ・箱1個あたりの平均手数が約15手となり、効率が著しく低い。
- ・最短手数を求めるための探索空間が極めて広く、実装が困難である。
- ・短期コンテストという時間制約下で、複雑なアルゴリズムを完成させられないリスクがある。
- ・「設置」と「操作」の2フェーズを同時に最適化する必要がある。
// Approach
筆者は、複雑なビームサーチ等を避け、巡回路を用いた一括搬出方式を採用した。
- ・全マスを距離1でカバーする巡回路を設置する。
- ・巡回路の各マスに、搬出順に応じた「指定席」を割り当てる。
- ・長さ2のswapコンベアを用い、箱を巡回路の指定席へ積み込む。
- ・「乗り遅れ箱」を事前に退避させるロジックを組み込む。
- ・二分探索で電車の開始位置を最適化する。
- ・コンベアの配置パターン（縦横、反転）を増やして改善を図る。
// Result
筆者が提案した手法を実装・適用した結果、以下の成果を得た。
- ・AHC065において暫定1位を獲得した。
- ・最終スコア1139Mを達成し、2位に大きな差をつけた。
- ・箱1個あたりの平均ターン数を約2.7ターンまで劇的に削減した。
- ・100ケース中、失敗ゼロの極めて高い安定性を実現した。
- ・赤パフォーマンスおよび入賞赤を同時に達成した。
- ・実装のシンプルさを維持しつつ、高いスコアを叩き出した。
Senior Engineer Insight
> 本解法は、複雑な最適化問題を「巡回＋局所的な入れ替え」という単純なモデルに落とし込んだ点が秀逸である。これは、リアルタイム性が求められる大規模システムにおける、ストリーム処理の設計思想に近い。実装コストを抑えつつ、理論的な限界に近い性能を引き出すアプローチは、実務におけるプロトタイプ開発や、制約の厳しいスケジューリング問題において極めて高い価値を持つ。複雑なものをシンプルに解く能力こそが、現場での勝負を決める。