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

これ茶色はさすがにびっくりした！ 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…

実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…