Dilworth(ディルワース)の定理についてのリンク集

意図

• 定義を見に行ってもよく分からないので、具体例をここに集めてふわっと理解したい

links

• The Phone Number
  • https://codeforces.com/contest/1017/problem/C
  • この問題のeditorialで出てきます

• ABC134-E
  • editorialに書いてある from https://img.atcoder.jp/abc134/editorial.pdf

「DAG 上の最小 path 被覆 (全ての頂点を適当な path に属するようにして
分割する時の必要な path の最小本数) は、最大 antichain
（頂点の集合であって、集合に属する任意の 2 頂点に関して、
それらを結ぶような path が存在しない）の要素数と一致する」

• from https://img.atcoder.jp/abc134/editorial.pdf

関連

• DAG上の最小パス被覆
  • https://perogram.hateblo.jp/entry/2020/09/24/033802

画像

• LISのマイナーチェンジ https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d1-matryoshka-review.pdf
• LIS : O(NlogN)