Hatena::Grouptopcoder

Hiro180の日記

 | 

2017-09-15

みんなのプロコン本選 E - 瞬間移動装置 02:09

本番ぶりに考察したら割とすんなり思いついた、良問です

問題概要

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))で通る。

 |