AOJ2404 ドッグフード

結構実装が大変と言われているこの問題。想定解法は指数オーダーの探索だが、これにも割と良さげな解法がある。

例えばこういうケースを例に考えてみる。ロープの上側がロープが結ばれている杭、左下側がスタート地点、右下の緑色の点がゴール地点である。

STEP 1
以下のような三角形を考える。この三角形の外側にある杭は無視してよい。三角形の内側にある杭について、その杭とゴール地点を結ぶ線分と赤い線分のなす角の小さい順に番号をつける。

STEP 2
適当な非負整数iを決め、1番目からi番目までの杭は迂回して、それ以外の杭は迂回しないとする。このとき、

(a) スタート地点、ゴール地点、1番目からi番目までの杭を頂点集合として凸包を求ると、スタート地点とゴール地点を直接結ぶ辺以外の辺の長さの和が犬の走る経路の長さとなる。
(b) ロープが結ばれている杭、ゴール地点、i+1番目以降の杭を頂点集合として凸包を求ると、ロープが結ばれている杭とゴール地点を直接結ぶ辺以外の辺の長さの和が必要なロープの長さとなる。

必要なロープの長さが実際のロープの長さ以下となるケースのうち、犬の走る経路の長さが最短となるものを求めればよい。iに対して必要なロープの長さは単調非増加なので、二分探索を用いることができ、O(N(logN)^2) で求めることができる。