次は一人ゲーム。これは最初、論理的に最小値を求めるロジックがあるのかと思ってさんざん考えたけど、思いつかなかったのであきらめて総当りで計算することにした。
ロジックは、すべての要素が0になるまで2で割り続ける→そのうち5で割り切れるものが 1つでもあればそのセットを覚える→そのセットのコンビネーションを計算→そのうち、結果的にすべての要素が5で割り切れていれば、その手数を覚える。→覚えた手数のうち最小のものが答え、という感じにした。
言語はrubyで書いた。コンビネーションのメソッドはググッてヒットしたものを使わせて頂きました。
#!/usr/bin/env ruby
class Array
def combination(num)
return [] if num < 1 || num > size
return map{|e| [e] } if num == 1
tmp = self.dup
self[0, size - (num - 1)].inject([]) do |ret, e|
tmp.shift
ret += tmp.combination(num - 1).map{|a| a.unshift(e) }
end
end
end
def devide(depth, master, ary)
ary4 = ary.collect{|k| if (k % 5 == 0) then 1 else 0 end}
master << ( [depth ] << ("0b" + ary4.join).oct )
ary2 = ary.collect{|i| i / 2 }
ary3 = ary2.select{|j| j == 0}
if ary3.size != ary2.size
depth = depth + 1
devide(depth, master, ary2)
end
return master
end
def solver(num, ary)
master=[]
depth=0
master = devide(depth, master, ary)
min = master.size + 1
master.reject! {|x| x[1] == 0}
1.upto(master.size){|i|
combi = master.combination(i)
combi.each{|j|
mask = 0
maxc = 0
j.each{|k|
mask = mask | k[1]
if( k[0] > maxc )
maxc = k[0]
end
}
if ( ((2 ** ary.size) - 1) == mask )
if ( min > maxc + j.size)
min = maxc + j.size
end
end
}
}
puts min
end
body=File.open(ARGV[0]).readlines
1.upto(body[0].to_i){|i|
solver(body[i * 2 - 1 ].chop, body[i * 2].split("\s").collect{|j| j.to_i})
}ary2とか3とか 4とかいうのが非常に汚い。