n個の自然数の集合 S_1, S_2, S_3, ... S_n が与えられているとします。
この時、i!=j , S_i ⊆ S_j となる i, j が存在するか?という問題を考えます。
素朴な方法ではそれぞれの集合のペアの包含関係を調べることになると思いますが、
この時、集合の包含関係を O(n^2) 回調べる必要があります。
この回数を減らす方法はあるでしょうか?
n個の自然数の集合 S_1, S_2, S_3, ... S_n が与えられているとします。
この時、i!=j , S_i ⊆ S_j となる i, j が存在するか?という問題を考えます。
素朴な方法ではそれぞれの集合のペアの包含関係を調べることになると思いますが、
この時、集合の包含関係を O(n^2) 回調べる必要があります。
この回数を減らす方法はあるでしょうか?