ARC090 D : People on a Line(400)
作成日：2018.02.02
最終更新日：2018.02.02
問題概要
$x$軸上の$10^9$以下の非負整数の座標に$N$人の人がいて、人$R_i$は人$L_i$よりも$D_i$だけ右にいるという形式の情報が$M$個与えられる。
同じ位置に人が複数人いても良い時、$M$個の情報に矛盾しない人の配置が存在するかを判定せよ。
制約
$1 \leq N \leq 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq L_i , R_i \leq N$
$L_i \neq R_i$
$i \neq j$ならば$\{L_i , R_i\} \neq \{L_j , R_j\}$
$0 \leq D_i \leq 10^4$
$D_i$は整数
考え方
まず$10^9$以下の非負整数という座標についての条件を満たすかについて考える。
ある$2$人が最も離れるのは、$N$人が$max(D_i)$間隔で並んでいる時である。
この時の$2$人の距離の最大値は$(N-1)max(D_i)$であり、これは$10^9$未満である。
すなわちはみ出した分は後で調整することによって、座標の条件は常に満たすようにできる。
以下では人を頂点、情報を有向辺とみなす。
辺がない頂点同士には制約が存在しないので、弱連結成分ごとに考える。
先の考察から正当性は保証されているので、1つの頂点の座標を$0$に決め打ちすることができる。
すると、座標が決まった頂点と辺で結ばれている頂点の座標を一意に定めることができる。
もし矛盾が生じたら、条件を満たす人の配置は存在しないことが分かる。
逆にすべての弱連結成分で矛盾が生じなかったら、そのような配置が存在することが分かる。
有向辺を無向辺とみなして全域木を作ると、すべての頂点の座標を決めることができる。
後はその全域木に含まれなかった辺で矛盾が生じないかを調べれば良い。
これは例えば全域木を深さ優先探索木とするとそれに含まれない辺は後退辺であり、木の構築と矛盾判定が深さ優先探索1回で行える。
この方法の計算量は$O(N+M)$なので十分高速である。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N,M;
vector<P2> V[MC];
bool b[MC];
int x[MC];
bool dfs(int q){
b[q] = 1;
for(auto u : V[q]){
if(b[u.first]){
if(x[u.first] != x[q] + u.second) return 0;
continue;
} else {
x[u.first] = x[q] + u.second;
if(!dfs(u.first)) return 0;
}
}
return 1;
}
int main(){
cin >> N >> M;
repp(i,0,M){
int l,r,d;
cin >> l >> r >> d;
V[l].PB(MP(r,d));
V[r].PB(MP(l,-d));
}
repp(i,1,N+1){
if(b[i]) continue;
if(!dfs(i)) return cout << "No" << endl , 0;
}
cout << "Yes" << endl;
return 0;
}解法まとめ
弱連結成分ごとに考える。
1つの頂点の座標を$0$と決めた上で深さ優先探索木を構築し、それに含まれる辺を用いて他の頂点の座標を決める。
後退辺の示す情報がすでに決めた座標と矛盾するならNo、すべての弱連結成分で矛盾しないならYesが答えである。(7-19,29-33行)