ハル研プロコンに参加しました

ハル研プロコンに参加しました。

結果はまだ出てないので後で書きます。そんなにいい順位ではないはずです。もうコンテストは終わって解法について触れても良さそうなので考えたことを書きたいと思います。

問題文はこちら↓
www.hallab.co.jp

問題文からはわかりませんが, 今回の問題では配達先が最大でも 16 個しかないので, 配達先の集合が分かれば, bitDP で最小コストが求められることはすぐにわかります。

あと問題なのは, 配達先をどう分類するかです。配達先の数を n として, それぞれの配達先にどの時間帯に届けるかを単純に全探索すると, 少なくとも O(4^n) かかり死にます。
そこで, まず配達先の集合 s について, 「時間帯を 01のみ/23のみ にした場合に, 最小コストはいくらになるか」というものを考えます(時間帯は 0, 1, 2, 3 であるとしています)。
bitDP で dp[s] = (最小コスト) という形で値を保持しておけば, 集合 s について, 時間帯を 01 のみに限定した際の最小コストは, s0&s1 = 0 かつ s0|s1 = s を満たす s0, s1 について, dp[s0] + dp[s1] の最小値を求めれば良いです。
で, ここで愚直に s0, s1 を探索するとやはり O(4^n) かかって死にますが, 部分集合を列挙するテクニックを使えば, s0 を決めた時 s1 の集合はそれほど多くならず, 計算量としては O(3^n) で計算できます。これはつい最近の記事で書きました。
mayokoex.hatenablog.com
「ていうかこれ…」と書いてるのは「ハル研プロコンで使えるじゃん」と思ったからですね。

で, 01/23 の時間帯における最小コストが求められれば, あとは 「01 で配達する荷物か, 23 で配達する荷物か」というのに関する O(2^n) の全探索をして最小コストを求められます。

結局 O(n^2*2^n + 3^n + 2^n) くらいで答えを求められました。これが主に考えたことですね。

あと普通に思いつきそうな高速化(調べなくて良い bitDP は調べないとかもう時間帯が決まっている配達先については調べないとか)して提出しました。

コード貼っておきます。
github.com