結果
| 問題 |
No.2121 帰属関係と充足可能性
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:12 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 303 ms / 2,000 ms |
| コード長 | 8,467 bytes |
| コンパイル時間 | 428 ms |
| コンパイル使用メモリ | 83,028 KB |
| 実行使用メモリ | 129,756 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:03 |
| 合計ジャッジ時間 | 4,312 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 49 |
ソースコード
import sys
# Increase recursion depth if necessary, though the iterative generation should avoid deep recursion.
# sys.setrecursionlimit(2000)
def solve():
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A0, A1, A2, A3, A4, A5 = A
# Handle N=0 case: V_0 is the empty set, so no elements m_0, m_1, m_2 exist.
if N == 0:
print("NO")
return
# Check for conditions that violate the Axiom of Regularity (no set contains itself).
# In the context of Von Neumann hierarchy V_N, sets are well-founded, so x \in x is impossible.
# Condition 2: m_{A1} \in m_{A2}. If A1 == A2, this becomes m_{A1} \in m_{A1}, which is impossible.
# Condition 3: m_{A3} \in m_{A2}. If A3 == A2, this becomes m_{A2} \in m_{A2} (since m_{A3}=m_{A2}), impossible.
# Condition 4: m_{A4} \in m_{A2}. If A4 == A2, this becomes m_{A2} \in m_{A2}, impossible.
# Condition 5: m_{A5} \in m_{A0}. If A5 == A0, this becomes m_{A0} \in m_{A0}, impossible.
if A5 == A0 or A1 == A2 or A3 == A2 or A4 == A2:
print("NO")
return
# Generate the hierarchy of sets V_k up to V_N.
# We assign a unique integer ID to each distinct set encountered.
# `all_sets` list stores the canonical representation (sorted tuple of element IDs) for each set ID.
# ID 0 is reserved for the empty set.
all_sets = [()]
# `set_to_id` dictionary maps canonical representation (tuple) to the assigned set ID.
set_to_id = {(): 0}
next_id = 1
# `V_k_ids` list of lists stores the IDs of sets belonging to each V_k.
V_k_ids = [[] for _ in range(N + 1)]
# V_0 is the empty set, has no elements. Its list of IDs is empty.
V_k_ids[0] = []
# V_1 = {emptyset}. The empty set has ID 0.
empty_set_id = 0
if N >= 1:
V_k_ids[1] = [empty_set_id]
# Generate V_k for k=1..N iteratively.
# V_k is the power set of V_{k-1}.
for k in range(1, N + 1):
# Get the list of IDs of elements in V_{k-1}
elements_of_V_k_minus_1_ids = V_k_ids[k-1]
num_elements_V_k_minus_1 = len(elements_of_V_k_minus_1_ids)
# Store IDs of sets that constitute V_k
current_V_k_ids = []
# Iterate through all possible subsets of V_{k-1} using bitmasks.
# Each integer `i` from 0 to 2^|V_{k-1}| - 1 represents a subset.
limit = 1 << num_elements_V_k_minus_1
for i in range(limit):
# Construct the current subset based on the bits of `i`.
subset_element_ids = []
for j in range(num_elements_V_k_minus_1):
if (i >> j) & 1:
# If j-th bit is set, include the j-th element of V_{k-1} in the subset.
subset_element_ids.append(elements_of_V_k_minus_1_ids[j])
# Use a sorted tuple of element IDs as the canonical representation for the set.
subset_element_ids.sort()
canon_rep = tuple(subset_element_ids)
set_id = -1
# Check if this set structure has been seen before.
if canon_rep in set_to_id:
set_id = set_to_id[canon_rep]
else:
# Assign a new ID if it's a new set structure.
set_id = next_id
set_to_id[canon_rep] = set_id
all_sets.append(canon_rep)
next_id += 1
# Add the ID of this set to the list for V_k.
current_V_k_ids.append(set_id)
# Store the generated IDs for V_k. Sorting is optional but helps consistency.
V_k_ids[k] = sorted(current_V_k_ids)
# Finished generating sets up to V_N.
# Get the list of IDs for elements in V_N.
V_N_element_ids = V_k_ids[N]
# It's possible V_N is empty only if N=0, which is handled already.
# If N > 0, V_N always contains at least the empty set.
# Create a set of IDs for elements in V_{N-1} for efficient lookups.
ids_V_N_minus_1_set = set(V_k_ids[N-1])
# Determine which variables (m_0, m_1, m_2) MUST be assigned values from V_{N-1}.
# This is required by the membership conditions: if `m_X \in m_Y`, then `m_X` must be an element of `V_{N-1}`
# because `m_Y \in V_N` implies `m_Y \subseteq V_{N-1}`.
restricted_vars_flags = [False, False, False]
# Condition 2: m_{A1} \in m_{A2}. Implies m_{A1} must be a set from V_{N-1}. The variable m_{A1} is restricted.
restricted_vars_flags[A1] = True
# Condition 3: m_{A3} \in m_{A2}. Implies m_{A3} must be a set from V_{N-1}. The variable m_{A3} is restricted.
restricted_vars_flags[A3] = True
# Condition 4: m_{A4} \in m_{A2}. Implies m_{A4} must be a set from V_{N-1}. The variable m_{A4} is restricted.
restricted_vars_flags[A4] = True
# Condition 5: m_{A5} \in m_{A0}. Implies m_{A5} must be a set from V_{N-1}. The variable m_{A5} is restricted.
restricted_vars_flags[A5] = True
# Define the possible choices (domain) for each variable m_0, m_1, m_2.
# Initially, assume all elements of V_N are possible choices.
choice_sets = [list(V_N_element_ids) for _ in range(3)]
# Apply restrictions based on `restricted_vars_flags`.
for i in range(3):
if restricted_vars_flags[i]:
# If m_i is restricted, filter its choice set to include only IDs that are also in V_{N-1}.
choice_sets[i] = [id_val for id_val in choice_sets[i] if id_val in ids_V_N_minus_1_set]
# Precompute Python set objects for each set ID for faster subset and membership checks.
# `all_sets[i]` is a tuple representing the elements (by ID) of the set with ID `i`.
# `all_sets_as_python_sets[i]` is the corresponding Python set object.
all_sets_as_python_sets = { i : set(all_sets[i]) for i in range(len(all_sets)) }
# If any choice set becomes empty after applying restrictions, no solution is possible.
if not choice_sets[0] or not choice_sets[1] or not choice_sets[2]:
print("NO")
return
# Iterate through the restricted search space for assignments (id_0, id_1, id_2).
# This significantly reduces the number of checks compared to |V_N|^3 for large N.
for id_0 in choice_sets[0]:
for id_1 in choice_sets[1]:
for id_2 in choice_sets[2]:
# Current assignment: m_0 has ID id_0, m_1 has ID id_1, m_2 has ID id_2.
ids = [id_0, id_1, id_2]
# Map the A_k indices to the actual IDs based on the current assignment.
id_A0 = ids[A0]
id_A1 = ids[A1]
id_A2 = ids[A2]
id_A3 = ids[A3]
id_A4 = ids[A4]
id_A5 = ids[A5]
# Retrieve the precomputed Python set objects for the relevant IDs.
set_A0 = all_sets_as_python_sets[id_A0]
set_A1 = all_sets_as_python_sets[id_A1]
set_A2 = all_sets_as_python_sets[id_A2]
# Check the 5 conditions of the formula:
# Condition 1: m_{A0} \subseteq m_{A1}
# Check if the set represented by id_A0 is a subset of the set represented by id_A1.
if not set_A0.issubset(set_A1):
continue # If condition fails, try next assignment.
# Condition 2: m_{A1} \in m_{A2}
# Check if the ID representing set m_{A1} (which is id_A1) is an element of the set m_{A2}.
# `set_A2` contains the IDs of elements constituting the set m_{A2}.
if id_A1 not in set_A2:
continue
# Condition 3: m_{A3} \in m_{A2}
if id_A3 not in set_A2:
continue
# Condition 4: m_{A4} \in m_{A2}
if id_A4 not in set_A2:
continue
# Condition 5: m_{A5} \in m_{A0}
if id_A5 not in set_A0: # `set_A0` contains IDs of elements of m_{A0}.
continue
# If all 5 conditions are satisfied for this triple (id_0, id_1, id_2).
print("YES")
return # Found a satisfying assignment, exit.
# If the loops complete without finding any satisfying assignment.
print("NO")
# Execute the solver function.
solve()