結果

問題 No.2121 帰属関係と充足可能性
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:37:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,228 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 81,424 KB
実行使用メモリ 53,780 KB
最終ジャッジ日時 2025-04-16 16:39:30
合計ジャッジ時間 3,048 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 47 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import combinations

def generate_vn(n):
    if n == 0:
        return []
    prev = generate_vn(n-1)
    prev_list = list(prev)
    subsets = []
    for mask in range(0, 1 << len(prev_list)):
        subset = []
        for i in range(len(prev_list)):
            if mask & (1 << i):
                subset.append(prev_list[i])
        subsets.append(frozenset(subset))
    return subsets

# Precompute V_0 to V_4
v = []
for i in range(5):
    vn = generate_vn(i)
    v.append(vn)
# V_5 is not generated due to its size, so handle N=5 as a special case

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:7]))
    A0, A1, A2, A3, A4, A5 = A

    if N == 0:
        print("NO")
        return

    # Handle N >=5 as special case (cannot generate V_5)
    if N >= 5:
        print("NO")
        return

    required_vars = {A1, A3, A4, A5}

    # Check if required_vars need to be in V_{N-1} which might be empty
    if (N-1 >=0) and (len(v[N-1]) == 0) and (len(required_vars) > 0):
        print("NO")
        return

    # Determine possible values for each variable
    possible = []
    for var in [0, 1, 2]:
        if var in required_vars:
            # Must be in V_{N-1}
            possible_var = v[N-1] if (N-1 >=0) else []
        else:
            possible_var = v[N]
        possible.append(possible_var)

    # Iterate through all combinations
    for m0 in possible[0]:
        for m1 in possible[1]:
            for m2 in possible[2]:
                m = [m0, m1, m2]
                # Condition 1: m[A0] subset of m[A1]
                if not m[A0].issubset(m[A1]):
                    continue
                # Condition 2: m[A1] in m[A2]
                if m[A1] not in m[A2]:
                    continue
                # Condition 3: m[A3] in m[A2]
                if m[A3] not in m[A2]:
                    continue
                # Condition 4: m[A4] in m[A2]
                if m[A4] not in m[A2]:
                    continue
                # Condition 5: m[A5] in m[A0]
                if m[A5] in m[A0]:
                    print("YES")
                    return
    print("NO")

if __name__ == "__main__":
    main()
0