RSS

優勝作品と解説

優勝されたo0p1qさんの作品と、ご本人による作品解説です。

優勝者作品

o0p1qさんの作品(ソースコード)

作品解説

この問題のポイントは、時間帯の指定されていない荷物の時間帯を、どのようにして決定するかという点だと思います。その時間帯の決定には、DFS(深さ優先探索)を用いました。単純にDFSをして最善の時間帯を求めようとすると、組み合わせの数が大きいため、制限時間内に導出できませんが、最善でないと分かった時点で探索をやめる枝刈りを行うことで高速化できました。

各点(荷物・オフィスの座標)間の最短経路の導出について

各点間の最短経路の導出には、BFS(幅優先探索)を用いました。1点を始点に決定して、その他距離を測る必要がある全ての点への最短経路を、キューを用いて導出しました。

ここでの高速化の手段として、無駄な壁の判定を避けました。4方向の壁の有無が決定すると、その時点で移動の有効な方向が決定します。プログラムの始めに、4方向の壁の有無の組み合わせ全てに対して、移動の有効な方向を求めておき、それを使うことで、BFSの最中では壁の判定をしないで済むようにしました。また、これによりループ回数も減りました。

荷物を配達する最善の巡回路の導出について

1つの時間帯で配達する荷物を決定したとき、消費燃料を最小とする荷物配達の巡回路は、bitDP(bit操作を用いた動的計画法)で求められます。このような、コストを最小とする巡回路の導出の代表的な問題として、「巡回セールスマン問題」があります。

DFSを行う過程で、1度計算した荷物の組み合わせの最小の消費燃料が再び必要となる場合がありますが、再計算を避けるためにメモ化を用いました。

DFSについて

DFSを行う前に、探索を高速化するため、以下のことを行いました。

  1. 時間帯の指定されていない荷物を、オフィスからの消費燃料が多い順にソートする。
  2. 全ての荷物の時間帯が指定されていなかった場合は、1つの荷物の時間帯を無条件に決定する。
  3. 枝刈りをする初期値として、貪欲に荷物の時間帯を決定していったときの消費燃料を求める。
  4. 時間帯の指定されていない荷物に対して、配達に必要な最低限の消費燃料を求めておく。

DFS本体では、重複する探索を避けるために、1つの荷物に対して、荷物がない時間帯への配分は1回だけとしました。荷物がない別々の時間帯に同じ荷物を配分するのは、状態としては同じであるため、意味のない配分となります。

PAGE TOP