ハル研プロコン2015 に底辺プログラマとして参加しました.
結果が 2015/01/29 に出ますが, 底辺なので良い順位になるはずもありません.
そして, 一気に高速化ゲーにしてしまった感があります...
プロコンサイトのプログ: プロコン速報 vol.1 に書かれてるように
また、処理時間もけっこうな勢いで短縮していきました。これも予想以上でした。
と, 序盤から高速化勝負にしてしまった責任感から投稿します.
底辺の考え方は一般的な人にも利用できると思うので記しておきます.
- 荷物を持って出発し, 配達して戻ってくる -> どうみても最小ハミルトン閉路です. 本当にありがとうございました.
- 4つの時間に指定されているか, 時間無関係な荷物を配達する -> 3つ列挙するとだめ...
(一日経過)...4つで全部行くなら二つで行ける部分を組み合わせる半分全列挙か...底辺とはいえ頭悪すぎだなぁ...
という感じです. 一般的な人なら一瞬で最適解を出せるでしょう.
これが例だと思います.
ハル研プロコン見た瞬間に解放思いつくタイプの問題だと思っていたんだけどなあ
— JOI実質予選落ち (@maroon_kuri)
2015, 12月 18なお普通の人は 配送計画問題 というORの分野での典型問題である事を知っているはずなので
最適解を出す部分で差がついていると思います.
一瞬で分かる人が言う通り, DP(動的計画法)で最適解が間に合う時間で簡単に求められます.
- 全通りの荷物の持ち方に対して 最短ハミルトン閉路 を列挙する.
O(2^N * 2 * N) で求められます. 安定のスパソで安心ですね. - 何時でも運んでよい荷物に対して, 2回運ぶ解を列挙(半分全列挙)して合成する. (マッチングする)
工夫しないと O(4^n), 工夫すると O(3^n + 2^n) となります. (nは時間帯指定されていない荷物の数)
解法としては以下の人のツイートと全く同じです.
ハル研プロコン、採用したのは各時間帯について巻き戻しを考えるとTSPの類似っぽくなってO(2^n*n^2)で計算できて、その結果をマージするのにO(3^n)という解法でした。
O(2^n*n^2*c)(cは最大積載量)の解法もあったけど遅かった
— そすうぽよ (@_primenumber)
2016, 1月 7この解法はとても簡単で, どんな底辺でも最適解を出せる事でしょう.
しかし, ナイーブに実装すると 10sec や 5sec くらいになります. 高速化しましょう.
マラソン系コンテストでは非自明な手法や枝刈りが注目されます.
しかし, 自明な手段しか分からない底辺にはとてもとても難しい話です.
なので, 底辺でもやれる自明な事をやって地道に速度を上げていきました.
枝刈りをするのであれば, 枝刈りした結果が波及しないと意味がありません.
このため, 単純にforループで全ての荷物のbit列を列挙するよりも
キューを使ってbit列をbit数順に見た方が枝刈りが効果的に働きます.
コードとしては以下のようなものになります.
//before
for(int bit = 0; bit < (1 << N); bit++){
if(枝刈り条件){ continue; }
// 何か処理する
}
// after
std::queue<int> bit_queue;
while(!queue.empty()){
const int bit = queue.front(); queue.pop();
// 何か処理する
// 次のbit列を枝刈りしながら queue に突っ込む
}
※ メモ化再帰にしてマッチング側から呼ぶ方が速いし枝刈りできます. 底辺だから頭が回らなかった...
ハミルトン閉路を探す際に重さが15を超える場合は計算しなくていいです.
これは最高でも一回10個の荷物しか持てない事を意味します.
(重さ1,2,3 の荷物は最高でも各6個までしかないので10個が最大)
別々の時間を指定されている荷物がある場合は配達不可能です.
そのような頂点は探索されないようにすると速くなります.
TSPにおいて, 荷物のbit列からfor文で今いる荷物番号を見るのは高コストです.
N = 16 とかの場合に結構重い処理になるので無駄な部分に continue するコストを払いたくありません.
これについては, ntz(number of trailing zeros) や nlz(number of leading zeros)を使って
削減できそうだと思えます. (効果があるとは言っていない)
// before
for(int cur = 0; cur < N; cur++){
if((bit & (1 << cur)) == 0){ continue; }
// 処理
}
// after
for(int cur_bit = bit, cur = ntz(bit); cur_bit > 0; cur_bit -= 1 << cur, cur = ntz(cur_bit)){
//処理
}
※ 底辺なので こういう話 があるのに初回にDPしてntzテーブルを作ってました.
..(SSEでもLZCNTとかあるし速く出来るのに...)
時間帯指定のない N = 14, 15, 16 はテストケース全体から見ると非常に少ないです.
しかし, これのせいでマッチングする際に時間が掛かっておりボトルネックとなります.
これらには時間指定のない荷物だけなので時間帯を区別しなくて良いという特徴があり,
時間帯を区別する条件をこちらで定められます. これは探索範囲を制限できるという事です.
例えば, 時間帯を 01 と 23 で分けた場合, どちらかの最上位bitは必ず立っており
もう片方の最上位bitは必ず立ってないという分け方が出来ます.
これを利用する事で部分列挙が 3^n -> 3^(n - 1) と改善します.
しかし, 半分全列挙のチェックで 2^n が 3^(n - 1) に増えます.
結果的には, 2 * 3^(n - 1) < 2^n + 3^n であるので計算量が削減できます.
先ほどは, 前半, 後半の順序付けですが, 前半内, 後半内にも順序付けが出来ます.
例えば, 前半で 0(bit列) > 1(bit列) を満たすように探索範囲を狭められます.
//before
for(int fst = 0; fst < (1 << (n - 1)); fst++){
for(int snd = ^fst; snd >= 0; snd --){
snd &= ~fst;
// なにか
}
}
//after
for(int fst = 0; fst < (1 << (n - 1)); fst++){
// fst の最上位bit より上はダメ
const int mask = roundup_2(fst) - 1;
for(int snd = mask & ~fst; snd >= 0; snd --){
snd &= mask & ~fst;
// なにか
}
}
頭が悪い底辺でも 約0.7 sec と 一秒切る事が出来ました.
この過程でプロのhirokazu氏やtakapt氏等と勝負出来たのは奇跡なのではないでしょうか.
そして, 底辺でもプロと並んで勝負が出来るという証拠になっていればなぁと思います.
最後に, どんなに頭の悪い底辺でもコンテストにおける中間的な強さは狙える
という希望を与えられたら満足です.