結果

問題 No.2025 Select $k$-th Submultiset
ユーザー gew1fw
提出日時 2025-06-12 15:27:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,154 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 106,860 KB
最終ジャッジ日時 2025-06-12 15:27:53
合計ジャッジ時間 5,118 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def comb(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    if k == 0 or k == n:
        return 1
    return comb(n, k-1) * (n - k + 1) // k

def compute_ways(rem, *constraints):
    n = len(constraints)
    total = 0
    for mask in range(0, 1 << n):
        bits = bin(mask).count('1')
        sum_d = 0
        for j in range(n):
            if mask & (1 << j):
                sum_d += (constraints[j] + 1)
        rem_adj = rem - sum_d
        if rem_adj < 0:
            continue
        ways = comb(rem_adj + n - 1, n - 1)
        if bits % 2 == 0:
            total += ways
        else:
            total -= ways
    return max(0, total)

def find_kth_submultiset(total, k_prime, N, L, c):
    remaining = L
    counts = [0] * (N + 1)
    for i in range(1, N + 1):
        max_xi = min(c[i-1], remaining)
        for xi_candidate in range(max_xi + 1):
            rem = remaining - xi_candidate
            if rem < 0:
                continue
            if i == N:
                ways = 1 if rem == 0 else 0
            else:
                ways = compute_ways(rem, *c[i:])
            if ways < k_prime:
                k_prime -= ways
            else:
                counts[i] = xi_candidate
                remaining = rem
                break
        else:
            return None
    return counts[1:]

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    L = int(input[ptr])
    ptr += 1
    c = list(map(int, input[ptr:ptr + N]))
    ptr += N
    Q = int(input[ptr])
    ptr += 1
    queries = []
    for _ in range(Q):
        queries.append(int(input[ptr]))
        ptr += 1

    if N == 1:
        if L > c[0]:
            total = 0
        else:
            total = 1
    else:
        total = compute_ways(L, *c)

    for k in queries:
        if k > total or total == 0:
            print(-1)
            continue
        k_prime = total - k + 1
        counts = find_kth_submultiset(total, k_prime, N, L, c)
        if not counts:
            print(-1)
            continue
        print(' '.join(map(str, counts)))

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