競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
296: (ﾜｯﾁｮｲ 9f55-hzXf) 2023/05/03(水)17:06 ID:aKUbjdKi0(1/5) AAS
n次元直方体とは I = [a_1, b_1] × [a_2, b_2] × … × [a_n, b_n] の形の集合である。
n次元空間 R^n の部分集合 B で、有限個のn次元直方体の和集合であるようなもの全体の集合を C とする。
B1, B2 ∈ C であるときに、 B1 = B2 であるかそうでないかを判定してください。
↑自作の問題です。
この問題って効率的なアルゴリズムが存在しますか？
299: (ﾜｯﾁｮｲ 9f55-hzXf) 2023/05/03(水)19:40 ID:aKUbjdKi0(2/5) AAS
B1 が1個のn次元直方体からなる集合とします。
それを2つに分けた2つのn次元直方体の和集合を B2 とします。
B1 を構成する直方体の数は 1 です。
B2 を構成する直方体の数は 2 です。
ですが、B1 = B2 です。
300: (ﾜｯﾁｮｲ 9f55-hzXf) 2023/05/03(水)19:43 ID:aKUbjdKi0(3/5) AAS
B1 = [0, 1] × [0, 1]
B2 = [0, 1/2] × [0, 1/2] ∪ [1/2, 1] × [0, 1/2] ∪ [0, 1/2] × [1/2, 1] ∪ [1/2, 1] × [1/2, 1]
が入力として与えられた場合、 B1 = B2 です。
301(1): (ﾜｯﾁｮｲ 9f55-hzXf) 2023/05/03(水)19:48 ID:aKUbjdKi0(4/5) AAS
B1 = [0, 5] × [0, 5]
B2 = [0, 2] × [0, 1] ∪ [1, 4] × [2, 3] ∪ [2, 4] × [3, 4] ∪ [0, 1] × [2, 4] ∪ [2, 4] × [0, 2] ∪ [0, 2] × [1, 2]
B1 ≠ B2 です。
302: (ﾜｯﾁｮｲ 9f55-hzXf) 2023/05/03(水)19:49 ID:aKUbjdKi0(5/5) AAS
>>301
訂正します：
B1 = [0, 4] × [0, 4]
B2 = [0, 2] × [0, 1] ∪ [1, 4] × [2, 3] ∪ [2, 4] × [3, 4] ∪ [0, 1] × [2, 4] ∪ [2, 4] × [0, 2] ∪ [0, 2] × [1, 2]
B1 ≠ B2 です。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.725s*