私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「カードを使って数を作ろう（両面編）」（CodeIQ）を参照してください。
【概要】
カードが何枚かあります。
カードには両方の面に、一桁の数字が書いてあります。同じ数字のこともあれば、異なる数字のこともあります。
カードをn枚選んで並べて数を作ります。並べる際には、カードのどちらの面を使っても構いません（もちろん、両面同時には使えません）。
作れる数のうち、ある数 m にもっとも近い数を答えてください。
【入出力】
入力は
4,1234,17/82/72/83/98/97/98
のような感じです。
コンマ区切りで、n(カードの枚数)、m(この値に近い数を作る)、カード列 が並んでいます。
カード列は、カードに書いてある数字をスラッシュ区切りで並べたものです。
カードの情報は、表の数字と裏の数字を区切り文字なしで並べたものです。 例えば上記の例は
ということを意味しています。
n( 使うカードの枚数 ) 4 m(この値に近い数を作る) 1234 1枚目のカード 表が1で裏が7 2枚目のカード 表が8で裏が2 3枚目のカード 表が7で裏が2 4枚目のカード 表が8で裏が3 5枚目のカード 表が8で裏が9 6枚目のカード 表が9で裏が7 7枚目のカード 表が9で裏が8
出力は、
1232
のような感じです。最も近い数が2つある場合は、小さい順に両方共出力してください。
1233,1235
のような感じです。
末尾の改行はあってもなくても構いません。
作れる数がひとつもない場合には、-を出力してください。
【補足】
「01」のような、「0」で始まる二桁以上の数は作れません。一桁の「0」はOKです。
カードの枚数は8枚以下です。
n は 1以上で、カードの枚数を超えることはありません。
m は 0以上、10の9乗以下です。
6 のカードを逆さにして 9 として使ったりすることはできません。
不正な入力に対処する必要はありません。
Rubyで解答しています。
#!/usr/bin/ruby
def toNum(m, ptn)
ret = [0]
ptn.each_with_index{|c, i|
n0 = c[0].to_i # 表の値
n1 = c[1].to_i # 裏の値
# 2桁以上の数値で先頭が0はエラー
if (ptn.size > 1) && (i == 0) && (n0 == 0) && (n1 == 0) then
ret = []
break
end
r = 10**(ptn.size - i - 1) # 桁（上の桁から決める）
# 値の候補を作る
cands = []
for j in ret
cands << j + n0*r
cands << j + n1*r
end
sm = 999999999
mr = (m/r) * r # mの上位(i-1)桁の値
for cd in cands
# 2桁以上の場合で候補値が0（=先頭が0）はエラー
if (ptn.size > 1) && (cd == 0) then next end
sb = cd-mr
# cdがmrより小さい場合、最後の桁の場合を除いてrを加えて評価しなければならない
# （例：m=200 cd=[100,200]の場合、100から199になる可能性があり、
# 199は201と同じ近さになるので100は候補に残さなければならない）
if (i != 0) && (sb < 0) then sb = (sb+r).abs
else sb = sb.abs
end
if sb < sm then
nxt = [cd]
sm = sb
elsif sb == sm then
nxt << cd
end
end
ret = nxt
}
return ret
end
def solve(n,m,cards)
ret = []
bs = 9999999999
cards.permutation(n){|ptn|
cands = toNum(m, ptn)
if cands.empty? then next end
s = (m-cands[0]).abs # 候補値はすべて同じだけ近いので最初の値だけを比較すれば良い
if s < bs then
ret = cands
bs = s
elsif s == bs then
ret = ret + cands
end
# 差が0に成ったらそれ以上の結果はないのでやめる
if s == 0 then break end
}
return ret.uniq.sort
end
def printResult(ptn)
if ptn.empty? then
puts("-")
else
puts(ptn.join(","))
end
end
while line = gets
line.strip!
if line.empty? then next end
sc = line.split(",")
n = sc[0].to_i
m = sc[1].to_i
cards = sc[2].split("/")
ret = solve(n,m,cards)
printResult(ret)
end
「カードを使って数を作ろう（簡単編）」の続編です。が、こちらの問題は★★★★となっています。
簡単編は総当たりで問題なかったのですが、こちらの問題では最悪の場合、2
引数n,m,cardsは入力値をパースして数値にしたものです。
cardsは["17","82","72","83","98","97","98"]のようなカードの値の配列です。
Rubyなのでcardsにpermutation()を使ってパターンを列挙します。
そしてtoNum()でパターンを数値に変換します。toNum()はcardsの裏表で作れる数値のうちmに最も近い値の配列を返します。エラー時は空の配列を返します。
そして帰ってきた候補値の最初の値（cands[0]）とmの差の絶対値を取り、以前の差の絶対値より小さくなっていたら結果を更新します。以前の差の絶対値と同値なら結果に追加します（61〜67行目）。toNum()が返す値とmとの差は全て同じなので最初の値のみの比較でOKです。
もし、差が0に成った（mを作ることができた）らそれ以上mに近い値は作れないので処理をやめます。
これがこのプログラムのいい加減な部分で、カードが「88/88/88/88/88/88/88/79」でm=88888888、n=8のような入力値の場合、処理を止めることができず時間切れになると思うのです。
結果は同じ値が重複していたり、順番が昇順になっていないのでuniqしてsortしてから返します。
引数ptnのカードの並びでmに最も近い値を作ります。
ptnの値を先頭から順に取り出し、裏表それぞれを数値(n0, n1)にします。
なお、仕様で先頭を0とした2桁以上の値はダメなのでチェックして弾きます（10〜13）行目。
値の候補を作ります。
まず、ptnの先頭要素が最も大きな位、最後の要素が1の位なので取り出した値の桁にします。15行目で後ろに何個0をつけるかを決定し、19〜22行目で取り出した値までの数値を作ります。
retは返却値の配列ですが、処理の途中では処理している桁までで最も近くなる可能性のある値が入っています（途中段階で最も近い値ではないことに注意してください）。
例えば、ptn=["17","82","72","83"]、m=1234で2回目のループの場合、この時点で1800と1200が作られます。
次に候補値を絞り込みます。
smはmと候補地の差です。
mrはmの現在処理している桁より後を0にしたものです（先の例で1234で上位2桁目を処理する時点ではmr=1200）。
candsに入っている候補値全てに対してmrとの差をとって最も近いものを選ぶのですが、1桁ごとに絞り込むので注意が必要です。コメントに書いてありますが、m=200で最も上の位を処理している時点の候補が[100,200]の場合、100を捨てることはできないのです。最終的に作れる数字が202と199だとすると199の方がmに近いので100を残しておかないと間違った結果になってしまいます。
そのため1の位を処理する場合以外は候補値とmrの差がマイナスの場合、rを差に加えて評価します。m=200で最上位桁処理時点の候補値が[100,200]の場合、mr=200なので候補値100との差は-100ですがr=100を加えると差は0になるので候補値200と同じ評価になります。
なお、1の位を処理している時はこのような加減をする必要はなく単に差の絶対値を評価するだけです。
全ての候補値に対して最もmに近い可能性のある値をチェックし、最上位の桁から1の桁まで繰り返して候補を絞り込みます。
なぜこのような面倒なことをしているかというと、こうすることで桁ごとに候補を絞り込めるので計算量を減らすことができるからです。ptn=["17","82","72","83"]、m=1234の場合、7878、7873、7828、7823、7278、7273、7228、7223という値は7000の時点で1000よりもmに近い値を作れる可能性はありません。同様に1800も1200よりもmに近い値を作れる可能性はないので以降の計算をする必要がありません。このように桁ごとに絞り込むことで計算量が相当減ります。
最初の方に書いた通り、テストケースにはありませんでしたが時間切れになるパターンはあるような気がします。じゃあ、どうするかというとtoNum()の先頭かtoNum()を処理する前に、その時点で最もmに近い候補値より近い値になる可能性のない値で始まるパターンは処理しない、程度の枝刈りでも計算量を27×7!くらいにできるのでこのくらいのカード枚数ならいけるんじゃないかと思っています。
ただ、カードの並び順は最上位の桁がmに近いものを含む順にソートするなどの工夫が必要でしょうが。