ハル研究所プログラミングコンテスト2015

応募最終日では1位と同スコア同実行時間で2位でした。
・方針
ある時間帯に配達する荷物を決めたときの最小コストは明らかに巡回セールスマン問題(TSP)の応用で解ける。
それぞれの荷物をどの時間帯に割り当てるかは愚直に探索するとO(4^n)で間に合わないが(時間帯,残りの荷物集合)を状態として持つDPでbit演算で部分集合を列挙するテクを使うとO(3^n)で解ける。
最適解を求めることは出来たので以降はずっと高速化。
・探索パターンの削減
自明な事実として時間帯0と時間帯1の荷物集合を入れ替えてもコストは変わらないのでこのような重複パターンの探索を避ける。
例として最大ケースである時間帯指定のない荷物が16個ある場合を考える。
未割り当ての荷物が16個の場合、4つの時間帯はどれも荷物が割り当てられていない。荷物集合はどの時間帯に配達してもコストは変わらないので、1つ目の荷物についてはどの時間帯に割り当てるかを探索する必要がなく3^16から3^15に計算を落とせる。
2つ目の荷物についても荷物が割り当てられていない時間帯を複数探索する必要がなく2通りの分岐で済むので2*3^14になる。
さらに1つ目と2つ目の荷物を同じ時間帯に割り当てた場合を考えると3つ目の荷物の割り当ても2通りの分岐で済み、また同じ時間帯に割り当てたときはさらに再帰的に適用できる。
より実装寄りに説明すると、荷物が割り当てられている時間帯が2つ以上の場合はDPで計算して、そうでない場合はそれぞれの1つでも荷物が割り当てられている時間帯と1つも割り当てられていない時間帯のうち1つに、今注目している荷物を割り当て次の荷物について再帰的に計算した場合の最小コストとなるものを返す。
このように処理すると個数14,13,12,...についてDPの計算が行われておよそ3^14+3^13+3^12+...≒1.5*3^14程度の計算で済む。
・DPの高速化
重複パターンの探索が無駄なのはDPの計算においても同じなので、まだ荷物が割り当てられていない時間帯が複数ある場合は、後ろの時間帯に割り当てれば取り返しがつくので今注目している時間帯ではある荷物を絶対に割り当てないという選択が出来る。これによってその時間帯での計算パターン数を半分に出来る。
最小配達コストのテーブルは頻繁にアクセスされるので時間指定のない荷物はあらかじめ下位のindexにくるようソートしておくとキャッシュに乗りやすい。
・その他高速化
配達先や営業所間の距離はサイズ２のリングバッファを使いA*で探索する。
TSPテーブルなどのサイズが大きい配列はshortで宣言してキャッシュに乗りやすくする。
初期化は必要最小限に。
std::fill_nはfor文まわすより速い。
各荷物集合に対する重さはO(n*2^n)ではなくO(2^n)で計算する。
TSPの計算はO(n^2*2^n)でとても重いので別々の時間帯が含まれる荷物集合などの不要な計算は極力抑える。
TSPの計算は配るDPより集めるDPのほうが速い。

最終方針
途中までこんな感じでDP解法を0.4秒近くまで高速化していた。
o0p1qさんが0.2秒だしてやべぇなTSPの計算しかしてないとしても速すぎるなと思ったので、TSPの計算をあまりせず遅延評価しているというのは察しがついた。
方針は枝刈りでナップザックを下界を見積もって枝刈りするという方法を思い出してやった（分枝限定法というらしい）。
最適解をビューアで見てみると荷物は同じ時間帯に配達するもの同士でかたまっているという幾何的な特徴があり、良い解付近には良い解が、悪い解付近には悪い解が集まっていることが推測できるので枝刈りしやすそうと考えられる。
ということで途中からDP解法を枝刈り解法に変更した。
・下界
下界はそれぞれの時間帯ですでに割り当てた荷物集合に対する配達コストと未割り当ての荷物それぞれに対する下界の和として計算する。荷物集合にある荷物を追加するとき大きく2通りの場合がある。荷物集合が空である場合は営業所と配達先の往復分のコストがかかる。荷物集合が空でない場合は追加する荷物の配達先の直前と直後の位置は営業所または別の配達先にいるので、直前、直後の位置をそれぞれa,b,追加する荷物の位置をcとするとa->bをa->c->bに変更したときのコストの考えられる最小増加分を下界とする。
それぞれの荷物について上記のどのパターンになるかわからないが全パターンの増加コストの最小値なら実コストを超える心配はないので下界として使用することが出来る。
・荷物ソート
枝刈り解法の場合どの順番で荷物を追加するかで枝刈り効率が大きく変わる。
営業所からのマンハッタン距離で降順ソートした場合、クラスタ（同じ時間帯に配達する荷物集合）への距離は近く、または遠くなりやすいのでより枝刈りが効率的に行われると考えられる。最終的には荷物の重さも含めた式でソートした。
・時間帯の探索順序
分枝限定法では今まで見つかった解の最小コストを上界として枝刈りするのでなるべく早く最適解を求めたほうが良い。
各時間帯に荷物を追加した際の増加コストの昇順に探索すると早く最適解が見つかるのでより枝刈りすることが出来る。
・フィールド生成にあわせたA*高速化
ここまでくるともう前処理の距離計算がボトルネックになってきたのでこちらも高速化する必要が出てきた。
フィールドの形は明らかに規則的なのでフィールド生成コードを見ると(odd,odd)の座標は壁ではなく、(even,even)の座標は壁になっていることがわかる。つまり(odd,odd)から1歩移動した先の両肩は必ず壁になっておりそのまま直進するしかできないことが出来ないので再び壁の判定をするのは無駄なことがわかる。なので(odd,odd)の座標しかキューに入れず壁判定の回数を抑えることが出来る。

コード　no title