GCJ 2017 Qualification Round B: Tidy Numbers
問題
与えられた整数Nについて、N以下で数字が左から昇順に並ぶ最大の数を求める。
例えば、132であれば、129が132以下で数字が1,2,9と昇順に並ぶ最大の数となる。
https://code.google.com/codejam/contest/3264486/dashboard#s=p1
方針
Nから順にデクリメントして条件にあうかチェック、、、みたいな実装だとSmallはクリアできてもlargeは時間がかかりすぎてしまう。
よって、単なる数字の並びの規則性という観点でロジックを考えると、
・左から数字をチェックしていき、降順になる箇所が見つかった場合、前の数字を一つ小さくし、以降の数字を全て9に変更する 例:14548 -> 14499 ・上記操作によりさらに一つ前の数字との大小関係が変わる場合は、同様の処理をもう一つ前の数字についても行う。これを繰り返す。 例:14438 -> 14399 -> 13999
となる。
実装
gets n = 1 STDIN.each_line do |line| digits = line.chomp.chars.map(&:to_i) prev = digits[0] for i in 1..(digits.size-1) if digits[i-1] < digits[i] then digits[i] = 9 digits[i-1] -= 1 j = i - 1 while(j < 0) do if digits[j-1] < digits[j] then digits[j] = 9 digits[j-1] -= 1 end j -= 1 end for j in (i+1)..(digits.size-1) digits[j] = 9 end break end end printf "Case #%d: ", n digits.select{|c| c < 0}.each do |c| print c end printf "\n" n += 1 end