eijirouの競プロ参加記

主に AtCoder Heuristic Contest の解説記事を書く予定です。

AHC006 解説

f:id:eijirou_kyopro:20220208232033g:plain
Seed=0 の出力

京セラプログラミングコンテスト(AtCoder Heuristic Contest 006) の解説です。

コンテスト中は1,764,699点で57位、コンテスト後は2,110,386点で10位相当のスコアを出しました。ここではコンテスト後の解法を紹介します。

紹介する解法は一例です。もっといい解法があるかもしれません。

問題概要

デリバリーサービスを題材とした問題です。

注文が1000件入っており、 i 番目の注文は (a_i,b_i) にあるレストランから (c_i,d_i) への配達依頼です。移動にはマンハッタン距離の分だけ時間がかかります。また、任意個の料理を同時に運ぶことができます。

50件の注文を処理できるような配達ルートで、移動時間が短いものを求めてください。

方針

貪欲法で得られた解をベースに、注文の入れ替えと2-optで焼きなましました。

なお、この方針はWriterであるwataさんのツイートを参考にしています。 https://twitter.com/wata_orz/status/1459840344062050304

TSP(巡回セールスマン問題)に帰着する

50件の注文を固定した場合、TSPに訪問順序の制約をつけたものとみなすことができます。"訪問順序の制約"というのが厄介ですが、条件付きで2-optという強力な手法を用いることができます。2-optがわからない人は"TSP 2-opt"などで検索するといいと思います。

注文の入れ替え

まず、50件の注文のうち1件を削除します。

次に、採用していない950件のうち何件かを選択し、最適位置に挿入したときのコストが最も小さいものを選び、それを追加します。("何件か選択し"というのは1件でもいいと思います。)

焼きなまし法のスケジューラーにかけて、採用の場合は変更を保存し、不採用の場合は元に戻すようにします。

挿入最適位置を求めるアルゴリズム

注文の個数を M=50 とします。 O(M^{2}) の全探索をせずとも、 O(M) で最適位置を求めることができます。

a_i = レストランを i 番目より前に挿入したときの最小コスト

b_i = 配達先を i 番目以降に挿入したときの最小コスト

c_i = a_i + b_i

d_i = レストランと配達先の両方を i 番目に挿入したときのコスト

とすると、最小コストは \min(\min(c),\min(d)) となります。 a は前から、 b は後ろから O(M) でそれぞれ求められるため、全体の計算量も O(M) になります。

O(M) の操作を何度か行うことになるため、この処理がボトルネックになりやすいと思います。精度を犠牲にして、より速いアルゴリズムを用いたほうがよいかもしれません。

初期解に貪欲法を用いたと述べましたが、その貪欲法とは、この最適挿入を50回繰り返すだけです。うまく実装すれば同じ関数を使えます。

2-opt

訪問順序の制約により、単純な2-optは使えません。そこで、繋ぎ直しても順序が逆転しない場合にのみ処理を行うようにすればよいです。

ある範囲の順番を入れ替えるときに、レストランと、その対応する配達先のペアが両方範囲に含まれている場合には、繋ぎ直したときに順序が逆転してしまうので2-optを適用できません。それ以外の場合には2-optを適用できます。

提出コード

atcoder.jp 約300行です。最適挿入位置を求めるところで少し苦労しました。

最後に

「いくつかの点を選んでTSPに帰着する」というのはAHC005と似ていますが、注文の選び方が難しく、また、単純な2-optが使えないので、今回ならでは難しさがあるなあと思いました。

最後まで読んでいただき、ありがとうございました。