2021-08-17から1日間の記事一覧

有向グラフ 閉路検出 トポロジカルソート DAG

Quiz PAST7 J-終わりなき旅 AC https://atcoder.jp/contests/past202107-open/submissions/24415719 解法 グラフをトポロジカルソートする DAGじゃない時は失敗する DAGじゃない場合は閉路がある 計算量 トポロジカルソートの分の O(N+M)

平面走査(法) (scanline algorithm?)

上記画像は https://atcoder.jp/contests/abc174/tasks/abc174_f の解説放送から 2Dにプロットしてそれぞれ処理していくのだが、処理順をx軸またはy軸の順に滑らせる BIT, segtreeがお供? 問題集 Range Set Query https://atcoder.jp/contests/abc174/tasks…