2017-09-15
■ みんなのプロコン本選 E - 瞬間移動装置
本番ぶりに考察したら割とすんなり思いついた、良問です
問題概要
N(<=10^5)頂点のクリークからM(<=10^5)本の辺を取り除いたグラフにおいて、頂点cから頂点dに行く時の最短経路をQ(<=10^5)組求めよ。
解法
本質は、次数がN/2以上の頂点同士を選んだ場合答は1か2であることに気づくことです。(そそ)
そして、次数がN/2未満 <=> 補グラフでの次数がN/2より大 よりそのような頂点は高々2*M/(N/2) = 4*M/Nしかなく、
4*M/N <= 2*Nが成り立つのでNの値で場合分けするとそのような頂点は高々1000個くらいしかないことがわかる。
ということは次数がN/2未満の頂点からO(N+M)でBFSして答を前計算してやれば良いとわかる。
BFSのやり方は、バケツソートのような感じで距離が0,1,2....の順に見ていき
「距離Dの頂点全てに対し取り除かれた辺でつながっている頂点に+1した後、未処理の頂点をすべて舐めて今までの加算回数(=距離D以下の頂点の個数)と頂点の値が等しくないなら距離D+1として決定する」
という処理を行えばよい。(未処理の頂点をすべて舐めて良いのは、距離D+1にならない頂点を見る回数は合計で高々O(M)回、距離D+1になる頂点を見る回数は合計で高々O(N)回なので)
以上を実装すると、計算量O(sqrt(M) * (N+M))で通る。
