私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「限られた数字で作れる数の、まんなかの値」（CodeIQ）を参照してください。
【概要】
たとえば。
0, 4, 5以外の数を使わずに作ることができる3桁以下の非負の整数は、
0, 4, 5, 40, 44, 45, 50, 54, 55, 400, 404, 405, 440, 444, 445, 450, 454, 455, 500, 504, 505, 540, 544, 545, 550, 554, 555
の27個です。中央は14番目の数なので、求める値は444になります。
このような感じで、桁数の最大値と使える数字を与えますので、作ることができる数の中央の値を求めてください。
【入出力】
入力は
3 045こんな感じです。
空白の前が桁数の上限。空白の後が使える数字です。使える数字は重複なく昇順に並んでいます。
出力は、
444のように、中央の値を出力してください。
作れる数が偶数個の場合には、中央に近い数を2つ、小さい順にコンマ区切りで並べてください。
【例】
入力 出力 3 045 444 1 012789 2,7 10 059 5555555555
【補足】
桁数の上限の最小値は 1 。最大値は 15 です
不正な入力に対処する必要はありません
Rubyで解答しています。
#!/usr/bin/ruby
def parse(line)
n,ns = line.split
nums = ns.split("")
return [n.to_i, nums]
end
def solve(line)
r, nums = parse(line)
ret = nil
if nums.size > 1 then
ret = solveNumsSizeGt1(r, nums)
else
ret = solveNumsSizeIs1(r, nums)
end
puts ret.join(",")
end
def solveNumsSizeIs1(r, nums)
# 0しか数字がない場合、0しか作れないので例外的に扱う
if nums[0].to_i == 0 then
return [0]
end
mid = []
if r%2 == 0 then
mid << r/2
mid << r/2+1
else
mid << r/2+1
end
ret = []
for m in mid
ret << (nums[0] * m).to_i
end
return ret
end
def solveNumsSizeGt1(r, nums)
n = nums.size
smx = (n-1).to_s * r # n進数のr桁
mx = smx.to_i(n) # 数値に直す
# numsが0を含まない場合、指定された桁数未満の数のことを考慮しなければならない
if !nums.include?('0') then
small = 0
for i in 1...r
small += n**i
end
# smallの分左にずれるのでmxから引く
mx -= small
end
# 中央の値
# 処理は0始まりなのでmxが偶数の場合、奇数個の数字がある
mid = []
if mx % 2 == 1 then
mid << mx/2
mid << mx/2 + 1
else
mid << mx/2
end
ret = []
for m in mid
ret << getPrintNum(m, r, nums).to_i
end
return ret
end
def getPrintNum(n, r, nums)
pos = n.to_s(nums.size).rjust(r, '0').split("").map{|a| a.to_i}
str = ""
for i in pos
str += nums[i]
end
return str
end
# main
while line = gets
line.strip!
if line.empty? then next end
solve(line)
end
★★の問題としては難しいです。私の考え方意外にも方法があるかもしれませんが、作ることのできる数のリストを作ることなく真ん中の値を作り出すロジックを考えつかなければできないと思います(あまりにもパターンが多いため)。
また、特殊なパターンが多いのも注意すべき点です。
まず、単純に全ての数を列挙した場合、1015もあります。列挙してから真ん中の値を表示するのではとても時間的に間に合いません。何パターンの数を作ることができるかを計算し、そのパターン数の真ん中の番号から目的の数だけを作るようにしなければなりません。
012で作れる3桁以下の数を考えてみます。これは0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, 222の27個であることはわかるでしょう。これは3進数で3桁以下の数と同じです。
同様に、0〜n-1まで順番に並んだ数であればn進数で表現できる数になります。
そして、例の045の場合と上記012の場合を比較してみましょう。すると1を4、2を5に置き換えると例のパターンになります。
つまり、入力値で与えられる使用可能な数の数に等しい進数で作れる数を考え、入力値で与えられた数と対応する数を置き換えれば良いことになります。これは入力値の数を配列として考えて配列の添字で作れる数から求めることができます。
例の045なら[0,4,5]の添字0,1,2で数を作り、添字の位置にある数で置き換えれば良いということになります。
また、入力値の数に0を含む場合、真ん中の値はn進数で指定された桁数の最大値と0の最大値÷2+1（2個ある場合は最大値÷2と最大値÷2+1）になります。
ただし、入力値に0を含まない場合、ここまで説明した方法では指定された桁数の数しか作れません。なので、入力値に0を含まない場合は指定された桁数未満の数の数を考慮しなければなりません。
また、使用可能な数が1種類しかない場合、1進数というのは成立しないので特殊なパターンとして扱う必要があります。また、使用可能な数が1種類で0の場合、0しかない場合は0しか作れないのでこれも特殊なパターンになります。
入力値をパースして使用可能な数の種類によって処理を分けます。
入力値のパースはparse()で行い桁数と数の配列を得ます（10行目、処理は3〜7行目）。
使用可能な数が1種類しかない場合はsolveNumsSizeIs1()、それ以外はsolveNumsSizeGt1()に処理を移譲します。
使用可能な数が1種類しかない場合の処理です。
使用可能な数が0の場合は0しか作れないので[0]を返して終わります（24〜16行目）。
それ以外の場合は桁数の真ん中の数だけ使用可能な数を並べたものを返します。
使用可能な数が2以上ある場合の処理です。
考え方で説明した通りの処理をします。
まず、使用可能な数の数から何進数かを決定します（45行目）。
n進数で作れる最大の数を求めます（47〜48行目）。n進数の最大値は(n-1)を指定された桁数だけ並べたものになります。同時にその数は入力値の使用可能な数に0を含む場合のパターン数になります。
50〜59行目は入力値の使用可能な数に0を含まない場合の処理です。
私のロジックで入力された数の配列を元に数を作った場合、入力値が「3 123」だったとすると一番小さな数は「111」になります。しかし、問題では「1〜33」までの数も作成可能なのでこれらの数のことを考えなければなりません。
指定された桁数未満の数のパターン数は桁数をrとするとni（ただし、1≦i≦(r-1)、nは使用可能な数の数）のi=1からi=r-1までの合計です。
これは必ず小さい側に並ぶ数で、その個数はr桁の数の数の1/2以下になります。例えば、3進数で3桁なら3桁の数は27個、1〜2桁の数（0を含まない）は3+9=12個しかありません。2進数で2桁の場合は2桁の数が4個、1桁の数は2個です。
この性質を利用すると、入力値で指定された数で作れる指定された桁数の数の個数から、指定された桁数未満の数の個数を引いてしまえば良いことがわかります。入力値が「2 12」なら「1,2,11,12,21,22」を作れますが、2桁の数を大きい方から2個減らすと「11,12」となり、これが真ん中の値になります。
次に真ん中の値を求めます。
変数mxは作成可能な数のパターン数-1（入力値に0を含まない場合は指定された桁数未満の数だけ減らしたパターン数）なのでこの1/2（端数切り捨て）+1が真ん中の値になります。パターン数が偶数の場合は1/2の値も答えになります。
何パターン目の数が真ん中の値かがわかったので答えの数にします。
これはgetPrintNum()で行います。
引数は何パターン目の数か、rは桁数、numsは入力値で与えられた使用可能な数の配列です。
80行目の処理でnをnumsの要素数進数（nums=[045]なら3進数）の文字列にし、桁数が揃うように0埋めします（n=13, r=3なら"111"にします）。そしてその文字を1文字ずつ取り出して再度数字に直し、numsの添字として扱います（nums[1]を3個つなげた数なので"444"になります）。
私のコードはちょっとごちゃっとしています。入力された数で作れる数の最大値はn進数のr桁の最大値として求めていますが、これはnrでも同じなで、このように処理すると入力値に0を含まない場合に考慮する数の個数と同じ計算方法になります。これだけでももう少しシンプルにできそうです。
ただ、この問題の処理方法（何番目の数かがわかればそれをn進数に変換して入力値の数の配列の添字として扱って答えを求める）と言う方法は割とすんなり思いつきました。しかし、思いつかずにものすごく悩み込んでしまう可能性もあったと思うので、これはついていたとしか言いようがない気がします。