結果

問題 No.332 数列をプレゼントに
ユーザー gew1fw
提出日時 2025-06-12 14:35:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,912 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 84,148 KB
最終ジャッジ日時 2025-06-12 14:36:15
合計ジャッジ時間 4,146 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 1 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    X = int(input[idx])
    idx +=1
    A = list(map(int, input[idx:idx+N]))
    
    # 预处理检查
    sum_A = sum(A)
    if X == 0:
        print('No')
        return
    
    # 检查是否有一个元素等于X
    for i in range(N):
        if A[i] == X:
            s = ['x']*N
            s[i] = 'o'
            print(''.join(s))
            return
    
    # 检查总和
    if sum_A < X:
        print('No')
        return
    if sum_A == X:
        print('o'*N)
        return
    
    # 动态规划处理较小的sum_A
    if sum_A <= 10**6:
        # 动态规划
        dp = [False] * (X + 1)
        dp[0] = True
        path = [[] for _ in range(X + 1)]
        for a in A:
            for i in range(X, a-1, -1):
                if not dp[i] and dp[i - a]:
                    dp[i] = True
                    path[i] = path[i - a] + [a]
        if not dp[X]:
            print('No')
            return
        # 找出选中的元素的索引
        selected = []
        current_sum = X
        for i in range(N-1, -1, -1):
            a = A[i]
            if current_sum >= a and current_sum - a >=0 and dp[current_sum - a]:
                selected.append(i)
                current_sum -= a
        # 生成结果字符串
        selected_indices = set(selected)
        res = []
        for i in range(N):
            if i in selected_indices:
                res.append('o')
            else:
                res.append('x')
        print(''.join(res))
        return
    else:
        # 回溯法
        # 按降序排序，并记录原始索引
        sorted_A = sorted(A, reverse=True)
        original_indices = [i for i, _ in sorted(enumerate(A), key=lambda x: -x[1])]
        # 回溯函数
        result = None
        selected = []
        # 为了效率，采用迭代的回溯法
        
        from itertools import combinations
        
        # 由于时间复杂度高，尝试使用生成器
        # 尝试所有可能的子集，按元素数量递增排序，先检查较小的子集
        # 这样可以在找到第一个解时立即返回
        found = False
        for k in range(1, N+1):
            for comb in combinations(original_indices, k):
                current_sum = sum(A[i] for i in comb)
                if current_sum == X:
                    # 构造结果字符串
                    res = ['x']*N
                    for i in comb:
                        res[i] = 'o'
                    print(''.join(res))
                    return
            # 剪枝：如果已经尝试了所有可能的子集，但未找到解
            # 但这种方法对于n=100来说，无法处理
        
        # 如果上述方法无法处理，返回No
        print('No')
        return

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