結果

問題 No.3408 1215 Segments
コンテスト
ユーザー kencho
提出日時 2025-12-09 21:30:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,755 ms / 2,500 ms
コード長 6,388 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 407 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 84,852 KB
最終ジャッジ日時 2025-12-14 23:36:42
合計ジャッジ時間 24,358 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

# 再帰制限の緩和
sys.setrecursionlimit(5000)

def main():
    # 高速I/O: 一括読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n_str = input_data[0]
    length_n = len(n_str)
    
    # ターゲット比較用の数値リスト（毎回文字をint変換するコストを省く）
    target_digits = [int(c) for c in n_str]
    
    # DFS用のカウント配列
    counts = [0] * 10
    
    # 答えの格納用（リストにして参照渡し可能にする）
    # best_ans[0] に現在の暫定最小解を保持
    best_ans = [None]

    # -----------------------------------------------------
    # 内部関数: 桁数分布から最小の数値を構築
    # -----------------------------------------------------
    def solve_recursive(idx, tight, current_counts):
        if idx == length_n:
            return []
        
        start = target_digits[idx] if tight else 0
        
        # 0-9のループ
        for d in range(start, 10):
            if current_counts[d] > 0:
                current_counts[d] -= 1
                next_tight = tight and (d == start)
                
                if not next_tight:
                    # 制約が外れたら残りは辞書順最小（昇順）で埋める
                    res = [str(d)]
                    # 0から9まで順に残りの個数分追加
                    for k in range(10):
                        c = current_counts[k]
                        if c > 0:
                            res.append(str(k) * c)
                    
                    current_counts[d] += 1 # backtrack
                    return res
                
                # 制約が続く場合
                res = solve_recursive(idx + 1, next_tight, current_counts)
                if res is not None:
                    current_counts[d] += 1 # backtrack
                    return [str(d)] + res
                
                current_counts[d] += 1 # backtrack
        
        return None

    def find_smallest(current_counts, total_digits, target_str_len):
        # ケース1: 桁数がターゲットより多い場合 -> 最小の非ゼロを先頭、残りを昇順
        if total_digits > target_str_len:
            for d in range(1, 10):
                if current_counts[d] > 0:
                    current_counts[d] -= 1
                    res = [str(d)]
                    for k in range(10):
                        c = current_counts[k]
                        if c > 0:
                            res.append(str(k) * c)
                    current_counts[d] += 1 # backtrack
                    return "".join(res)
            return None
        
        # ケース2: 桁数が同じ場合 -> target以上になる最小の並びを探す
        res_list = solve_recursive(0, True, current_counts)
        if res_list is not None:
            return "".join(res_list)
        return None

    # -----------------------------------------------------
    # 内部関数: セグメント整合性チェック (最深部)
    # -----------------------------------------------------
    def check_and_update(cnt, L):
        # 配列アクセスを減らすためローカル変数に展開
        c0, c1, c2, c3, c4, c5, c6, c7, c8, c9 = cnt

        # パリティチェック (s2 + s4) % 2 != 0 なら不可
        # s2 = L - c2
        # s4 = c0 + c2 + c6 + c8
        # sum_check = L + c0 + c6 + c8 (mod 2)
        if (L + c0 + c6 + c8) & 1:
            return

        # 基本となる base の計算
        # s2 = L - c2
        # s4 = c0 + c2 + c6 + c8
        # base = (s2 + s4) // 2
        # 展開して計算:
        base = (L + c0 + c6 + c8) >> 1

        # 各数字の必要数を計算し、持っている個数(cnt)と比較
        # 計算順序を工夫して早期returnを狙う

        # s4 は既出
        s4 = c0 + c2 + c6 + c8
        one = base - s4
        if one < 0 or one > c1: return

        s3 = c0 + c2 + c3 + c5 + c6 + c8 + c9
        nine = s3 - base
        if nine < 0 or nine > c9: return

        s1 = c0 + c1 + c2 + c3 + c4 + c7 + c8 + c9
        zero = s1 - one - base
        if zero < 0 or zero > c0: return

        s5 = c0 + c4 + c5 + c6 + c8 + c9
        seven = base - (s5 - zero + one)
        if seven < 0 or seven > c7: return

        s0 = c0 + c2 + c3 + c5 + c6 + c7 + c8 + c9
        six = s0 - zero - base
        if six < 0 or six > c6: return

        # 最後の整合性チェック
        # 変数定義に使わなかった独立な式 s6 について検証が必要
        # s6 + zero == base
        s6 = c2 + c3 + c4 + c5 + c6 + c8 + c9
        if s6 + zero != base:
            return
            
        # ここまで到達すれば有効な構成
        candidate = find_smallest(cnt, L, length_n)
        
        if candidate is not None:
            # 暫定解との比較
            curr_best = best_ans[0]
            if curr_best is None:
                best_ans[0] = candidate
            else:
                # 文字列長、次いで辞書順比較
                len_cand = len(candidate)
                len_best = len(curr_best)
                if len_cand < len_best:
                    best_ans[0] = candidate
                elif len_cand == len_best and candidate < curr_best:
                    best_ans[0] = candidate

    # -----------------------------------------------------
    # DFS
    # -----------------------------------------------------
    def dfs(digit, remaining, counts, L):
        if digit == 9:
            counts[9] = remaining
            check_and_update(counts, L)
            counts[9] = 0 # backtrack
            return

        # counts[digit] を 0 から remaining まで試す
        for i in range(remaining + 1):
            counts[digit] = i
            dfs(digit + 1, remaining - i, counts, L)
        
        counts[digit] = 0 # backtrack

    # -----------------------------------------------------
    # メインループ
    # -----------------------------------------------------
    # 長さ L を Nの長さ から 20 まで探索
    for l in range(length_n, 21):
        best_ans[0] = None
        dfs(0, l, counts, l)
        
        if best_ans[0] is not None:
            print(best_ans[0])
            break

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