parking lot
B: 駐車場 - AtCoder Regular Contest 056 | AtCoder
解説スライドを見ましょう。
問題概要
$i$を$1$から$N$まで増やしていく。
始点$s$から頂点$i$に到達できたとき、以降は$i$を通れなくなる。
到達できなかったときは何もしない。（以降も$i$は通れる。）
到達できた頂点を昇順で出力してね。
解き方
まず、“到達できなかったときは何もしない”とありますが、“以降は頂点$i$を通れなくなる”としてよいです（到達できないので）。 結局、次のように言い換えられます。
- $s$から$i$まで到達できるかどうか判定する。
- 以降は$i$を通れなくなる。
こうすると、$i$について調べるとき$i$より小さい頂点は全て通れなくなっています。つまり、次の2つのことを同等に扱えます。
- $s$から$i$まで到達できる。
- $s$から$i$まで番号$i$以上の頂点のみを通って到達できる。
ここで$cost_i$を次のように定義します。
$s$から$i$へのある経路を考える。
その経路に含まれる頂点の中で最小の番号を$c$とする。
$s$から$i$への全ての経路について$c$を考え、その最大値を$cost_i$とする。
たとえば、入出力例2において$cost_2=2$です。5→1→2という経路を考えたとき$c=1$ですが、5→3→2という経路を考えると$c=2$です。そして$c\geq 3$となる経路は存在しないので$cost_2=2$です。また、$cost_4=3$です。対応する経路は5→3→4です。
さて、$cost_i$を用いると到達可能判定はcost[i]>=iと書けます。 *1 たとえば、$cost_4<4$なので4は答えに含まれません（到達できません）。
素直に$cost_i$を求めるには、たとえば$s$から各$i$への全ての経路を列挙すればいいでしょう。しかしそれはさすがにつらそうなので、もう少し効率よく求めたいのですが、実は$cost_i$はdjikstra的に大きい順に確定させていくことができます。これは分からない。ある時点で各頂点に対して暫定的な$cost_i$が求まっているとします。このとき、その中で最大のものを$cost_v$とすると、$s\to j\to\cdots\to v$という経路で$cost_v$が更新されることはありません。なぜなら、$v$を除く全ての頂点$j$について$cost_j\leq cost_v$だからです。*2
初期条件を考えましょう。まず、始点から全ての頂点に到達できることが保証されているので、全ての$i$に対して$cost_i=0$としていいです。*3次に、始点$s$に対して$cost_s=s$が確定します。なぜなら$s$から$s$への経路は1つしかないからです。
計算量はきっと$O(M\log{N})$くらいになります。
解答例
別解
UnionFindを使った別解があります。
$i$が答えに含まれるか判定するとき、$i$以上の頂点同士をすべてつなげたあとに$s$と$i$が連結かどうかを見ればいいです。ただし、$i$は$N$から$1$まで減らしていきます。これは、$i=1$から始めると1回で全ての頂点が連結になってしまってうわわってなったり、$i=N$が答えに含まれる条件はかなり厳しくなる感を感じたりすれば分かると思います。
おわりに
ダイクストラが分かってないので、意味不明になりました。 下の記事（とてもわかりやすい！）を10回くらい読むと、ちょっと分かりました。
