とりあえず解きたい(続)

• ６月２２日の記事の問題の変形
• 今、N個の要素からなる要素集合がある
• これの部分集合がｋ個与えられている
• k個の部分集合のうち、s個の部分集合がロシアのマトリョーシカ人形のような包含関係にあるときs個の部分集合に対する処理はその一番要素数の多い部分集合１つを処理すれば十分であるとする。このs個の部分集合の代表となる部分集合を代表部分集合とする
• このような条件にあるとき、もっとも少ない数の代表部分集合の組を求めたい

• 解はこう？
  
  • 与えられる部分集合数kが大きくなく、Nも大きくなければ、k(k-1)/2の包含関係を調べるのが速いだろう
  • 問題はkが大きいとき