結果

問題 No.1630 Sorting Integers (Greater than K)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:08:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,205 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 88,516 KB
最終ジャッジ日時 2025-06-12 20:14:42
合計ジャッジ時間 4,591 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 5 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N, K = sys.stdin.readline().split()
    N = int(N)
    K = K.strip()
    c = list(map(int, sys.stdin.readline().split()))
    len_K = len(K)
    
    if len_K < N:
        digits = []
        for i in range(9):
            digits += [str(i+1)] * c[i]
        digits.sort()
        M = ''.join(digits)
        print(M)
        return
    elif len_K > N:
        print(-1)
        return
    else:
        # len_K == N
        digits = []
        for i in range(9):
            digits += [str(i+1)] * c[i]
        digits.sort()
        minimal_M = ''.join(digits)
        if minimal_M > K:
            print(minimal_M)
            return
        
    # Now, need to find the next higher M
    # Implement the helper function
    def helper(suffix, c):
        M = len(suffix)
        c = c.copy()
        for i in range(M):
            for d in range(1, 10):
                if c[d-1] == 0:
                    continue
                if d < int(suffix[i]):
                    continue
                # Try d
                c[d-1] -= 1
                if d > int(suffix[i]):
                    # Remaining digits can be arranged in the smallest way
                    remaining = []
                    for j in range(9):
                        remaining += [str(j+1)] * c[j]
                    remaining.sort()
                    if len(remaining) != M - i - 1:
                        c[d-1] += 1
                        continue
                    constructed = str(d) + ''.join(remaining)
                    if constructed > suffix[i:]:
                        c[d-1] += 1
                        return constructed
                    else:
                        c[d-1] += 1
                        continue
                else:
                    # d == int(suffix[i])
                    # Need to find a suffix for the remaining digits
                    res = helper(suffix[i+1:], c.copy())
                    if res is not None:
                        constructed = str(d) + res
                        if constructed > suffix[i:]:
                            c[d-1] += 1
                            return constructed
                        else:
                            c[d-1] += 1
                            continue
                    else:
                        c[d-1] += 1
                        continue
        return None
    
    # Now, try to construct M
    # We need to find the earliest position where we can choose a digit >= K[i]
    # and then find a valid suffix
    # c is the list of counts
    # Convert K into a list of characters for easy access
    K_list = list(K)
    for i in range(N):
        for d in range(1, 10):
            if c[d-1] == 0:
                continue
            if d < int(K_list[i]):
                continue
            # Try d
            c[d-1] -= 1
            if d > int(K_list[i]):
                # The remaining digits can be arranged in the smallest way
                remaining = []
                for j in range(9):
                    remaining += [str(j+1)] * c[j]
                remaining.sort()
                if len(remaining) != N - i - 1:
                    c[d-1] += 1
                    continue
                M_candidate = K[:i] + str(d) + ''.join(remaining)
                if M_candidate > K:
                    print(M_candidate)
                    return
                else:
                    c[d-1] += 1
                    continue
            else:
                # d == int(K_list[i])
                # Need to find a valid suffix
                c_copy = c.copy()
                c_copy[d-1] -= 1
                suffix = K[i+1:]
                res = helper(suffix, c_copy)
                if res is not None:
                    M_candidate = K[:i] + str(d) + res
                    if M_candidate > K:
                        print(M_candidate)
                        return
                    else:
                        c[d-1] += 1
                        continue
                else:
                    c[d-1] += 1
                    continue
    print(-1)

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