結果

問題 No.2025 Select $k$-th Submultiset
ユーザー lam6er
提出日時 2025-03-20 20:57:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,948 bytes
コンパイル時間 561 ms
コンパイル使用メモリ 82,824 KB
実行使用メモリ 100,852 KB
最終ジャッジ日時 2025-03-20 20:57:23
合計ジャッジ時間 6,040 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, L = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    c = list(map(int, input[ptr:ptr+N]))
    ptr += N
    Q = int(input[ptr])
    ptr +=1
    queries = [int(input[ptr+i]) for i in range(Q)]
    
    def comb(m, k):
        if m < k:
            return 0
        if k == 0:
            return 1
        if k == 1:
            return m
        if k == 2:
            return m * (m -1) // 2
        if k == 3:
            return m * (m -1) * (m -2) // 6
        return 0
    
    def compute_ways(v, s):
        variables = list(range(v, N+1))
        n = len(variables)
        if n == 0:
            return 1 if s == 0 else 0
        total = 0
        for mask in range(0, 1 << n):
            bits = bin(mask).count('1')
            subset_sum = 0
            for j in range(n):
                if (mask >> j) & 1:
                    variable = variables[j]
                    subset_sum += (c[variable-1] + 1)
            available = s - subset_sum + (n -1)
            if available <0:
                continue
            sign = (-1)**bits
            current_comb = comb(available, n-1)
            total += sign * current_comb
        return max(total, 0)
    
    results = []
    for k in queries:
        sum_so_far =0
        selected = []
        valid = True
        for v in range(1, N+1):
            remaining = L - sum_so_far
            if remaining <0:
                valid = False
                break
            if v > N:
                if remaining ==0:
                    selected.append(0)
                else:
                    valid = False
                    break
                continue
            max_possible = min(c[v-1], remaining)
            sum_next = 0
            for u in range(v+1, N+1):
                sum_next += c[u-1]
            min_possible = max(0, remaining - sum_next)
            selected_a = None
            for a_v in range(max_possible, min_possible -1, -1):
                if a_v <0:
                    continue
                s_remaining = remaining -a_v
                if s_remaining <0:
                    continue
                if v == N:
                    if s_remaining ==0:
                        selected_a = a_v
                        break
                    else:
                        continue
                ways = compute_ways(v+1, s_remaining)
                if ways >=k:
                    selected_a = a_v
                    break
                else:
                    k -= ways
            if selected_a is None:
                valid = False
                break
            sum_so_far += selected_a
            selected.append(selected_a)
        if valid and sum_so_far == L:
            results.append(' '.join(map(str, selected)))
        else:
            results.append('-1')
    
    print('\n'.join(results))

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