Quiz
https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d
Submit (TLE)
https://atcoder.jp/contests/nikkei2019-qual/submissions/4108450
補足
- コンテスト中、queueを使った幅優先をしつつ、距離dが大きくなるときは更新
- しかしTLE
- dが更新される度にqueue.pushしているのでO(N), O(M)にならないのだろう
- 解答を見るとトポロジカルソートするとのこと
- 親の辿り方も含めて理解した
- コンテスト中にはトポロジカルソートは候補にも出なかった
- DAGならトポロジカルソートを候補に入れていきたい（アルゴも簡単）
レート
- A, B, Cまでペナルティなしで早めに解いて水色パフォ
- Dまで解きたかった
- TLEだったので惜しい(?)。進歩は感じられる
3000人
- このコンテストは賞金もあるし新聞にも掲載したようで3000人も参加している
- 提出しているのは2500人
- Aを通しているのも2500人
- この規模、盛り上がりを感じる
