私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「単調増加で単調減少な数」（CodeIQ）を参照してください。
【概要】
たとえば、
179のような数のことを「10進数で狭義単調増加な数」と呼ぶことにします。
つまり、各桁を見ると狭義単調増加列になっています。
逆に、
8631のような数のことを「10進数で狭義単調減少な数」と呼ぶことにします。
つまり、各桁を見ると狭義単調減少列になっています。
さて、
a進数で狭義単調増加、b進数で狭義単調減少な数のうち、もっとも大きな数を求めるプログラムを書いてください。
【入出力】
入力は
5 6こんな感じで標準入力から来ます。
スペース区切りで２つの10進数が並んでいます。
スペースの前が先程の a、つまりa進数で表記すると狭義単調増加になります。
スペースの後は先程の b、つまりb進数で表記すると狭義単調減少になります。
出力は、条件を満たす値を 10 進数で。先ほどの入力なら、
19を出力すると正解です。
【例】
入力 出力 a進数 b進数 5 6 19 34 31 6 11 101 245 92 4 3 7 13 21
【補足】
不正な入力に対処する必要はありません。
長さ1でも狭義単調増加列になります。
a も b も、2以上16以下です。
Rubyで解答しています。
#!/usr/bin/ruby
# b進数で単調減少する最大の数を返す
def getMaxOfCBA(b)
lst = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
return lst[0...b]
end
# a進数で単調増加する最大の数を返す
def getMaxOfABC(a)
return (1...a).to_a.reverse
end
# a進数で単調増加する最大数よりも大きく、b進数で単調減少する最大数以下で最も桁数の少ないもののうち最大の数を返す。
# 多少無駄がある
def getRangeMax(a, b)
mx_a = getMaxOfABC(a)
mx_b = getMaxOfCBA(b)
# printf("mx_a=%s, mx_b=%s\n", mx_a, mx_b) # DEBUG
va = toDecimal(mx_a, a)
vb = toDecimal(mx_b, b)
if va < vb then
len_a = va.to_s(b).size
len_b = mx_b.size
if len_a > len_b then return mx_b
else return mx_b[len_b-len_a, len_b]
end
else return mx_b
end
end
# 単調減少する次の数を返す
def getNext(lst, mx)
ret = lst.dup
ret.each_with_index{|v, i|
if v > i then
ret[i] -= 1
for j in 1..i
k = i - j
ret[k] = ret[k+1]-1
end
return ret
end
}
# 桁が1つ小さくなる場合
st = mx.size - lst.size + 1
return mx[st..-1]
end
# lstに渡されたb進数の単調減少の数のリスト（要素番号の大きい方が大きな桁）がa進数で単調増加かをチェックする
def isABC(lst, a, b)
vb = lst.reverse.map{|v| v.to_s(b)}.join("")
va = vb.to_i(b).to_s(a)
# printf("%s, %s\n", va, vb) # DEBUG
lst_a = va.split("")
for i in 1...lst_a.size
if lst_a[i-1] >= lst_a[i] then return false end
end
return true
end
# lstの配列の値を10進数の数値になおす
def toDecimal(lst, r)
return lst.reverse.map{|v| v.to_s(r)}.join("").to_i(r)
end
# 問題を解く
def solve(a, b)
mx = getRangeMax(a, b)
lst = mx
while !lst.empty?
if isABC(lst, a, b) then break end
lst = getNext(lst, mx)
end
return toDecimal(lst, b)
end
# main
while line = gets
line.strip!
if line.empty? then next end
a,b = line.split.map{|v| v.to_i}
p solve(a, b)
end
★★ですが結構難しいです。同日に公開された★★★のIPアドレスの範囲チェックをする問題よりもはるかに難しいです。
問題は「最大の数を求めよ」なので大きな数からカウントダウンして行って、条件を満たす数を発見したらそこで処理をやめれば良い、というのはすぐにわかります。しかし、総当たりした場合、最大の数は0xFEDCBA987654321で非常に大きな数になります。総当たりしていては絶対に間に合いません。
入力値に対して最大の数はn進数で使える数字を降順に並べたものなのはすぐにわかります。そして、これは単調減少数です。
ということはb進数で単調減少数となる数を大きい方から順番にa進数で単調増加数になるかをチェックして行けば問題は解けます。
私は引っかかったのですが、最悪のパターンa=2, b=16の時はRubyだと時間が足りませんでした。なのでもう一工夫します。
a進数の単調増加数とb進数の単調減少数でそれぞれの最大値の小さい方より大きい数は考える必要がないということは簡単にわかります。なので、a進数の単調増加数とb進数の単調減少数の最大値の小さい方から開始して、単調減少数を大きい方から順に順番にa進数で単調増加数になるかをチェックして行く、というのが解法になります。
入力値を数値に変換してsolve()に渡します。
getRangeMax()でa進数の単調増加数とb進数の単調減少数の最大値のうち小さい方を含む同じ桁数の最大の単調減少数を取得します（80行目）。これはちょっと無駄で、a進数の単調増加数とb進数の単調減少数の最大値のうち小さい方以下で最大の単調減少数から初めて良いと思うのですが、大した問題ではないのとコードの処理の方が簡単だったので妥協しました。
83〜86行目のループでb進数の単調減少数をmxから初めて大きい順に取得し（85行目）、a進数の単調増加数であるかをチェックします（84行目）。条件を満たしたらループを抜けます。
ループを抜けてきたらtoDecimal()でb進数の値を10進数の数値に直して返します。
この処理で扱うb進数の数は数値ではなく桁ごとの配列です。例えば、0xFEDCBA9876543210は[0x0,0x1,0x2,0x3,0x4,0x5,0x6,0x7,0x8,0x9,0xa,0xb,0xc,0xd,0xe,0xf]になっています。
a進数の単調増加数とb進数の単調減少数の最大値のうち小さい方を含む最小の単調減少数を返す関数です。
getMaxOfABC(a)でa進数の単調増加数の最大値、getMaxOfCBA(b)でb進数の単調減少数の最大値を取得します（17〜18行目）。
それぞれの値を10進数に直して（22〜23行目）大小を比較し（25行目）ます。
a進数の単調増加数の最大値の方が大きい場合、a進数の単調増加数の最大値とb進数の単調減少数の最大値のうち小さい方の桁数を求め、その桁数に治る最大のb進数で単調減少数を返します（26〜31行目）。
b進数の単調減少数の最大値の方が小さければそれを返します（32行目）。
b進数の単調減少数の最大値を返します。
16進数が最大とわかっているので0〜15までの配列を用意しておいて、その部分配列を返せば目的の処理になります。
a進数の単調増加数の最大値を返します。
1以上a未満の整数の降順の配列を返せば目的を満たせます。
単調減少数でlstに渡された値の次に小さな値を返します。具体的にどのようになるかというと、321から320、310、210、32、31、30、21、20、2、1、0というように値を返します。
mxは最大の単調減少数です。
lst、mxともに[0x0,0x1,0x2,0x3,0x4,0x5,0x6,0x7,0x8,0x9,0xa,0xb,0xc,0xd,0xe,0xf]のような配列表現であることに注意してください。
引数を壊したくないので値をコピーします（38行目）。
単調減少数の各桁の値は配列表現の添字番号より小さくなりません。なので、前回の値を下の桁から順にループし（39〜50行目）、添字番号より大きな値になっているかをチェックします（40行目）。添字番号より大きな値を持つ桁があればそこを1減らし（41行目）、それより下の桁の値を1ずつ小さい値にします。
例えば、5進数で410の次の値を求める場合を考えてみます。これの配列表現は[0,1,4]で要素0と1はこれ以上小さくできません。要素2は3にできますので3にしますが、310は410の次に小さい値ではありません。1小さくなった桁から下の桁は単純減少数になる最大の値にしなければならないので、[3-2,3-1,3]=[1,2,3]に再計算するわけです。
すべての桁が添字番号と同じ数の場合、最上位桁を0にすることになります。そして、1桁少なくなった単調減少数は最大値を上位の桁から必要な桁数だけ選んだものになります（53〜54行目）。例えば、5進数で210の次は43で、これは43210の先頭から2桁分を選んだものというわけです。
lstの配列表現のb進数の数がa進数で単純増加数かをチェックし、単純増加数ならtrue、違えばfalseを返します。
lstをb進数の文字列表現に直します（59行目）。
それをさらにa進数の文字列表現に直します（60行目）。
その各桁の値が1上の桁以上なら単調増加数にならないのでfalseを返します（64〜68行目）。
すべての桁が1つ上の桁よりも小さな値なら単調増加数なのでtrueを返します（70行目）。
r進数の配列表現の数を10進数の数値に直して返します。
この問題は全体の方針としてはそれほど難しくはないのですが、細部がややこしいです。最大のポイントは単調減少数で順次小さい数を作ることだと思いますが、これに存外手こずりました（整理がついていないままコーディングを始めているからでしょうが）。
あと、本文でも言及しましたがカウントダウンを始める数がちょっと大きくて、無駄なのが引っかかっています。a進数で単調増加数の最大値の方が小さい時に、それ以下の最大のb進数で単調減少数を取得する効率の良い方法ってあるんでしょうか？