結果
| 問題 | No.3408 1215 Segments |
| コンテスト | |
| ユーザー |
 kencho
|
| 提出日時 | 2025-12-09 22:32:04 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 734 ms / 2,500 ms |
| コード長 | 8,697 bytes |
| 記録 | |
| コンパイル時間 | 330 ms |
| コンパイル使用メモリ | 82,352 KB |
| 実行使用メモリ | 78,168 KB |
| 最終ジャッジ日時 | 2025-12-14 23:36:54 |
| 合計ジャッジ時間 | 11,823 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 46 |
ソースコード
import sys
# 再帰呼び出しを排除したため setrecursionlimit は不要ですが、
# 念のためインポートは残します。
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 = [None]
# -----------------------------------------------------
# 非再帰版: 最小値構築ロジック
# ターゲット文字列 target_str 以上で、構成 counts を満たす
# 最小の文字列を返す。存在しない場合は None。
# -----------------------------------------------------
def find_smallest_iterative(current_counts, total_digits, target_str, t_digits):
# -------------------------------------------------
# ケース1: 桁数がターゲットより多い場合
# -> 最小の非ゼロ数字を先頭にし、残りを昇順に並べる
# -------------------------------------------------
if total_digits > len(target_str):
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: 桁数が同じ場合
# -> ターゲットとの共通接頭辞(Prefix)を利用して探索
# -------------------------------------------------
# 戦略:
# 1. countsで target の先頭から最大何文字まで一致させられるか(max_p)を調べる。
# 2. 一致長 P = max_p から 0 まで逆順にループする。
# 分岐点 k (0 <= k <= P) において、target[k] より大きい数字 d を
# counts から選べるなら、それが「分岐点 k で成立する最小解」である。
# k を大きい方から試すことで、よりターゲットに近い（小さい）値が見つかる。
# 作業用カウント配列
temp_counts = list(current_counts)
L = len(target_str)
# 1. 最大一致長 max_p を計算
max_p = 0
for val in t_digits:
if temp_counts[val] > 0:
temp_counts[val] -= 1
max_p += 1
else:
break
# もし最後まで一致可能なら、それが最小値 (targetそのもの)
if max_p == L:
return target_str
# 2. 分岐点を後ろから探す
# temp_counts は現在 max_p 文字分減った状態
# k は「分岐するインデックス」
# k = max_p のときは、prefix一致の後、次の文字で勝負する（実際は不一致で止まった箇所）
for k in range(max_p, -1, -1):
# ループの初回以外は、一つ後ろの桁(target[k])を「使わなかった」ことにするので在庫に戻す
if k < max_p:
temp_counts[t_digits[k]] += 1
# 分岐点 k において、target[k] より大きい最小の数字を探す
current_digit_val = t_digits[k]
found_d = -1
# target[k] + 1 から 9 まで探索
for d in range(current_digit_val + 1, 10):
if temp_counts[d] > 0:
found_d = d
break
if found_d != -1:
# 見つかった場合、これより上位の桁での分岐より必ず小さくなるので確定
temp_counts[found_d] -= 1
# 結果構築: target[:k] + found_d + 残りを昇順
res = []
# 接頭辞
res.append(target_str[:k])
# 分岐文字
res.append(str(found_d))
# 残り（昇順）
for digit in range(10):
c = temp_counts[digit]
if c > 0:
res.append(str(digit) * c)
return "".join(res)
return None
# -----------------------------------------------------
# 整合性チェック関数 (変更なし、計算のみ)
# -----------------------------------------------------
def check_and_update(cnt, L):
c0, c1, c2, c3, c4, c5, c6, c7, c8, c9 = cnt
if (L + c0 + c6 + c8) & 1: return
base = (L + c0 + c6 + c8) >> 1
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 = c2 + c3 + c4 + c5 + c6 + c8 + c9
if s6 + zero != base: return
# 有効なら最小値を構築
candidate = find_smallest_iterative(cnt, L, n_str, target_digits)
if candidate is not None:
if best_ans[0] is None:
best_ans[0] = candidate
else:
# 文字列長比較 -> 辞書順比較
len_cand = len(candidate)
len_best = len(best_ans[0])
if len_cand < len_best:
best_ans[0] = candidate
elif len_cand == len_best and candidate < best_ans[0]:
best_ans[0] = candidate
# -----------------------------------------------------
# 非再帰 DFS: スタックを使用
# -----------------------------------------------------
def run_iterative_dfs(total_len):
# スタックの要素: [digit_index, current_val, remaining_sum]
# digit_index: 現在決めている数字 (0-8)
# current_val: counts[digit_index] として試している値 (-1は未処理を示す)
# remaining_sum: 残りの割り当て可能数
# 初期状態: 数字0について、まだ値は決めていない(-1)、残り全て(total_len)
stack = [[0, -1, total_len]]
while stack:
frame = stack[-1]
d = frame[0]
# 直前のループ処理のクリーンアップ（バックトラック）
if frame[1] != -1:
counts[d] = 0 # 戻す
# 次の値を試す
frame[1] += 1
val = frame[1]
rem = frame[2]
# ループ終了条件: 割り当て数が残り数を超えたら pop
if val > rem:
stack.pop()
continue
# 値をセット
counts[d] = val
if d == 8:
# 数字8まで決めたら、数字9は残り全てで確定
# ここで再帰の底の処理を行う
last_rem = rem - val
counts[9] = last_rem
check_and_update(counts, total_len)
counts[9] = 0
# 8のループを継続するため、ここではpopせず、次のループへ
continue
else:
# 次の深さ(d+1)へ
# 新しいフレームをプッシュ
stack.append([d + 1, -1, rem - val])
# -----------------------------------------------------
# メインループ
# -----------------------------------------------------
# 長さ L を Nの長さ から 20 まで探索
for l in range(length_n, 21):
best_ans[0] = None
run_iterative_dfs(l)
if best_ans[0] is not None:
print(best_ans[0])
break
if __name__ == '__main__':
main()