大学の授業で Dilworth の定理が出てきたので、この機会に（競プロer 的な視点から）まとめてみたいと思います。 例題 1 最小パス被覆 最大独立集合 Dilworth の定理 （補足）半順序集合とそのグラフ表現 半順序集合の定義 半順序集合のグラフ表現 半順序集…

概要 通常の最短経路問題と違って、辺を通ったときのコストの変化のしかたが変な場合でも、ダイクストラ法で解けることがある。ダイクストラ法を適用できる条件は 「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらな…

概要 「条件を満たすものすべてについてのスコアの総和を求めよ」という形の問題を DP で解けることがある。このときスコアの総和だけをもってもうまくいかなくて、条件を満たすものの個数も同時にもっておく必要がある。 例題 atcoder.jp 個の整数 がある。…