hirokazu1020 https://blog.hatena.ne.jp/hirokazu1020/ hirokazu1020の日記 https://hirokazu1020.hatenadiary.org/ 応募最終日では1位と同スコア同実行時間で2位でした。 ・方針 ある時間帯に配達する荷物を決めたときの最小コストは明らかに巡回セールスマン問題(TSP)の応用で解ける。 それぞれの荷物をどの時間帯に割り当てるかは愚直に探索するとO(4^n)で間に合わないが(時間帯,残りの荷物集合)を状態として持つDPでbit演算で部分集合を列挙するテクを使うとO(3^n)で解ける。 最適解を求めることは出来たので以降はずっと高速化。 ・探索パターンの削減 自明な事実として時間帯0と時間帯1の荷物集合を入れ替えてもコストは変わらないのでこのような重複パターンの探索を避ける。 例として最大ケースである時間帯指定のな… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhirokazu1020.hatenadiary.org%2Fentry%2F20160114%2F1452775966" title="ハル研究所プログラミングコンテスト2015 - hirokazu1020の日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-01-14 21:52:46 rich https://hirokazu1020.hatenadiary.org/entry/20160114/1452775966 1.0 100%