読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

Google Code Jam Qualification Round 2017 B

B Tidy Numbersは数字(の10進数表現)が1123456など非減少列になってるものをtidyと定義し、与えられたN以下で最大のtidy数を求めるもの。まずはtidyかどうかを判定するメソッドtidy?を作る。次に、与えられたNがtidyならそれを出力して終了なのでtidyでないとする。すると、Nを1ずつ減らしていきtidy数を見つけることになるが、その場合は1桁目は必ず9になることが分かる。そこで1桁目を忘れて1桁少ない数字が最初に与えられたとして同じようにtidy数を構築して、最終的にそれに9をくっつければOK。またDecrease-and-Conquerだ(笑) 今回は桁数が高々18桁なので再帰関数で書いてみた。一応、ブルートフォース版で小さい数でチェックもし、万全を期す。

def tidy?(n)
    n.to_s.bytes.each_cons(2).all?{|a,b|a<=b}
end

def bf_max_tidy(m)
    m.downto(1){|n|return n if tidy?(n)}
end

def rec_max_tidy(m)
    return m if m<10
    return m if tidy?(m)
    return rec_max_tidy((m-1-(m%10))/10)*10+9
end

gets.to_i.times{
  n=gets.to_i
  write(rec_max_tidy(n))
}