AOJ(問題集)10
AIZU ONLINE JUDGE: Programming Challenge
0091 Blur
L = 10 table = [[[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2], [-1, 2], [-2, 2], [1, 2], [2, 2], [0, 3], [-1, 3], [1, 3], [0, 4]], [[0, 0], [1, 0], [2, 0], [0, 1], [1, 1], [2, 1], [0, 2], [1, 2], [2, 2]], [[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2]]] n = $<.gets.to_i cloth = $<.readlines.map {|l| l.split.map(&:to_i)} copy = ->(ary) { ary.map {|l| l.dup} } form = ->(x, y, i) { case (j = 3 - i) when 1 then "#{x} #{y + 1} #{j}" when 2 then "#{x + 1} #{y + 1} #{j}" when 3 then "#{x} #{y + 2} #{j}" else nil end } try = ->(place, field, co, order = []) { # にじみがあるまでスキップ x = y = nil loop do return false if place >= L * L x, y = place % L, place / L break if field[y][x].nonzero? place += 1 end result = false # 大、中、小の滴を順に試す table.each_with_index do |drip, i| tmp = copy.(field) catch(:jump) do # 滴を試す(適合しなければ大域脱出で次の滴へ) drip.each do |po| x1, y1 = x + po[0], y + po[1] throw(:jump) if x1 < 0 or x1 >= L or y1 >= L or tmp[y1][x1].zero? tmp[y1][x1] -= 1 end # 滴が適合した場合の処理 co -= 1 prc = form.(x, y, i) if co.zero? if tmp.flatten.map(&:zero?).all? return order + [prc] #解が発見された場合(一気にリターン) else co += 1 throw(:jump) end end result = try.(place, tmp, co, order + [prc]) return result if result co += 1 end end result } puts try.(0, cloth, n)
よくこんなのできたな。いまのところ Ruby で解けたのは 5人だけで、タイムは自分が最速。うれしい。
0092 Square Searching
until (n = $<.gets.to_i).zero? field = Array.new(n) {$<.gets.chomp} max = 0 check = ->(x, y, num) { num.times do |i| num.times do |j| return false if x + j >= n or y + i >= n return false if field[y + i][x + j] == "*" end end true } (0...n * n).each do |i| x, y = i % n, i / n (max + 1..n - x).each do |width| max = width if check.(x, y, width) end end puts max end
これだと時間オーバー。ちょっと素朴すぎるか。
高速化に挑戦。チェックをビット演算に切り替える。
until (n = $<.gets.to_i).zero? field = Array.new(n) {$<.gets.chomp} field.map! {|st| eval("0b" + st.gsub(/\./, "0").gsub(/\*/, "1"))} max = 0 n.times do |y| l = field[y] break unless n - y > max (n - y).times do |i| l |= field[y + i] if l.to_s(2).rjust(n, "0").include?("0" * (i + 1)) max = i + 1 if i + 1 > max end end end puts max end
いちおう通ったけれども、3.91秒もかかってしまった。判定時にわざわざ文字列に直しているのがよくないのだけれど。
判定時に文字列を使わないバージョンも作ってみたのだが、余計に遅くなってしまった。正解者の結果を見ると 3.91秒というのは真ん中くらいで、そんなに悪い数字ではなかったようだ。Ruby だとしようがないのね。
0093 Leap Year
stack = [] until (years = $<.gets.split.map(&:to_i)) == [0, 0] is_uruu = ->(year) { (year % 4).zero? and ((year % 100).nonzero? or (year % 400).zero?) } result = (years.first..years.last).map {|i| is_uruu.(i) ? i : nil}.compact result << "NA" if result.empty? stack << result.join("\n") end print stack.join("\n\n") + "\n"
0094 Calculation of Area
a, b = $<.gets.split.map(&:to_i) printf "%.5f\n", a * b / 3.305785
0095 Surf Smelt Fishing Contest
$<.gets data = $<.readlines.map {|l| l.split.map(&:to_i)}.sort_by(&:last) max = data.last.last num = data.select {|a| a.last == max}.sort_by(&:first).first.first puts "#{num} #{max}"
sort_by
を sort
と書くタイポがあって、なかなか気づけなかった。
0096 Sum of 4 Integers II
L = 1000 @memo = {} def doit(s, n = 1) return (s <= L) ? 1 : 0 if n == 4 key = [s, n] return @memo[key] if @memo.has_key?(key) co = 0 a = (s <= L) ? s : L (0..a).each do |i| co += doit(s - i, n + 1) end @memo[key] = co end $<.readlines.map(&:to_i).each do |s| puts doit(s) end
これだと時間オーバー。メモ化はしているのだけれど、もっと工夫しないといけない。
L = 1000 memo = {} f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6} f2 = ->(n) {(n ** 2 + 3 * n + 2) / 2} f3 = ->(n) {n + 1} f = ->(s, n) { case n when 1 then f1.(s) when 2 then f2.(s) when 3 then f3.(s) when 4 then 1 else nil end } doit = ->(s, n = 1) { co = 0 return f.(s, n) if s <= L return 0 if n == 4 key = [s, n] return memo[key] if memo.has_key?(key) (0..L).each do |i| co += doit.(s - i, n + 1) end memo[key] = co } $<.readlines.map(&:to_i).each do |s| puts doit.(s) end
これも時間オーバーだが、正しい答えを出すようだ。これがひな型になる。
f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6} f2 = ->(n) { n1 = n - 1000 (335337002 + 1004001 * n1 + 998 * n1 ** 2 - n1 ** 3) / 2 } f3 = ->(n) { n1 = n - 2001 (1337336000 - 4002 * n1 - 1999 * n1 ** 2 + n1 ** 3) / 2 } f4 = ->(n) { n1 = n - 3002 (999999000 - 2999999 * n1 + 3000 * n1 ** 2 - n1 ** 3) / 6 } $<.readlines.map(&:to_i).each do |s| result = case s when 0..1000 then f1.(s) when 1001..2001 then f2.(s) when 2002..3002 then f3.(s) when 3003..4000 then f4.(s) end puts result end
ほとんどインチキ。瞬殺である。WolframAlpha に助けを借りたのはナイショ。
他の人の回答。
MAX_SUM = 4000 MAX_I = 1000 K = 4 $sn_cache = Array.new(K + 1) {[]} def check_sum(k, n) unless $sn_cache[k][n] count = 0 max_i = [MAX_I, n].min (0..max_i).each do |i| count += check_sum(k - 1, n - i) end $sn_cache[k][n] = count end $sn_cache[k][n] end $sn_cache[1] = Array.new(MAX_I + 1, 1) + Array.new(MAX_SUM - MAX_I, 0) while (line = gets) n = line.chomp.to_i puts check_sum(K, n) end
これで 0.81秒なのだが、自分の最初の答えとよく似ている。しかし、自分のだと 6.51秒で時間オーバー。どこがちがうのだろう。
わかった、メモ化の際の配列の作り方がちがっているのだ。ハッシュを多重配列に直す。
L = 1000 @memo = Array.new(3) {[]} def doit(s, n = 1) return (s <= L) ? 1 : 0 if n == 4 return @memo[n - 1][s] if @memo[n - 1][s] co = 0 a = (s <= L) ? s : L (0..a).each do |i| co += doit(s - i, n + 1) end @memo[n - 1][s] = co end $<.readlines.map(&:to_i).each do |s| puts doit(s) end
これだけのことで 0.83秒で解けた。うーん、めっちゃ勉強になるなあ。
この最後のコードがいちばん好きだな。
なお、メモ化をハッシュにして、キーを key = "#{s},#{n}"
という感じにしてやってもまあまあいけて、2.25秒で出来た。しかし、数字でいける場合はやはり配列が速いのは当り前か。
0097 Sum of Integers II
L = 100 @memo = Array.new(9) {Array.new(101) {[]}} def solve(num, start, sum) return 0 if sum < 0 or start > L return (start <= sum and sum <= L) ? 1 : 0 if num == 1 a = @memo[num - 1][start][sum] return a if a co = 0 lim = [L, (2 * sum - num ** 2 + num) / (2 * num)].min (start..lim).each do |i| co += solve(num - 1, i + 1, sum - i) end @memo[num - 1][start][sum] = co end until (a = $<.gets.split.map(&:to_i)) == [0, 0] puts solve(a.first, 0, a.last) end
1.11秒かかった。lim を求めるのは少し凝ってみた。lim = [L, sum].min
とやるより少し効率がよい。
0098 Maximum Sum Sequence II
matrix = Array.new(n = $<.gets.to_i) {$<.gets.split.map(&:to_i)} max = -Float::INFINITY memo = {} try = ->(x, y, w, h) { return 0 if x >= n or y >= n or w <= 0 or h <= 0 key = "#{x},#{y},#{w},#{h}" return memo[key] if memo[key] if h == 1 and w == 1 num = matrix[y][x] else try.(x, y + 1, w, h - 1) try.(x, y , w, h - 1) try.(x + 1, y, w - 1, h) try.(x , y, w - 1, h) num = try.(x, y, 1, 1) + try.(x + 1, y, w - 1, 1) + try.(x, y + 1, 1, h - 1) + try.(x + 1, y + 1, w - 1, h - 1) end max = num if num > max memo[key] = num } try.(0, 0, n, n) puts max
メモ化しても時間オーバー。
他の人の回答(参照)を見る。コードは自分の好みに改変してあります。
n = $<.gets.to_i matrix = (1..n).map { $<.gets.split.map(&:to_i) } # 各行の数字を左から加算していった配列 accum = matrix.map {|row| row.inject([0]) {|s, x| s + [s[-1] + x]} } max = 0 [*1..n].repeated_combination(2) do |i, j| sum = 0 (0..n - 1).each do |k| sum += accum[k][j] - accum[k][i - 1] max = sum if sum > max sum = 0 if sum < 0 end end matrix.flatten! puts matrix.any? {|x| x >= 0} ? max : matrix.max
瞬殺。うーん、すごい、これは思いつかなかった。でもあらかじめ数字を加算しておいた配列を作るのいうのは、確かに時々見る手法。
0099 Surf Smelt Fishing Contest II
Node = Struct.new(:key, :value, :left, :right) class Tree def initialize @root = nil end def insert(key, value) unless @root @root = Node.new(key, value) return end node = @root while node if key < node.key if node.left node = node.left else node.left = Node.new(key, value) break end elsif key > node.key if node.right node = node.right else node.right = Node.new(key, value) break end else if block_given? node.value = yield(key, node.value, value) else node.value = value end break end end end def []=(key, value) insert(key, value) end def search(key) node = @root while node if key < node.key node = node.left elsif key > node.key node = node.right else return node end end nil end def [](key) search(key)&.value end def delete(key) delete_min = ->(node) { return node.right unless node.left node.left = delete_min.(node.left) node } search_min = ->(node) { node = node.left while node.left node } del = ->(node) { if node if key == node.key if node.left.nil? return node.right elsif node.right.nil? return node.left else min_node = search_min.(node.right) node.key = min_node.key node.value = min_node.value node.right = delete_min.(node.right) end elsif key < node.key node.left = del.(node.left) else node.right = del.(node.right) end end node } @root = del.(@root) end def maximum search_max = ->(node) { node = node.right while node.right node } raise "error" unless @root node = search_max.(@root) raise "error" unless node node.key end end n, q = $<.gets.split.map(&:to_i) entry = [] fish_num = Hash.new(0) t = Tree.new delete = ->(fish, member) { t[fish] -= [member] t.delete(fish) if t[fish].empty? } q.times do member, fs = $<.gets.split.map(&:to_i) tmp = fish_num[member] fish_num[member] += fs t.insert(fish_num[member], [member]) {|k, v1, v2| v1 + v2} if entry.include?(member) delete.(tmp, member) else entry << member end max_fish = t.maximum puts "#{t[max_fish].sort.first} #{max_fish}" end
惜しい、22課題中21課題までいって時間オーバー(9秒99)。二分探索木を実装して頑張った。しかしこれではダメのようだから、平衡二分探索木を実装しないといけないのか。
いや、シンプルに考え直してみる。
fish = Hash.new(0) max = 0 max_fishers = [] selected_fisher = nil n, q = $<.gets.split.map(&:to_i) q.times do a, v = $<.gets.split.map(&:to_i) fish[a] += v if v > 0 if fish[a] > max max = fish[a] puts "#{a} #{max}" max_fishers = [a] selected_fisher = a elsif fish[a] == max max_fishers << a puts "#{selected_fisher = max_fishers.min} #{max}" else puts "#{selected_fisher} #{max}" end else if fish[a] - v == max if max_fishers.size == 1 max = fish.values.max max_fishers = fish.keys.select {|k| fish[k] == max} puts "#{selected_fisher = max_fishers.min} #{max}" else max_fishers.delete(a) puts "#{selected_fisher = max_fishers.min} #{max}" end else puts "#{selected_fisher} #{max}" end end end
Ruby のバージョンアップ
AOJ(問題集)9
AIZU ONLINE JUDGE: Programming Challenge
0081 A Symmetric Point
require 'matrix' $<.readlines.map {|l| l.split(",").map(&:to_f)}.each do |x1, y1, x2, y2, xq, yq| p1 = Vector[x1, y1] n = Vector[y2 - y1, x1 - x2].normalize q = Vector[xq, yq] d = (p1 - q).dot(n) r = q + (2 * d) * n printf "%.6f %.6f\n", r[0], r[1] end
わりとうまく解けた。
0082 Flying Jenny
table = [4, 1, 4, 1, 2, 1, 2, 1] $<.readlines.map {|l| l.split.map(&:to_i)}.each do |persons| result = (0..7).map do |i| order = table.rotate(i) left = persons.map.with_index do |n, j| a = n - order[j] a < 0 ? 0 : a end.sum [left, order] end.sort_by {|d| d.first} min = result.first.first result = result.select {|d| d.first == min}.sort_by {|d| d.last.join.to_i}.first puts result.last.join(" ") end
0083 Era Name Transformation
require 'date' table = [["pre-meiji", [ 1, 1, 1], [1868, 9, 7]], ["meiji" , [1868, 9, 8], [1912, 7, 29]], ["taisho" , [1912, 7, 30], [1926, 12, 24]], ["showa" , [1926, 12, 25], [1989, 1, 7]], ["heisei" , [1989, 1, 8], [2020, 1, 1]]] table.map! {|n, d1, d2| [n, Date.new(*d1), Date.new(*d2)]} $<.readlines.map {|l| Date.new(*l.split.map(&:to_i))}.each do |day| table.each do |name, d1, d2| if day.between?(d1, d2) if name == "pre-meiji" puts name else puts "#{name} #{day.year - d1.year + 1} #{day.month} #{day.day}" end end end end
0084 Search Engine
text = $<.gets.chomp puts text.split(/[ \.,]/).select {|w| w.length.between?(3, 6)}.join(" ")
0085 Joseph's Potato
until (a = $<.gets.split.map(&:to_i)) == [0, 0] n, m = a circle = [*1..n] try = ->(po) { return circle.first if circle.size == 1 po += m - 1 po -= circle.size while po >= circle.size circle = circle[0...po] + circle[po + 1..-1] try.(po) } puts try.(n) end
0086 Patrol
loop do roots = Hash.new([]) i = 0 loop do exit unless (l = io.gets) break if (l = l.split.map(&:to_i)) == [0, 0] a, b = l roots[a] += [[b, i]] roots[b] += [[a, i]] i += 1 end try = ->(spot, visited) { if spot == 2 return true if visited == 2 ** i - 1 else roots[spot].each do |nxt, root| next if (2 ** root & visited).nonzero? return true if try.(nxt, 2 ** root | visited) end end false } puts try.(1, 0) ? "OK" : "NG" end
これは時間オーバー。バックトラック法しか思いつかない。ちょっと他の人の回答を見たい。
例えばこの回答。
loop do spots = [] loop do line = $<.gets exit if line.nil? p0, p1 = line.chomp.split(" ").map(&:to_i) break if p0.zero? and p1.zero? p0 -= 1 p1 -= 1 spots[p0] = spots[p0] ? (spots[p0] + 1) : 1 spots[p1] = spots[p1] ? (spots[p1] + 1) : 1 end #p spots ok = true if spots[0].even? or spots[1].even? ok = false else (2...spots.length).each do |i| if spots[i].odd? ok = false break end end end puts ok ? "OK" : "NG" end
これは…、瞬殺である。配列 spots はその場所から出ている道の数を表わしている。
なるほど、道が一筆書きになればよいわけだな。そんな簡単なことに気づかなかったとは!
0087 Strange Mathematical Expression
$<.readlines.map {|l| l.chomp.split}.each do |data| stack = [] while (x = data.shift) if %w(+ - * /).include?(x) a, b = stack.pop, stack.pop stack << eval("#{b}.to_f #{x} #{a}") else stack << x end end printf "%.6f\n", stack.first end
0088 The Code A Doctor Loved
table1 = {"'"=>"000000", ","=>"000011", "-"=>"10010001", "."=>"010001", "?"=>"000001", "A"=>"100101", "B"=>"10011010", "C"=>"0101", "D"=>"0001", "E"=>"110", "F"=>"01001", "G"=>"10011011", "H"=>"010000", "I"=>"0111", "J"=>"10011000", "K"=>"0110", "L"=>"00100", "M"=>"10011001", "N"=>"10011110", "O"=>"00101", "P"=>"111", "Q"=>"10011111", "R"=>"1000", "S"=>"00110", "T"=>"00111", "U"=>"10011100", "V"=>"10011101", "W"=>"000010", "X"=>"10010010", "Y"=>"10010011", "Z"=>"10010000", " "=>"101"} table2 = {"00000"=>"A", "00001"=>"B", "00010"=>"C", "00011"=>"D", "00100"=>"E", "00101"=>"F", "00110"=>"G", "00111"=>"H", "01000"=>"I", "01001"=>"J", "01010"=>"K", "01011"=>"L", "01100"=>"M", "01101"=>"N", "01110"=>"O", "01111"=>"P", "10000"=>"Q", "10001"=>"R", "10010"=>"S", "10011"=>"T", "10100"=>"U", "10101"=>"V", "10110"=>"W", "10111"=>"X", "11000"=>"Y", "11001"=>"Z", "11010"=>" ", "11011"=>".", "11100"=>",", "11101"=>"-", "11110"=>"'", "11111"=>"?"} $<.readlines.each do |line| line.chomp! text = "" line.each_char {|c| text += table1[c]} l = text.length % 5 text += "0" * (5 - l) if l > 0 result = "" until text.empty? result += table2[text[0, 5]] text = text[5..-1] end puts result end
0089 The Shortest Path on A Rhombic Path
lines = $<.readlines.map {|l| l.split(",").map(&:to_i)} ln = lines.size / 2 + 1 up = ->(n, sums) { return sums if n == ln nxt = Array.new(n + 1, 0) sums.each_index do |i| nxt[i] = sums[i] + lines[n][i] if i.zero? nxt[i + 1] = sums[i, 2].max + lines[n][i + 1] end up.(n + 1, nxt) } mid = up.(1, lines.first) down = ->(n, sums) { return sums.first if sums.size == 1 nxt = sums.each_cons(2).map.with_index do |pair, i| lines[n][i] + pair.max end down.(n + 1, nxt) } puts down.(ln, mid)
こんな面倒なやり方しか思いつかなかった。むずかしかったので一発でいってよかった。ダメだったら考え直す気力がない…。
0090 Overlaps of Seals
全然思いつかない…。他人の回答を見る(自己流に改変しています)。
require 'matrix' DELTA = 1e-6 until (n = $<.gets.to_i).zero? points = [] n.times do points << Vector[*$<.gets.chomp.split(",").map(&:to_f)] end cps = [] points.each_with_index do |p0, i| (i + 1...n).each do |j| p1 = points[j] v = p1 - p0 d = v.norm if d <= 1.0 + DELTA hd = d / 2 ul = Math.sqrt(1.0 - hd * hd) u = Vector[-v[1], v[0]] / d * ul c = (p0 + p1) / 2 cps << c + u cps << c - u end end end max_ov = 1 cps.each do |cp| ov = 0 points.each do |point| ov += 1 if (point - cp).norm <= 1.0 + DELTA end max_ov = ov if max_ov < ov end puts max_ov end
AOJ(問題集)8
AIZU ONLINE JUDGE: Programming Challenge
0071 Bombs Chain
$<.gets.to_i.times do |co| $<.gets field = Array.new(8) {$<.gets.chomp.chars.map(&:to_i)} xi, yi = $<.gets.to_i, $<.gets.to_i blast = ->(x, y) { field[y][x] = 2 3.times do |i| [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| x1, y1 = x + dx * (i + 1), y + dy * (i + 1) next if x1 < 0 or x1 >= 8 or y1 < 0 or y1 >= 8 if field[y1][x1] == 1 blast.(x1, y1) else field[y1][x1] = 2 end end end } blast.(xi - 1, yi - 1) puts "Data #{co + 1}:" puts field.map {|line| line.map {|a| a == 2 ? 0 : a}.join} end
0072 Carden Lantern
until (n = $<.gets.to_i).zero? m = $<.gets.to_i table = Array.new(m) {$<.gets.split(",").map(&:to_i)} table.map! {|a, b, d| [a, b, d / 100 - 1]} min = Float::INFINITY (1..m).each do |i| table.combination(i) do |paths| next unless paths.inject([]) {|a, path| a + path[0, 2]}.uniq.sort == [*0...n] n = paths.map{|path| path.last}.sum min = n if n < min end end puts min end
まずはこれで解ける筈だが、時間オーバー。そりゃそうだ。
ふと、動的計画法で解けることに気がつく。これはよいアイデア。
until (n = $<.gets.to_i).zero? m = $<.gets.to_i field = [] Array.new(m) {$<.gets.split(",").map(&:to_i)}.each do |a, b, d| n = d / 100 - 1 field += field.map {|spots, num| [(spots + [a, b]).uniq, num + n]} field << [[a, b], n] end puts field.select {|x| x.first.size == n}.sort_by {|x| x.last}.first.last end
しかしメモリオーバー。ならばと訪れた史跡のチェックをビット演算でおこない、さらに配列の代わりにハッシュを使って省メモリ化。
until (n = $<.gets.to_i).zero? m = $<.gets.to_i field = {0=>0} Array.new(m) {$<.gets.split(",").map(&:to_i)}.each do |a, b, d| n = d / 100 - 1 added = {} field.each do |spots, num| spots |= 2 ** a spots |= 2 ** b added[spots] = num + n if !added[spots] or num + n < added[spots] end field.merge!(added) {|spots, b, f| [b, f].min} end puts field[2 ** n - 1] end
それでもメモリオーバー。うーん。いきづまった。
まったく別の考え方で。後戻りも含めて幅優先探索し、適当なところで打ち切る。
until (n = $<.gets.to_i).zero? m = $<.gets.to_i cpd = Hash.new([]) table = Array.new(m) {$<.gets.split(",").map(&:to_i)} table.map! {|a, b, d| [a, b, d / 100 - 1]} table.each_with_index do |x, i| cpd[x[0]] += [i] cpd[x[1]] += [i] end stack = [[0, 1, 0, 0]] # 現在位置、行った場所、灯籠の数、使った道 result = loop do nxt = stack.shift cpd[nxt[0]] .map {|tn| [tn, (table[tn][0, 2] - [nxt[0]]).first, table[tn].last]} .each do |tn, spot, n| nxt_lnt = nxt[2] nxt_lnt += n if (2 ** spot & nxt[1]).zero? stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** tn | nxt[3]] end tmp1 = stack.select {|x| x[1] == 2 ** n - 1} tmp2 = tmp1 .select {|x| x[3] == 2 ** m - 1} break tmp1 unless tmp2.empty? end puts result.map {|x| x[2]}.min end
今度は時間オーバー。うーむ。
後戻りは一度しかできないとする。
until (n = $<.gets.to_i).zero? m = $<.gets.to_i cpd = Hash.new([]) table = Array.new(m) {$<.gets.split(",").map(&:to_i)} table.map! {|a, b, d| [a, b, d / 100 - 1]} table.each_with_index do |x, i| cpd[x[0]] += [i] cpd[x[1]] += [i] end result = [] stack = [[0, 1, 0, 0, 0]] # 現在位置、行った場所、灯籠の数、使った道、道は戻ったことがあるか while (nxt = stack.shift) if nxt[1] == 2 ** n - 1 result << nxt[2] else cpd[nxt[0]] .map {|path| [path, (table[path][0, 2] - [nxt[0]]).first, table[path].last]} .each do |path, spot, n| next if (nxt[4] & 2 ** path).nonzero? # 道を戻るのは一度だけ # 行った場所で使っていない道だとダメ next if (2 ** spot & nxt[1]).nonzero? and (2 ** path & nxt[3]).zero? nxt_lnt = nxt[2] nxt_lnt += n if (2 ** spot & nxt[1]).zero? f = nxt[4] f |= 2 ** path if (2 ** path & nxt[3]).nonzero? stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** path | nxt[3], f] end end end puts result.min end
今度も時間オーバー。うーん、ここまで考えたのだが。
またまったく別の方法。すべて足しておいて、削れるだけ削る。
until (n = $<.gets.to_i).zero? m = $<.gets.to_i init_spots = Array.new(m, 0) tourou = 0 table = Array.new(m) {$<.gets.split(",").map(&:to_i)}.map do |a, b, d| init_spots[a] += 1 init_spots[b] += 1 n = d / 100 - 1 tourou += n [a, b, n] end min = tourou solve = ->(i, spots, t) { min = t if t < min return if i == m solve.(i + 1, spots, t) now = table[i] return if spots[now[0]] == 1 or spots[now[1]] == 1 spots[now[0]] -= 1 spots[now[1]] -= 1 solve.(i + 1, spots, t - now[2]) spots[now[0]] += 1 spots[now[1]] += 1 } solve.(0, init_spots, tourou) puts min end
これも時間オーバー。
他の人の回答(参照)。
until (n = $<.gets.chomp.to_i).zero? edges = [] $<.gets.chomp.to_i.times do e = $<.gets.chomp.split(",").map(&:to_i) e[2] = e[2] / 100 - 1 edges << e end #p [n, m, edges] #灯籠の数の少ない順に並べる edges.sort! {|a, b| a[2] <=> b[2]} nodes = Array.new(n, false) connected = [0] nodes[0] = true sumw = 0 while connected.length < n (0...edges.length).each |i| n0, n1, w = edges[i] if nodes[n0] or nodes[n1] if !nodes[n0] nodes[n0] = true connected << n0 sumw += w elsif !nodes[n1] nodes[n1] = true connected << n1 sumw += w end edges.delete_at(i) break end end end puts sumw end
なるほど、灯籠の少ない順にならべておいて、あとは史跡 0 から順に繋げていくと。なるほどなあー。
0073 Surface Area of Quadrangular Pyramid
loop do x, h = $<.gets.to_i, $<.gets.to_i break if x.zero? and h.zero? puts x * x + Math.sqrt(h * h + (x / 2.0) ** 2) * x * 2 end
0074 Videotape
loop do t, h, s = $<.gets.split.map(&:to_i) break if t == -1 and h == -1 and s == -1 left = 120 * 60 - (t * 3600 + h * 60 + s) output = ->(t) { printf "%02d:%02d:%02d\n", h = t / 3600, (m = t / 60) - h * 60, t - m * 60 } output.(left) output.(left * 3) end
0075 BMI
$<.readlines.map {|l| l.split(",").map(&:to_f)} .select {|s, w, h| w / h ** 2 >= 25.0}.each {|a| puts a.first.to_i}
0076 Treasure Hunt II
until (n = $<.gets.to_i) == -1 x, y = 1.0, 0.0 (n - 1).times do l = Math.sqrt(x ** 2 + y ** 2) x, y = x - y / l, y + x / l end puts x, y end
0077 Run Length
$<.readlines.map(&:chomp).each do |given| po = 0 text = "" while po < given.length if given[po] == "@" text += given[po + 2] * given[po + 1].to_i po += 3 else text += given[po] po += 1 end end puts text end
0078 Magic Square
until (n = $<.gets.to_i).zero? square = Array.new(n) {[0] * n} set = ->(i, x, y) { return if i > n * n if x < 0 set.(i, n - 1, y) elsif x >= n set.(i, 0, y) elsif y >= n set.(i, x, 0) elsif square[y][x].nonzero? set.(i, x - 1, y + 1) else square[y][x] = i set.(i + 1, x + 1, y + 1) end } set.(1, n / 2, n / 2 + 1) square.each do |l| puts l.map {|x| sprintf("%4d", x)}.join end end
0079 Area of Polygon
多角形の面積。
include Math points = $<.readlines.map {|l| Complex(*l.split(",").map(&:to_f))} start_po = p0 = points.sort_by(&:imaginary).last prev_arg = PI e = Enumerator.new do |y| loop do points -= [start_po] break if points.empty? selected = points.map {|po| [po - start_po, po]} .reject {|pos| pos.first == 0} .sort_by {|pos| a = pos.first.angle + PI - prev_arg; a >= 0 ? a : a + 2 * PI} .first.last y << selected prev_arg = (selected - start_po).angle + PI start_po = selected end end result = e.each_cons(2).map do |p1, p2| a = (p1 - p0).abs b = (p2 - p0).abs c = (p2 - p1).abs z = (a + b + c) / 2.0 sqrt(z * (z - a) * (z - b) * (z - c)) end.sum puts result
意外とむずかしくて、かなり大袈裟なことをしている。0068 の回答参照。
他の人の回答にはすごいのがあって、例えばどうしてこれで求まるのかわからない。
ああ、そうか、問題をよく読んでいなかったのか! よくあるな、これ。点が順番に並んでいるのだ。じゃあ簡単だ…。
これでOK。
require 'matrix' p0, *points = $<.readlines.map {|l| Vector[*l.split(",").map(&:to_f)]} result = points.each_cons(2).map do |p1, p2| a = (p1 - p0).norm b = (p2 - p0).norm c = (p2 - p1).norm z = (a + b + c) / 2 Math.sqrt(z * (z - a) * (z - b) * (z - c)) end.sum puts result
前の回答だと、点の並びが任意でも計算できる。
0080 Third Root
until (q = $<.gets.to_f) == -1 x = q / 2.0 result = loop do x -= (x ** 3 - q) / (3 * x ** 2) break x if (x ** 3 - q).abs < 0.00001 * q end puts result end
古い Linux Kernel のインストール
askubuntu.comここが参考になる。
例えばここ、ここ、ここから
を拾ってきてひとつのフォルダに入れ、
$ sudo dpkg -i *.deb
を実行するということらしい。
あとは Grub の変更が必要。自分は Grub Customizer でやる。
※追記
こんなことをするくらいなら Synaptic で入れた方がよい。
※再追記(2019/8/11)
https://kernel.ubuntu.com/~kernel-ppa/mainline/
ここからv4.4.189を拾ってくる。
- linux-headers-4.4.189-0404189_4.4.189-0404189.201908111150_all.deb
- linux-headers-4.4.189-0404189-generic_4.4.189-0404189.201908111150_amd64.deb
- linux-image-unsigned-4.4.189-0404189-generic_4.4.189-0404189.201908111150_amd64.deb
- linux-modules-4.4.189-0404189-generic_4.4.189-0404189.201908111150_amd64.deb
をひとつのフォルダに入れて
$ sudo dpkg -i *.deb $ sudo update-grub
あとは Grub Customizer でやった。
$ sudo uname -a Linux tomoki-ThinkPad-T410 4.4.189-0404189-generic #201908111150 SMP Sun Aug 11 11:53:09 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
OK!
AOJ(問題集)7
AIZU ONLINE JUDGE: Programming Challenge
0061 Rank Checker
data = [] until (st = $<.gets.chomp) == "0,0" data << st.split(",").map(&:to_i) end data.sort! {|a, b| b[1] <=> a[1]} x = data.first.last h = {} l = 1 data.each do |d| l += 1 unless x == d.last x = d.last h[d.first] = l end puts $<.readlines.map(&:to_i).map {|i| h[i]}
実装が汚い…。
0062 What is the Bottommost?
def doit(ary) return ary.first if ary.size == 1 doit( ary.each_cons(2).map {|i, j| (i + j) % 10} ) end $<.readlines.map {|a| a.chomp.chars.map(&:to_i)}.each do |given| puts doit(given) end
0063 Palindrome
co = 0 $<.readlines.map(&:chomp).each do |st| co += 1 if st == st.reverse end puts co
0064 Secret Number
n = 0 $<.readlines.map(&:chomp).each do |st| n += st.scan(/\d+/).map(&:to_i).sum end puts n
0065 Trading
x, y = $<.readlines.map(&:chomp).chunk {|st| st.empty?}.reject {|a| a.first} .map(&:last).map{|a| a.map {|b| b.split(",").first.to_i}}.to_a h = Hash.new(0) (x + y).each {|i| h[i] += 1} (x - (x - y)).uniq.sort.each {|i| puts "#{i} #{h[i]}"}
0066 Tic Tac Toe
table = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]] check = ->(field, type) { table.each {|pat| return true if pat.map {|i| field[i] == type}.all?} false } $<.readlines.map(&:chomp).map(&:chars).each do |field| result = if check.(field, "o") "o" elsif check.(field, "x") "x" else "d" end puts result end
最初与えられた盤面でゲームが完結していないのかと思った…。
0067 The Number of Island
L = 12 def delete(field, x, y) field[y][x] = "0" [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| x1 = x + dx y1 = y + dy if !(x1 < 0 or x1 >= L or y1 < 0 or y1 >= L) and field[y1][x1] == "1" delete(field, x1, y1) end end end $<.readlines.map(&:chomp).chunk {|st| st.empty?} .reject {|a| a.first}.map {|a| a.last}.each do |field| co = 0 L.times do |y| L.times do |x| if field[y][x] == "1" co += 1 delete(field, x, y) end end end puts co end
0068 Enclose Pins with a Rubber Band
include Math until (n = $<.gets.to_i).zero? points = Array.new(n) { Complex(*$<.gets.split(",").map(&:to_f)) } ym = points.map(&:imaginary).max start_po = po0 = points.find {|po| po.imaginary == ym} prev_arg = PI result = loop do points = (points - [start_po] + [po0]).uniq selected = points.map {|po| [po - start_po, po]} .reject {|pos| pos.first == 0} .sort_by {|pos| a = pos.first.angle + PI - prev_arg; a >= 0 ? a : a + 2 * PI} .first.last points.select! {|po| po != start_po} break points.size - 1 if selected == po0 # po0の分だけ1引く prev_arg = (selected - start_po).angle + PI start_po = selected end puts result end
ムズカしかったので一発でいってうれしいが、しかし複雑すぎる。もっといい解法がないかな。
Ruby で解けている人は多くない。
問題はこれ。考え方としては
1. 点を複素数としてオブジェクト化する。
2. 確実に外にある点(po0
)をひとつ選ぶ。
3. 残りの点のすべてへの方向を計算し、いちばん少ない角度で左回りになる点を選ぶ。
4. 選んだ点で同様に (3) を繰り返し、一周したところでおしまい。
5. 残った点の数が求めるもの。
つまり、反時計回りで一周して、周にない点の数を求めるということ。
0069 Drawing Lots II
あみだくじ。与えられたあみだくじで特定の場所を選んで当たりに到達するか調べる。もしそれでダメなら、一本だけ横線を加えてもよい。という問題(参照)。
def hit(n, m, goal, d, dans) h = 0 until h == d yoko = dans[h] if m != n - 1 and yoko[m] == 1 m += 1 elsif m.nonzero? and yoko[m - 1] == 1 m -= 1 end h += 1 end goal == m end until (n = $<.gets.to_i).zero? m = $<.gets.to_i - 1 goal = $<.gets.to_i - 1 d = $<.gets.to_i dans = Array.new(d) { $<.gets.chomp.chars.map(&:to_i) } if hit(n, m, goal, d, dans) puts 0 else try = ->{ d.times do |h| ([0] + dans[h] + [0]).each_cons(3).with_index do |a, x| if a.sum.zero? dans[h][x] = 1 return "#{h + 1} #{x + 1}" if hit(n, m, goal, d, dans) dans[h][x] = 0 end end end 1 } puts try.() end end
これも一発でいった。しかし、段々ムズカしくなってきた…。ふう。
これも Ruby で解いた人は少ない。
0070 Tag Discussion Solution Statistics Submit
def solve(ary, n, s) co = 0 ary.each do |i| s1 = s - i * n if n == 1 if s1.zero? co += 1 end elsif s1 > 0 co += solve(ary - [i], n - 1, s1) end end co end $<.readlines.map {|a| a.split.map(&:to_i)}.each do |n, s| puts solve([*0..9], n, s) end
たぶんこれでいけるのだけれど、時間制限に引っかかる。問題はこれ。よく考えないとな。
デバッグ用。
io.readlines.map {|a| a.split.map(&:to_i)}.each do |n, s| solve = ->(ary, n, s1, st = "") { co = 0 ary.each do |i| s2 = s1 - i * n st1 = st + "#{i}*#{n} + " if n == 1 if s2.zero? co += 1 puts st1[0..-4] + " = #{s}" end elsif s2 > 0 co += solve.(ary - [i], n - 1, s2, st1) end end co } puts solve.([*0..9], n, s) end
これはたとえば n = 5, s = 24 でこうなる。
0*5 + 1*4 + 2*3 + 3*2 + 8*1 = 24 0*5 + 1*4 + 2*3 + 4*2 + 6*1 = 24 0*5 + 1*4 + 2*3 + 5*2 + 4*1 = 24 0*5 + 1*4 + 3*3 + 2*2 + 7*1 = 24 0*5 + 1*4 + 4*3 + 3*2 + 2*1 = 24 0*5 + 2*4 + 1*3 + 3*2 + 7*1 = 24 0*5 + 2*4 + 1*3 + 4*2 + 5*1 = 24 0*5 + 2*4 + 1*3 + 5*2 + 3*1 = 24 0*5 + 2*4 + 3*3 + 1*2 + 5*1 = 24 0*5 + 3*4 + 1*3 + 2*2 + 5*1 = 24 0*5 + 3*4 + 2*3 + 1*2 + 4*1 = 24 1*5 + 0*4 + 2*3 + 3*2 + 7*1 = 24 1*5 + 0*4 + 2*3 + 4*2 + 5*1 = 24 1*5 + 0*4 + 2*3 + 5*2 + 3*1 = 24 1*5 + 0*4 + 3*3 + 2*2 + 6*1 = 24 1*5 + 0*4 + 3*3 + 4*2 + 2*1 = 24 1*5 + 0*4 + 4*3 + 2*2 + 3*1 = 24 1*5 + 2*4 + 0*3 + 3*2 + 5*1 = 24 1*5 + 2*4 + 0*3 + 4*2 + 3*1 = 24 2*5 + 0*4 + 1*3 + 3*2 + 5*1 = 24 2*5 + 0*4 + 1*3 + 4*2 + 3*1 = 24 2*5 + 1*4 + 0*3 + 3*2 + 4*1 = 24 22
フーム。
関係性を調べてみる。
table = [] s = 0 while s < 25 st = "" table << (1..10).map {|n| "%3d" % solve([*0..9], n, s)}.join(" ") s += 1 end table.reverse_each {|l| puts l}
結果。
0 1 16 43 22 0 0 0 0 0 0 3 27 51 13 0 0 0 0 0 0 3 21 35 7 0 0 0 0 0 0 3 18 36 5 0 0 0 0 0 0 4 20 26 1 0 0 0 0 0 0 5 23 29 0 0 0 0 0 0 0 3 13 19 0 0 0 0 0 0 0 5 20 23 0 0 0 0 0 0 0 4 14 15 0 0 0 0 0 0 0 4 13 14 0 0 0 0 0 0 0 4 12 11 0 0 0 0 0 0 0 5 14 9 0 0 0 0 0 0 0 3 7 4 0 0 0 0 0 0 0 5 11 4 0 0 0 0 0 0 0 4 8 1 0 0 0 0 0 0 1 4 5 0 0 0 0 0 0 0 1 4 4 0 0 0 0 0 0 0 1 4 5 0 0 0 0 0 0 0 1 2 2 0 0 0 0 0 0 0 1 3 3 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
うーん。
かなり考えたのだが、これでも時間オーバー。メモ化。
@memo = {} def solve(ary, n, s) hash = ary.map {|i| [11, 13, 17, 19, 23, 29, 31, 37, 41, 43][i]}.inject(&:*) hash *= n return @memo[[hash, s]] if @memo[[hash, s]] co = 0 ary.each do |i| s1 = s - i * n if n == 1 if s1.zero? co += 1 end elsif s1 > 0 co += solve(ary - [i], n - 1, s1) end end @memo[[hash, s]] = co end $<.readlines.map {|a| a.split.map(&:to_i)}.each do |n, s| puts solve([*0..9], n, s) end
このアプローチでは無理かな。
他の人の回答(参照)。
$sumhash = {} def check_sum(n, s, used = 0) key = "#{n},#{s},#{used}" return $sumhash[key] if ! $sumhash[key].nil? if n == 0 return s == 0 ? 1 : 0 end count = 0 10.times do |i| b = 1 << i ni = n * i if (used & b).zero? and s >= ni used |= b count += check_sum(n - 1, s - ni, used) used ^= b end end return $sumhash[key] = count end while (line = $<.gets) n, s = line.chomp.split(" ").map{|s| s.to_i} puts check_sum(n, s) end
なんと、じつに素直なアプローチ。で、あとはメモ化かあ。全然自分の知っている方法だけで解けるではないか。うーん、まだまだだなあ…。
ただ、ビット演算で or で立てたフラグを消すのが xor というのは気づかなかった。これは勉強になった。
AOJ(問題集)6
AIZU ONLINE JUDGE: Programming Challenge
0051 Differential II
$<.readlines.drop(1).map {|a| a.chomp.chars.map(&:to_i).sort}.each do |ary| puts ary.reverse.join.to_i - ary.join.to_i end
0052 Factorial II
until (n = $<.gets.to_i).zero? five = n / 5 f = ->(x) { return five if n < x five += n / x f.(x * 5) } puts f.(25) end
これはちょっと考えました。
0053 Sum of Prime Numbers
require 'prime' nums = [] h = {} until (i = $<.gets.to_i).zero? nums << i h[i] = 0 end max_num = nums.max sum = 0 Prime.each.with_index do |prime, i| break if i + 1 > max_num sum += prime h[i + 1] = sum if h[i + 1] end nums.each {|j| puts h[j]}
与えられた値が重複しているのだな。結構いい成績だった。
0054 Sum of Nth decimal places
$<.readlines.map {|a| a.split.map(&:to_i)}.each do |a, b, n| f = ->(x, i = 1, sum = 0) { return sum if i > n or x.zero? f.(x * 10 % b, i + 1, sum + x * 10 / b) } puts f.(a % b) end
0055 Sequence
$<.readlines.map(&:to_f).each do |x| sum = 0 solve = ->(n, i = 1) { sum += n return sum if i == 10 (i + 1).even? ? solve.(n * 2.0, i + 1) : solve.(n / 3.0, i + 1) } puts solve.(x) end
0056 Goldbach's Conjecture
require 'prime' h = {} primes = Prime.each(50000).to_a primes.each {|pr| h[pr] = true} until (n = $<.gets.to_i).zero? co = 0 if n.odd? co = 1 if h[n - 2] else primes.each do |pr| break if pr > n / 2 co += 1 if h[n - pr] end end puts co end
何か変なミスをしていた。何とタイムは挑戦者中最速。
0057 The Number of Area
$<.readlines.map(&:to_i).each do |n| puts 2 + (n - 1) * (n + 2) / 2 end
0058 Orthogonal
$<.readlines.map {|l| l.split.map(&:to_r)}.each do |xa, ya, xb, yb, xc, yc, xd, yd| x1, y1 = xb - xa, yb - ya x2, y2 = xd - xc, yd - yc puts x1 * x2 + y1 * y2 == 0 ? "YES" : "NO" end
0059 Intersection of Rectangles
while (st = $<.gets) xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2 = st.split.map(&:to_f) if !(xa1 > xb2 or xa2 < xb1 or ya1 > yb2 or ya2 < yb1) puts "YES" else puts "NO" end end
こんなに簡単なものが条件を見落としていた…。
0060 Card Game
$<.readlines.map {|a| a.split.map(&:to_i)}.each do |my1, my2, opp1| deck = [*1..10] - [my1, my2, opp1] limit = 20 - (my1 + my2) p = 0 deck.each do |opp2| n = (deck - [opp2]).take_while {|i| i <= limit}.size p += 1/7r * Rational(n, 6) end puts p >= 1/2r ? "YES" : "NO" end
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