けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

DAGの最小パス被覆

AtCoder ABC 354 G - Select Strings (4D, 橙色, 625 点)

Dilworth の定理から、DAG の最小パス被覆!! かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…

AOJ 2828 マトリョーシカ (JAG 模擬国内 2017 F) (550 点)

DAG の最小パス被覆、忘れた頃に出て来るイメージ! 問題へのリンク editorials 問題概要 個の直方体があり、 番目の直方体の大きさは である。 今、ある直方体の中に他のある直方体を入れたりすることで、外部から見えている直方体の体積を小さくしたい。た…