AOJ（問題集）5
AIZU ONLINE JUDGE: Programming Challenge
0041 Expression
def solve(ary) if ary.size <= 1 return ary[0] if eval(ary[0]) == 10 else idxs = [*0...ary.size] idxs.combination(2) do |i, j| a, b = ary[i], ary[j] nxt = (idxs - [i, j]).map{|x| ary[x]} ["(#{a} + #{b})", "(#{a} - #{b})", "(#{b} - #{a})", "#{a} * #{b}"].each do |st| result = solve(nxt + [st]) return result if result end end end nil end until (given = $<.gets.chomp.split) == ["0", "0", "0", "0"] ans = solve(given) puts ans ? ans : 0 end
自信作（笑）。
0042 A Thief
i = 1 until (furoshiki = $<.gets.to_i).zero? table = {0 => 0} Array.new($<.gets.to_i) {$<.gets.split(",").map(&:to_i)}.each do |v, w| h = Hash.new(0) table.each {|key, value| h[key + w] = table[key] + v if key + w <= furoshiki} table.merge!(h) {|k, v1, v2| [v1, v2].max} end m = table.values.max result = table.select {|k, v| v == m}.sort {|a, b| a[0] <=> b[0]}.first puts "Case #{i}:", result[1], result[0] i += 1 end
典型的な動的計画法。
0043 Puzzle
def check(table) result = 0 if table.sum <= 2 result = 1 if table.find {|x| x == 2} else (1..7).each do |i| tmp = table.dup if tmp[i].nonzero? and tmp[i + 1].nonzero? and tmp[i + 2].nonzero? 3.times {|x| tmp[i + x] -= 1} result += check(tmp) return 1 if result.nonzero? end (1..9).each do |j| tmp1 = table.dup if tmp1[j] >= 3 tmp1[j] -= 3 result += check(tmp1) return 1 if result.nonzero? end end end end result end $<.readlines.map(&:chomp).map {|n| n.chars.map(&:to_i)}.each do |data| table = Array.new(10, 0) data.each {|i| table[i] += 1} result = (1..9).map do |i| added = table.dup added[i] += 1 next if added[i] > 4 check(added).nonzero? ? i : nil end.compact puts result.empty? ? 0 : result.join(" ") end
3.09秒かかった。
他の人の回答を見ていて気づいたが、check() メソッド内のループはネストさせる必要がない。書き直すと
def check(table) result = 0 if table.sum <= 2 table.find {|x| x == 2} else (1..7).each do |i| tmp = table.dup if tmp[i].nonzero? and tmp[i + 1].nonzero? and tmp[i + 2].nonzero? 3.times {|x| tmp[i + x] -= 1} return true if check(tmp) end end (1..9).each do |j| tmp1 = table.dup if tmp1[j] >= 3 tmp1[j] -= 3 return true if check(tmp1) end end false end end $<.readlines.map(&:chomp).map {|n| n.chars.map(&:to_i)}.each do |data| table = Array.new(10, 0) data.each {|i| table[i] += 1} result = (1..9).map do |i| added = table.dup added[i] += 1 next if added[i] > 4 check(added) ? i : nil end.compact puts result.empty? ? 0 : result.join(" ") end
これで 0.10秒。充分速い。
0044 Prime Number II
require 'prime' $<.readlines.map(&:to_i).each do |n| a = (n - 1).step(0, -1) {|i| break i if Prime.prime?(i)} b = (n + 1).step {|i| break i if Prime.prime?(i)} puts "#{a} #{b}" end
標準添付ライブラリを使うというインチキ。
0045 Sum and Average
all_price = amount = i = 0 $<.readlines.map {|x| x.split(",").map(&:to_i)}.each do |price, n| all_price += price * n amount += n i += 1 end puts all_price puts (amount / i.to_f).round
0046 Differential
max, min = 0, Float::INFINITY $<.readlines.map(&:to_f).each do |h| max = h if h > max min = h if h < min end printf "%.1f\n", max - min
0047 Cup Game
place = "A" $<.readlines.map {|x| x.chomp.split(",")}.each do |a, b| if place == a place = b elsif place == b place = a end end puts place
0048 Class
table = [["light fly", 0, 48.0], ["fly", 48.0, 51.0], ["bantam", 51.0, 54.0], ["feather", 54.0, 57.0], ["light", 57.0, 60.0], ["light welter", 60.0, 64.0], ["welter", 64.0, 69.0], ["light middle", 69.0, 75.0], ["middle", 75.0, 81.0], ["light heavy", 81.0, 91.0], ["heavy", 91.0, Float::INFINITY]] $<.readlines.map(&:to_f).each do |w| table.each {|name, bottom, top| puts name if bottom < w and w <= top} end
0049 Blood Groups
table = {"A"=>0, "B"=>1, "AB"=>2, "O"=>3}
nums = Array.new(4, 0)
$<.readlines.map {|a| a.chomp.split(",").last}.each do |type|
nums[table[type]] += 1
end
puts nums
