結果

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

ソースコード

diff #
raw source code 

import sys

# 再帰深度の上限を緩和（念のため）
sys.setrecursionlimit(5000)

def main():
    # 高速I/O
    input = sys.stdin.readline
    
    try:
        line = input().strip()
        if not line:
            return
        n = int(line)
    except ValueError:
        return

    s = str(n)
    length_n = len(s)
    
    # 計算用バッファ（0-9の個数）
    counts = [0] * 10
    
    # 答えを格納するコンテナ（リストにして参照で書き換え可能にする）
    # Javaの static String minForLen に相当
    best_ans = [None]

    # -----------------------------------------------------
    # 内部関数定義 (クロージャとして実装)
    # -----------------------------------------------------

    def solve_recursive(idx, tight, current_counts, target_str):
        if idx == len(target_str):
            return ""
        
        start = int(target_str[idx]) if tight else 0
        
        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:
                    # 制約が外れた場合（targetより大きい桁を選んだ場合）
                    # 残りは辞書順最小（0から順に詰める）で作る
                    res = [str(d)]
                    for k in range(10):
                        if current_counts[k] > 0:
                            res.append(str(k) * current_counts[k])
                    
                    current_counts[d] += 1 # backtrack
                    return "".join(res)
                
                # 制約が続く場合
                res = solve_recursive(idx + 1, next_tight, current_counts, target_str)
                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, target_str):
        total_digits = sum(current_counts)
        
        if total_digits > len(target_str):
            # 桁数がtargetより多い場合、最小の非ゼロ数字を先頭にして残りを昇順
            for d in range(1, 10):
                if current_counts[d] > 0:
                    current_counts[d] -= 1
                    res = [str(d)]
                    for k in range(10):
                        if current_counts[k] > 0:
                            res.append(str(k) * current_counts[k])
                    current_counts[d] += 1 # backtrack
                    return "".join(res)
            return None
        else:
            # 桁数が同じ場合、target_str以上になる最小の並び替えを探す
            return solve_recursive(0, True, current_counts, target_str)

    def check_and_update(cnt, target_str, L):
        # 高速な妥当性チェック
        if (L + cnt[0] + cnt[6] + cnt[8]) % 2 != 0:
            return

        # Javaロジックのセグメント計算
        s0 = cnt[0] + cnt[2] + cnt[3] + cnt[5] + cnt[6] + cnt[7] + cnt[8] + cnt[9]
        s1 = cnt[0] + cnt[1] + cnt[2] + cnt[3] + cnt[4] + cnt[7] + cnt[8] + cnt[9]
        s2 = L - cnt[2]
        s3 = cnt[0] + cnt[2] + cnt[3] + cnt[5] + cnt[6] + cnt[8] + cnt[9]
        s4 = cnt[0] + cnt[2] + cnt[6] + cnt[8]
        s5 = cnt[0] + cnt[4] + cnt[5] + cnt[6] + cnt[8] + cnt[9]
        s6 = cnt[2] + cnt[3] + cnt[4] + cnt[5] + cnt[6] + cnt[8] + cnt[9]

        base = (s2 + s4) // 2
        nine = s3 - base
        one = base - s4
        zero = (s1 - one) - base
        seven = base - (s5 - zero + one)
        six = (s0 - zero) - base

        # 負の値チェック
        if one < 0 or zero < 0 or seven < 0 or six < 0 or nine < 0: return
        # 上限チェック
        if one > cnt[1]: return
        if zero > cnt[0]: return
        if seven > cnt[7]: return
        if six > cnt[6]: return
        if nine > cnt[9]: return

        # 整合性チェック
        if s0 - zero - six != base: return
        if s1 - one - zero != base: return
        if s2 - one != base: return
        if s3 - nine != base: return
        if s4 + one != base: return
        if s5 - zero + one + seven != base: return
        if s6 + zero != base: return

        # 有効なら最小値を構築
        candidate = find_smallest(cnt, target_str)
        
        if candidate is not None:
            if best_ans[0] is None:
                best_ans[0] = candidate
            else:
                # 辞書順比較 (長さ比較含む)
                if len(candidate) < len(best_ans[0]):
                    best_ans[0] = candidate
                elif len(candidate) == len(best_ans[0]) and candidate < best_ans[0]:
                    best_ans[0] = candidate

    def dfs(digit, remaining, current_counts, target_str, L):
        if digit == 9:
            current_counts[9] = remaining
            check_and_update(current_counts, target_str, L)
            current_counts[9] = 0 # backtrack
            return

        for i in range(remaining + 1):
            current_counts[digit] = i
            dfs(digit + 1, remaining - i, current_counts, target_str, L)
        
        current_counts[digit] = 0 # backtrack

    # -----------------------------------------------------
    # メインループ
    # -----------------------------------------------------
    for l in range(length_n, 21):
        best_ans[0] = None
        dfs(0, l, counts, s, l)
        
        if best_ans[0] is not None:
            print(best_ans[0])
            break

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