結果

問題 No.1963 Subset Mex
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:51:37
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,077 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 108,488 KB
最終ジャッジ日時 2025-05-14 12:52:10
合計ジャッジ時間 8,437 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

MOD = 998244353

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    s = list(map(int, input[1:n+1]))
    
    count = defaultdict(int)
    for num in s:
        count[num] += 1
    
    max_num = max(count.keys()) if count else 0
    
    state = tuple(sorted(count.items()))
    visited = set()
    queue = deque([state])
    visited.add(state)
    result = 0
    
    while queue:
        current = queue.popleft()
        result += 1
        
        current_dict = dict(current)
        elements = list(current_dict.keys())
        elements.sort()
        m = 0
        while m in current_dict:
            m += 1
        
        subset = []
        for x in elements:
            if x < m:
                subset.append(x)
        
        from itertools import combinations
        
        def generate_subsets(elements, counts):
            subset = []
            for x in elements:
                if counts.get(x, 0) > 0:
                    subset.append(x)
            n = len(subset)
            masks = [1 << i for i in range(n)]
            for mask in range(1, 1 << n):
                selected = []
                for i in range(n):
                    if mask & masks[i]:
                        selected.append(subset[i])
                yield selected
        
        for selected in generate_subsets(elements, current_dict):
            temp_dict = current_dict.copy()
            for x in selected:
                temp_dict[x] -= 1
                if temp_dict[x] == 0:
                    del temp_dict[x]
            
            mex = 0
            while mex in selected:
                mex += 1
            
            temp_dict[mex] = temp_dict.get(mex, 0) + 1
            
            new_state_items = sorted(temp_dict.items())
            new_state = tuple(new_state_items)
            if new_state not in visited:
                visited.add(new_state)
                queue.append(new_state)
    
    print(result % MOD)

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