Orienteering(オリエンテーリング) - joi2011-day4 解説

筆者: qnighy

無閉路有向グラフ(DAG, Directed, Acyclic Graph)の最上流にスタート地点、最下流にゴール地点があり、頂点がチェックポイントであるかどうかが与えられたとき、スタート地点からゴール地点への有向パスの組で、全てのチェックポイントを一回以上通過しているようなもののうち、最短のものを求める問題である。

部分点解法

…

O(N^2+NM)解法

まず、これは無閉路有向グラフなので、トポロジカルソートを行うことで、頂点の順番をつけなおす。すると、どの道も小さい番号から大きい番号に向かって進むようになる。

ここで、問題文では、二人は独立に動くことになっているが、それぞれが道を進むことのできるタイミングに制約を設けることを考える。

すると、条件を満たすどのような経路も、以下のように同期をとることができる。

「どちらかがチェックポイントCに到達するまでは、どちらの人もCより先に進んではいけない。」

逆に、上記の条件を満たすように二人が進むとき、必ず条件を満たす経路が得られる。

この条件を満たすとき、どの状態でも、未到達のチェックポイントが二人の間にあることはない。すると、二人のいる位置が決まるとき、次に進んでよい範囲が決まる。あとは探索を組めばよい。

この探索は、状態数がN^2だけある。次に進める状態というのはどの場合でも「A君が進む」か「B君が進む」かしかない。そのため全体として辺数は2NMしかない。よってこれは動的計画法でO(N^2+2NM)で求めることができ、これが満点解法となる。