AOJ（問題集）18
AIZU ONLINE JUDGE: Programming Challenge
0170 Lunch
until (n = $<.gets.to_i).zero? data = n.times.map {$<.gets.split}.map {|a, *b| [a] + b.map(&:to_i)} selected = [] all = [*0...n] solve = ->(left, order) { return if data[order.last][2] < (all - order).map {|i| data[i][1]}.sum if left.empty? selected << order else left.each {|i| solve.(left - [i], order + [i])} end } all.each {|i| solve.(all - [i], [i])} result = selected.sort_by do |order| w = order.map {|i| data[i][1]} [*1..order.size].zip(w).map {|a, b| a * b}.sum / w.sum.to_f end.first puts result.map {|i| data[i][0]} end
3.74秒。バックトラック法。もっといい方法があるらしい。検索してみても C++ とかの奴らは全然参考にならない。
また tnakao さんの回答を見る。驚愕。とりあえず（自己流に書き直して）コードを掲載してみる。
until (n = io.gets.to_i).zero? data = n.times.map {io.gets.split}.map {|a, *b| [a] + b.map(&:to_i)} wsum0 = data.map {|a| a[1]}.sum memo = [] check = ->(bits, wsum) { return memo[bits] if memo[bits] return [0, []] if bits.zero? min_gw = Float::INFINITY min_ids = [] n.times do |i| b = 1 << i if (bits & b).nonzero? name, w, s = data[i] if s >= wsum - w gw0, ids0 = check.(bits & ~b, wsum - w) gw = gw0 + wsum if gw < min_gw min_gw = gw min_ids = [i] + ids0 end end end end memo[bits] = [min_gw, min_ids] } gw, ids = check.((1 << n) - 1, wsum0) puts ids.map {|i| data[i][0]} end
なるほど、最後からやっていくわけか…。(n - 1) 個の場合の min を求めておいて、n 個の min を出す。動的計画法だな。これは思いつかなかった。すごい。
0171 Dice Puzzle
table = [[1, 2, 3, 4, 5, 6], [4, 2, 1, 6, 5, 3], [2, 6, 3, 4, 1, 5], [5, 1, 3, 4, 6, 2], [3, 2, 6, 1, 5, 4], [1, 3, 5, 2, 4, 6], [1, 4, 2, 5, 3, 6], [6, 2, 4, 3, 5, 1], [2, 3, 1, 6, 4, 5], [5, 4, 1, 6, 3, 2], [4, 1, 5, 2, 6, 3], [4, 6, 2, 5, 1, 3], [6, 5, 3, 4, 2, 1], [3, 6, 5, 2, 1, 4], [2, 4, 6, 1, 3, 5], [3, 1, 2, 5, 6, 4], [5, 3, 6, 1, 4, 2], [1, 5, 4, 3, 2, 6], [2, 1, 4, 3, 6, 5], [5, 6, 4, 3, 1, 2], [6, 4, 5, 2, 3, 1], [6, 3, 2, 5, 4, 1], [3, 5, 1, 6, 2, 4], [4, 5, 6, 1, 2, 3]] Table = table.map {|i| i.map(&:pred)} Dirs = [[2, 4, 5], [1, 2, 5], [3, 4, 5], [1, 3, 5], [2, 4, 0], [1, 2, 0], [3, 4, 0], [1, 3, 0]] Touch = [[2, 1, 4], [0, 3, 5], [0, 3, 6], [2, 1, 7], [6, 5, 0], [4, 7, 1], [4, 7, 2], [6, 5, 3]] def each_position(dice, d_num) Dirs[d_num].each do |fix_po| Table.select {|od| od[fix_po] == fix_po}.each do |order| yield order.map {|i| dice[i]} end end end until (s = $<.gets.chomp) == "0" dices = [s.chars] 7.times {dices << $<.gets.chomp.chars} ok = false try = ->(cube, memo, d_num) { if d_num == 8 ok = true else ([*0..7] - cube).each do |nxt| each_position(dices[nxt], d_num) do |d1| f = Dirs[d_num].map.with_index do |dir, i| d2 = memo[Touch[d_num][i]] next unless d2 d1[dir] == d2[5 - dir].swapcase end.compact.all? try.(cube + [nxt], memo + [d1], d_num + 1) if f end end end } Table.each {|order| try.([0], [order.map {|j| dices[0][j]}], 1)} puts ok ? "YES" : "NO" end
42秒で時間オーバー。
0173 Haunted House
9.times do name, a, b = $<.gets.split a, b = a.to_i, b.to_i puts "#{name} #{a + b} #{200 * a + 300 * b}" end
0174 Badminton
until (rec = $<.gets.chomp) == "0" record = rec.chars.drop(1) a = b = 0 loop do (record.shift == "A") ? a += 1 : b += 1 if record.empty? (a > b) ? a += 1 : b += 1 break end end puts "#{a} #{b}" end
0176 What Color?
table = %w(black blue lime aqua red fuchsia yellow white) until (rgb = $<.gets.chomp) == "0" color = rgb[1..-1].chars.each_slice(2).map {|a| a.join.to_i(16)} idx = [0, 0xff].repeated_permutation(3).map.with_index do |tc, i| [3.times.map {|i| (tc[i] - color[i]) ** 2}.sum, i] end.sort.first.last puts table[idx] end
ちょっと Ruby らしく圧縮しすぎて却ってわかりにくいかも。
0177 Distance Between Two Cities
require 'matrix' include Math R = 6378.1 until (given = $<.gets.split.map(&:to_f)) == [-1] * 4 a, b, c, d = given.map {|i| i / 180 * PI} rot = ->(θ, n) { vx = [cos(θ) + n[0] * n[0] * (1 - cos(θ)), n[0] * n[1] * (1 - cos(θ)) - n[2] * sin(θ), n[2] * n[0] * (1 - cos(θ)) + n[1] * sin(θ)] vy = [n[0] * n[1] * (1 - cos(θ)) + n[2] * sin(θ), cos(θ) + n[1] * n[1] * (1 - cos(θ)), n[1] * n[2] * (1 - cos(θ)) - n[0] * sin(θ)] vz = [n[2] * n[0] * (1 - cos(θ)) - n[1] * sin(θ), n[1] * n[2] * (1 - cos(θ)) + n[0] * sin(θ), cos(θ) + n[2] * n[2] * (1 - cos(θ))] Matrix[vx, vy, vz] } calc = ->(θ, φ) { po = Vector[1, 0, 0] po = rot.(θ, [0, 0, 1]) * po n = po.cross(Vector[0, 0, 1]) rot.(φ, n) * po } x1 = calc.(b, a) x2 = calc.(d, c) c = (x1 + x2) / 2 θ = atan2((x1 - c).norm, c.norm) * 2 puts (R * θ).round end
Ruby 便利だ…。
0178 TETORIS
テトリス。
W = 5 until (n = $<.gets.to_i).zero? field = [] n.times do d, p, q = $<.gets.split.map(&:to_i) if d == 1 block = ((1 << p) - 1) << W + 1 - p - q if field.empty? field = [block] else i = field.size - 1 while (field[i] & block).zero? i -= 1 break if i < 0 end i += 1 field[i] ||= 0 field[i] |= block end else block = 1 << W - q if field.empty? p.times {field.push(block)} else i = field.size - 1 while (field[i] & block).zero? i -= 1 break if i < 0 end p.times do i += 1 field[i] ||= 0 field[i] |= block end end end field.delete_at(i) while (i = field.index(31)) end puts field.map {|a| a.to_s(2)}.join.count("1") end
圧倒的に速いですぞ、これは。
0179 Mysterious Worm
color = %w(r g b) until (worm = io.gets.chomp) == "0" queue = [[worm, 0]] appear = [worm] catch :jump do while (worm = queue.shift) worm, t = worm.first.chars, worm.last if color.map {|c| worm.all? {|a| a == c}}.any? puts t throw :jump else (worm.size - 1).times do |i| tmp = worm.dup next if tmp[i] == tmp[i + 1] c = (color - [tmp[i], tmp[i + 1]]).first tmp[i] = c tmp[i + 1] = c tmp = tmp.join next if appear.include?(tmp) appear << tmp queue << [tmp, t + 1] end end end puts "NA" end end
幅優先探索なのだけれど、42秒で時間オーバー。
他の人の回答を見る。
table = {"rg"=>"bb", "gr"=>"bb", "gb"=>"rr", "bg"=>"rr", "br"=>"gg", "rb"=>"gg"}
neighbours = ->(worm) {
len = worm.length
result = []
c0 = worm[0]
(1...len).each do |i|
c = worm[i]
pair = c0 + c
if table[pair]
worm0 = worm.dup
worm0[i - 1, 2] = table[pair]
result << worm0
end
c0 = c
end
result
}
until (worm = $<.gets.strip) == "0"
queue = [worm]
dists = {worm => 0}
dist = "NA"
n = worm.length
goal = ["r" * n, "g" * n, "b" * n]
while (worm = queue.shift)
if goal.include?(worm)
dist = dists[worm]
break
end
neighbours.(worm).each do |worm0|
unless dists[worm0]
dists[worm0] = dists[worm] + 1
queue << worm0
end
end
end
puts dist
end
これだと 0.85秒でクリア。考え方は自分のとそんなにちがわない。何がちがうのかな。シンプルさがちがうのだな。
これを参考に、自分のを書き直してみる。
table = {"rg"=>"bb", "gr"=>"bb", "gb"=>"rr", "bg"=>"rr", "br"=>"gg", "rb"=>"gg"}
until (worm = $<.gets.chomp) == "0"
queue = [worm]
dist = {worm => 0}
n = worm.size
catch :jump do
while (worm = queue.shift)
goal = ["r" * n, "g" * n, "b" * n]
if goal.include?(worm)
puts dist[worm]
throw :jump
else
(n - 1).times do |i|
tmp = worm.dup
pair = worm[i, 2]
next unless table[pair]
tmp[i, 2] = table[pair]
next if dist[tmp]
dist[tmp] = dist[worm] + 1
queue << tmp
end
end
end
puts "NA"
end
end
これだと 0.77秒でクリア。うーん、勉強になるなあ。
AOJ（問題集）17
AIZU ONLINE JUDGE: Programming Challenge
0160 Delivery Fee
table = [[60, 2, 600], [80, 5, 800], [100, 10, 1000], [120, 15, 1200], [140, 20, 1400], [160, 25, 1600]] until (n = $<.gets.to_i).zero? result = n.times.map {$<.gets.split.map(&:to_i)}.map do |x, y, h, w| idx = table.index {|d| x + y + h <= d[0] and w <= d[1]} idx ? table[idx].last : 0 end.sum puts result end
0161 Sport Meet
until (n = $<.gets.to_i).zero? result = n.times.map {$<.gets.split.map(&:to_i)}.map do |id, *d| [id, d.each_slice(2).map {|m, s| 60 * m + s}.sum] end.sort {|a, b| a[1] <=> b[1]}.map(&:first) puts result[0], result[1], result[-2] end
0162 Hamming Numbers
L = 1000000 table = [] (0..19).each do |a| table << (x1 = 2 ** a) (1..12).each do |b| table << (x2 = 3 ** b) y1 = x1 * x2 table << y1 if y1 <= L (1..8).each do |c| table << (x3 = 5 ** c) y2 = x2 * x3 y3 = x1 * x3 y4 = y1 * x3 table << y2 if y2 <= L table << y3 if y3 <= L table << y4 if y4 <= L end end end table.uniq!.sort! until (n = $<.gets.chomp) == "0" m, n = n.split.map(&:to_i) a = table.bsearch_index {|x| x >= m} b = table.bsearch_index {|x| x > n} b = b ? b : table.size puts b - a end
0163 Highway Toll
toll = [[0, 300, 500, 600, 700, 1350, 1650], [0, 0, 350, 450, 600, 1150, 1500], [0, 0, 0, 250, 400, 1000, 1350], [0, 0, 0, 0, 250, 850, 1300], [0, 0, 0, 0, 0, 600, 1150], [0, 0, 0, 0, 0, 0, 500]] S, E = 17 * 60 + 30, 19 * 60 + 30 until (d = $<.gets.to_i).zero? h, m = $<.gets.split.map(&:to_i) td = h * 60 + m a = $<.gets.to_i h, m = $<.gets.split.map(&:to_i) ta = h * 60 + m d, a = a, d if d > a f = if (a == 6 and d == 1) or (a == 7 and d <= 3) false elsif td.between?(S, E) or ta.between?(S, E) true else false end result = toll[d - 1][a - 1] result /= 2 if f puts ((result / 50.0).ceil * 50).to_i end
td, ta が S と E の間にあればよいということがなかなかわからなかった。
0164 Ohajiki Game
until (n = $<.gets.to_i).zero? ary = $<.gets.split.map(&:to_i) ohajiki = 32 loop do ohajiki -= (ohajiki - 1) % 5 puts ohajiki a = ary.first if ohajiki <= a ohajiki = 0 else ohajiki -= a end puts ohajiki break if ohajiki.zero? ary.rotate! end end
0165 Lottery
MP = 999983 sieve = [*0..MP] 2.upto(Math.sqrt(MP).to_i) do |i| next if sieve[i].zero? 2.upto(MP / i) {|j| sieve[i * j] = 0} end sieve = sieve[2..-1].reject {|x| x.zero?} until (n = $<.gets.to_i).zero? account = n.times.map do p, m = $<.gets.split.map(&:to_i) s = sieve.bsearch_index {|i| i >= p - m} e = sieve.bsearch_index {|i| i > p + m} || sieve.size prize = e - s prize.zero? ? -1 : prize - 1 end.sum puts account end
0166 Area of Polygon
until (m = $<.gets.to_i).zero? poly1 = (m - 1).times.map {$<.gets.to_i} poly1 << 360 - poly1.sum n = $<.gets.to_i poly2 = (n - 1).times.map {$<.gets.to_i} poly2 << 360 - poly2.sum area1 = poly1.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum area2 = poly2.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum result = case when area1 == area2 then 0 when area1 > area2 then 1 else 2 end puts result end
0167 Bubble Sort
def bubble_sort(ary) n = ary.size co = 0 (n - 1).downto(1) do |i| i.times do |j| if ary[j] > ary[j + 1] ary[j], ary[j + 1] = ary[j + 1], ary[j] co += 1 end end end co end until (n = $<.gets.to_i).zero? puts bubble_sort(n.times.map {$<.gets.to_i}) end
0168 Kannondou
@memo = {} def count(n) return @memo[n] if @memo[n] result = case n when 1 then 1 when 2 then 2 when 3 then 4 else count(n - 1) + count(n - 2) + count(n - 3) end @memo[n] = result end until (n = $<.gets.to_i).zero? days = Rational(count(n), 10).ceil puts Rational(days, 365).ceil end
0169 Blackjack
def calc(hand) i = hand.count(1) hand = hand - [1] point = 0 while (a = hand.pop) point += case a when 2..9 then a else 10 end end point1 = point2 = point + i point2 = point + 10 + i if i > 0 if point2 <= 21 point2 elsif point1 <= 21 point1 else 0 end end until (n = $<.gets.chomp) == "0" puts calc(n.split.map(&:to_i)) end
AOJ（問題集）16
AIZU ONLINE JUDGE: Programming Challenge
0150 Twin Prime
N = 10007 sieve = [*0..N] 2.upto(Math.sqrt(N).to_i) do |i| next if sieve[i].zero? 2.upto(N / i) {|j| sieve[i * j] = 0} end sieve = sieve[2..-1].reject {|x| x.zero?} until (n = $<.gets.to_i).zero? idx = sieve.index {|i| i > n} - 1 i = 0 i += 1 until sieve[idx - i] - sieve[idx - i - 1] == 2 puts "#{sieve[idx - i - 1]} #{sieve[idx - i]}" end
N = 10000 ではダメなことになかなか気づかなかった。
0151 Grid
def count(line) line.chunk {|i| i.nonzero?}.select(&:first).map {|l| l.last.size}.max || 0 end until (n = $<.gets.to_i).zero? field = n.times.map {$<.gets.chomp.chars.map(&:to_i)} max_l = field.map {|l| count(l)}.max max_l = [field.transpose.map {|l| count(l)}.max, max_l].max l = n - 1 n.times do |i| line = (i + 1).times.map {|j| field[i - j][j]} tmp1 = count(line) line = (i + 1).times.map {|j| field[l - i + j][l - j]} tmp2 = count(line) line = (i + 1).times.map {|j| field[i - j][l - j]} tmp3 = count(line) line = (i + 1).times.map {|j| field[l - i + j][j]} tmp4 = count(line) max_l = [tmp1, tmp2, tmp3, tmp4, max_l].max end puts max_l end
0.50秒。素朴にやった。まあまあか。
0152 Bowling
until (m = $<.gets.to_i).zero? result = m.times.map do id, *score = $<.gets.split.map(&:to_i) th = 0 final_point = 10.times.map do |i| if i == 9 if score[th] == 10 or score[th, 2].sum == 10 score[th, 3].sum else score[th, 2].sum end elsif score[th] == 10 th += 1 10 + score[th, 2].sum elsif score[th, 2].sum == 10 th += 2 10 + score[th] else th += 2 score[th - 2, 2].sum end end.sum [id, final_point] end.sort {|a, b| (b[1] <=> a[1]).nonzero? || a[0] <=> b[0]} puts result.map {|a| a.join(" ")} end
複数キーのソートはここを参考にしました。
0153 Triangle and Circle
def perpendicular_foot(a, b, p) s = Rational((p - a).dot(b - a), (b - a).dot(b - a)) h = a + (b - a) * s [s, (h - p).norm] end def triangle_inside(a, b, c, p) s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a s > 0 and t > 0 and 0 < s + t and s + t < 1 end until (p1 = $<.gets.split.map(&:to_i)) == [0, 0] p1 = Vector[*p1] p2 = Vector[*$<.gets.split.map(&:to_i)] p3 = Vector[*$<.gets.split.map(&:to_i)] c = Vector[*$<.gets.split.map(&:to_i)] r = $<.gets.to_i f1 = (p1 - c).norm f2 = (p2 - c).norm f3 = (p3 - c).norm g1 = (f1 <= r and f2 >= r) or (f1 >= r and f2 <= r) g2 = (f2 <= r and f3 >= r) or (f2 >= r and f3 <= r) g3 = (f3 <= r and f1 >= r) or (f3 >= r and f1 <= r) s, l = perpendicular_foot(p1, p2, c) h1 = (0 <= s and s <= 1) and (f1 >= r and f2 >= r) and l <= r e1 = l >= r and f1 > r and f2 > r s, l = perpendicular_foot(p2, p3, c) h2 = (0 <= s and s <= 1) and (f2 >= r and f3 >= r) and l <= r e2 = l >= r and f2 > r and f3 > r s, l = perpendicular_foot(p3, p1, c) h3 = (0 <= s and s <= 1) and (f3 >= r and f1 >= r) and l <= r e3 = l >= r and f3 > r and f1 > r e0 = triangle_inside(p1, p2, p3, c) result = if e0 and e1 and e2 and e3 "a" elsif f1 <= r and f2 <= r and f3 <= r "b" elsif g1 or g2 or g3 or h1 or h2 or h3 "c" else "d" end puts result end
Wrong Answer.
require 'matrix' def perpendicular_foot(a, b, p) s = Rational((p - a).dot(b - a), (b - a).dot(b - a)) h = a + (b - a) * s (h - p).norm end def triangle_inside(a, b, c, p) s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a s > 0 and t > 0 and 0 < s + t and s + t < 1 end until (p1 = $<.gets.split.map(&:to_i)) == [0, 0] p1 = Vector[*p1] p2 = Vector[*$<.gets.split.map(&:to_i)] p3 = Vector[*$<.gets.split.map(&:to_i)] c = Vector[*$<.gets.split.map(&:to_i)] r = $<.gets.to_i f1 = (p1 - c).norm f2 = (p2 - c).norm f3 = (p3 - c).norm l = perpendicular_foot(p1, p2, c) h1 = l > r e1 = l >= r and f1 > r and f2 > r l = perpendicular_foot(p2, p3, c) h2 = l > r e2 = l >= r and f2 > r and f3 > r l = perpendicular_foot(p3, p1, c) h3 = l > r e3 = l >= r and f3 > r and f1 > r e0 = triangle_inside(p1, p2, p3, c) result = if e0 and e1 and e2 and e3 "a" elsif f1 <= r and f2 <= r and f3 <= r "b" elsif f1 > r and f2 > r and f3 > r and h1 and h2 and h3 "d" else "c" end puts result end
Wrong Answer.
require 'matrix' def perpendicular_foot(a, b, p) s = Rational((p - a).dot(b - a), (b - a).dot(b - a)) h = a + (b - a) * s (h - p).norm end def triangle_inside(a, b, c, p) s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a s > 0 and t > 0 and 0 < s + t and s + t < 1 end until (p1 = $<.gets.split.map(&:to_i)) == [0, 0] p1 = Vector[*p1] p2 = Vector[*$<.gets.split.map(&:to_i)] p3 = Vector[*$<.gets.split.map(&:to_i)] c = Vector[*$<.gets.split.map(&:to_i)] r = $<.gets.to_i f1 = (p1 - c).norm f2 = (p2 - c).norm f3 = (p3 - c).norm h1 = perpendicular_foot(p1, p2, c) h2 = perpendicular_foot(p2, p3, c) h3 = perpendicular_foot(p3, p1, c) e0 = triangle_inside(p1, p2, p3, c) result = if h1 >= r and h2 >= r and h3 >= r and e0 "a" elsif h1 > r and h2 > r and h3 > r and !e0 "d" elsif f1 <= r and f2 <= r and f3 <= r "b" else "c" end puts result end
Wrong Answer.
require 'matrix' def perpendicular_foot(a, b, p) s = Rational((p - a).dot(b - a), (b - a).dot(b - a)) h = a + (b - a) * s (h - p).dot(h - p) end def triangle_inside(a, b, c, p) s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a s > 0 and t > 0 and 0 < s + t and s + t < 1 end until (p1 = $<.gets.split.map(&:to_i)) == [0, 0] p1 = Vector[*p1] p2 = Vector[*$<.gets.split.map(&:to_i)] p3 = Vector[*$<.gets.split.map(&:to_i)] c = Vector[*$<.gets.split.map(&:to_i)] r = $<.gets.to_i ** 2 f1 = (p1 - c).dot(p1 - c) f2 = (p2 - c).dot(p2 - c) f3 = (p3 - c).dot(p3 - c) h1 = perpendicular_foot(p1, p2, c) h2 = perpendicular_foot(p2, p3, c) h3 = perpendicular_foot(p3, p1, c) e0 = triangle_inside(p1, p2, p3, c) result = if f1 <= r and f2 <= r and f3 <= r "b" elsif f1 > r and f2 > r and f3 > r min_h = [h1, h2, h3].min if e0 and min_h >= r "a" elsif !e0 and min_h > r "d" else "c" end else "c" end puts result end
Wrong Answer.
0154 Sum of Cards
until (m = $<.gets.to_i).zero? cards = m.times.map {$<.gets.split.map(&:to_i)} ln = cards.map {|a, b| a * b}.sum table = [0] cards.each do |a, b| table = table.flat_map do |num| (b + 1).times.map {|i| num + a * i} end end $<.gets.to_i.times do puts table.count($<.gets.to_i) end end
20.9秒もかかったのに accept された。
他の人の回答を見てみた。
until (m = $<.gets.to_i).zero? cards = m.times.map {$<.gets.split.map(&:to_i)} memo = Array.new(cards.size + 1) {[]} $<.gets.to_i.times do count = ->(i, left) { return memo[i][left] if memo[i][left] if i >= cards.length co = left.zero? ? 1 : 0 else co = 0 a, b = cards[i] (b + 1).times do |j| nxt = left - a * j break if nxt < 0 co += count.(i + 1, nxt) end end memo[i][left] = co } puts count.(0, $<.gets.to_i) end end
0.07秒…。何でこれに気づかない…。
0155 Spider Jin
until (n = $<.gets.to_i).zero? buildings = n.times.map {$<.gets.split.map(&:to_i)} sg = $<.gets.to_i.times.map {$<.gets.split.map(&:to_i)} table = Hash.new {|h, k| h[k] = {}} buildings.combination(2) do |a, b| ida, xa, ya = a idb, xb, yb = b dist = (xa - xb) ** 2 + (ya - yb) ** 2 next if dist > 50 ** 2 table[ida][idb] = Math.sqrt(dist) table[idb][ida] = Math.sqrt(dist) end h = table.map {|k, v| [k, v.keys]}.to_h sg.each do |s, g| shortest = Hash.new(Float::INFINITY) pred = {} done = h.keys.map {|k| [k, false]}.to_h shortest[s] = 0 loop do u = nil h.each_key do |node| next if done[node] u = node if !u or shortest[node] < shortest[u] end break unless u done[u] = true h[u].each do |v| if (a = shortest[u] + table[u][v]) < shortest[v] shortest[v] = a pred[v] = u end end end result = if pred[g] order = [] while g order.unshift(g) g = pred[g] end order.join(" ") else "NA" end puts result end end
ダイクストラ法。
0156
until (a = io.gets.split.map(&:to_i)) == [0, 0] n, m = a field = m.times.map {io.gets.chomp.chars} i = field.flatten.index("&") numbering = ->(x, y, num) { type = field[y][x] queue = [[x, y]] while (a = queue.shift) x0, y0 = a field[y0][x0] = num [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| x1 = x0 + dx y1 = y0 + dy return num if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m next if field[y1][x1] != type next if ![".", "#", "&"].include?(field[y1][x1]) queue << [x1, y1] end end false } catch :jump do x, y = i % n, i / n [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| x1 = x + dx y1 = y + dy if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m puts 0 throw :jump else num = (field[y1][x1] == "#") ? 0 : 1 num = numbering.(x1, y1, num) if num puts 0 throw :jump end end end puts -1 end puts field.map(&:join) end
考え中。
0157 Russian Dolls
until (n = $<.gets.to_i).zero? ichiro = n.times.map {$<.gets.split.map(&:to_i)} .sort {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]} m = $<.gets.to_i jiro = m.times.map {$<.gets.split.map(&:to_i)} .sort {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]} memo = {} try = ->(h, r, ichi, ji) { key = "#{h},#{r},#{ichi},#{ji}" return memo[key] if memo[key] return 0 if ichi >= n and ji >= m co1 = co2 = 0 if ichiro[ichi] if h > ichiro[ichi][0] and r > ichiro[ichi][1] co1 = 1 + try.(ichiro[ichi][0], ichiro[ichi][1], ichi + 1, ji) else co1 = try.(h, r, ichi + 1, ji) end end if jiro[ji] if h > jiro[ji][0] and r > jiro[ji][1] co2 = 1 + try.(jiro[ji][0], jiro[ji][1], ichi, ji + 1) else co2 = try.(h, r, ichi, ji + 1) end end memo[key] = (co1 > co2) ? co1 : co2 } puts try.(Float::INFINITY, Float::INFINITY, 0, 0) end
これで 0.14秒。自力で考えたオレはえらいが、これは DAG（閉路なし有向グラフ）の最長経路問題なのだった。
なので、動的計画法で解くのがふつうらしい。こんな感じ。
until (n = $<.gets.to_i).zero? dolls = n.times.map {$<.gets.split.map(&:to_i)} m = $<.gets.to_i dolls += m.times.map {$<.gets.split.map(&:to_i)} dolls.sort! {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]} longest = Array.new(n + m, 0) (0..n + m - 2).each do |i| (i + 1...n + m).each do |j| if dolls[i][0] > dolls[j][0] and dolls[i][1] > dolls[j][1] if (a = longest[i] + 1) > longest[j] longest[j] = a end end end end puts longest.last + 1 end
これで 0.06秒。
0158 Collatz's Problem
@memo = {} def try(n) return @memo[n] if @memo[n] return 0 if n == 1 co = if n.even? try(n / 2) else try(n * 3 + 1) end @memo[n] = co + 1 end until (n = $<.gets.to_i).zero? puts try(n) end
0159 The Best Body
until (n = $<.gets.to_i).zero? min_dif = Float::INFINITY persons = [] n.times.map {$<.gets.split.map(&:to_i)}.each do |p, h, w| h = Rational(h, 100) dif = (Rational(w, h * h) - 22).abs if dif < min_dif persons = [p] min_dif = dif elsif dif == min_dif persons << p end end puts persons.sort.first end
AOJ（問題集）15
AIZU ONLINE JUDGE: Programming Challenge
0140 Bus Line
line = [*0..9] + [5, 4, 3, 2, 1] line += line $<.gets.to_i.times do start, goal = $<.gets.split.map(&:to_i) str = if 1 <= start and start <= 5 and start > goal [*goal..start].reverse.join(" ") else a = line.index(start) b = line[a + 1..-1].index(goal) line[a..a + 1 + b].join(" ") end puts str end
0141 Spiral Pattern
ぐるぐる模様。
result = [] $<.gets.to_i.times do n = $<.gets.to_i field = Array.new(n) {" " * n} x, y = 0, n - 1 go = ->(dx, dy, l) { l.times do field[y][x] = "#" x += dx y += dy end } square = ->(l) { if l != 1 go.(0, -1, l - 1) go.(1, 0, l - 1) go.(0, 1, l - 1) if l != 3 go.(-1, 0, l - 3) if l != 4 if l > 4 go.(0, -1, 2) square.(l - 4) end return end end end field[y][x] = "#" } square.(n) result << field.map {|l| l + "\n"}.join end puts result.join("\n")
思っていたよりずっとむずかしかった。これがいちばんよいやり方か自信がない。実際、Ruby で解けた人は自分も含めて 4人しかいない。
0142 Nature of Prime Numbers
素朴に実装してみる。
until (n = $<.gets.to_i).zero? rems = (1...n).map {|i| i * i % n}.uniq.permutation(2).map do |a, b| rem = a - b rem += n if rem < 0 rem = n - rem if rem > (n - 1) / 2 rem end puts (1..(n - 1) / 2).map {|i| rems.count(i)} end
時間オーバー。
0143 Altair and Vega
require 'matrix' $<.gets.to_i.times do given = $<.gets.split.map(&:to_r).each_slice(2).map {|x, y| Vector[x, y]} p1, p2, p3, k, s = given calc = ->(r) { Matrix.columns([p2 - p1, p3 - p1]).lup.solve(r - p1).to_a } s1, t1 = calc.(k) s2, t2 = calc.(s) f1 = s1 + t1 < 1 && s1 > 0 && t1 > 0 f2 = s2 + t2 < 1 && s2 > 0 && t2 > 0 puts f1 ^ f2 ? "OK" : "NG" end
こういう問題は慣れてきた。
0144 Packet Transportation
address = $<.gets.to_i.times.map do r, k, *t = $<.gets.split.map(&:to_i) [r, t] end.to_h $<.gets.to_i.times do s, d, v = $<.gets.split.map(&:to_i) queue = [[s]] catch :jump do while (now = queue.shift) and now.size <= v if now.last == d puts now.size throw :jump else address[now.last].each do |to| next if now.include?(to) queue << now + [to] end end end puts "NA" end end
幅優先探索なのだが、なんとメモリオーバー。
ダイクストラ法でやる。
class Node def initialize(t) @to = t @cost = Float::INFINITY @done = false end attr_accessor :to, :cost, :done end given = $<.gets.to_i.times.map do r, k, *t = $<.gets.split.map(&:to_i) [r, Node.new(t)] end.to_h $<.gets.to_i.times do s, d, v = $<.gets.split.map(&:to_i) nodes = Marshal.load(Marshal.dump(given)) nodes[s].cost = 0 loop do u = nil nodes.each_value do |node| next if node.done u = node if !u or node.cost < u.cost end break unless u u.done = true u.to.each do |v| if (a = u.cost + 1) < nodes[v].cost nodes[v].cost = a end end end i = nodes[d].cost + 1 puts (i <= v) ? i : "NA" end
1.15秒かかった。他の人の回答を見ると、やはりうまく幅優先探索で実装したほうが圧倒的に速い。
やってみる。
address = $<.gets.to_i.times.map do r, k, *t = $<.gets.split.map(&:to_i) [r, t] end.to_h $<.gets.to_i.times do s, d, v = $<.gets.split.map(&:to_i) queue = [s] dist = {s=>1} until !(now = queue.shift) or now == d address[now].each do |nxt| unless dist[nxt] dist[nxt] = dist[now] + 1 queue << nxt end end end ds = dist[now] puts ds && (ds <= v) ? ds : "NA" end
これだと 0.06秒。瞬殺である。
0145 Cards
decks = $<.gets.to_i.times.map {$<.gets.split.map(&:to_i)} L = decks.size memo = Array.new(L) {[]} minimum = ->(left, right) { return memo[left][right] if memo[left][right] result = if left == right 0 else (right - left).times.map do |i| decks[left][0] * decks[left + i][1] * decks[left + i + 1][0] * decks[right][1] + minimum.(left, left + i) + minimum.(left + i + 1, right) end.min end memo[left][right] = result } puts minimum.(0, L - 1)
0146 Lupin The 4th
全然思いつかない。とりあえず総当り。
n = $<.gets.to_i kuras = $<.readlines.map {|i| i.split.map(&:to_i)} min = Float::INFINITY result = nil try = ->(reached = [], w = 0, t = 0, before = nil) { return if t >= min if reached.size == n if t < min min = t result = reached end else kuras.each do |k| next if reached.include?(k[0]) before ||= k[1] l = (k[1] - before).abs v = 2000 / (70 + w.to_r) try.(reached + [k[0]], w + k[2] * 20, t + l / v, k[1]) end end } try.() puts result.join(" ")
予想通りタイムオーバー。
いつものごとく tnakao さんの回答を参考にする。なるほど、蔵間の距離はあらかじめ求めておけばよい。また、これは重要だが、出発点と残っている蔵が確定していれば、残りの順番は確定するということ（千両箱の重さに順番は関係ない）。うーん、すばらしい洞察だ。
n = io.gets.to_i
kuras = io.readlines.map {|i| i.split.map(&:to_i)}
kuras.each {|k| k[2] *= 20}
edges = Array.new(n) {[nil] * n}
n.times do |i|
(i + 1...n).each {|j| edges[i][j] = edges[j][i] = (kuras[i][1] - kuras[j][1]).abs}
end
all = (1 << n) - 1
memo = Array.new(n) {[]}
n.times {|i| memo[i][all ^ (1 << i)] = [0, [kuras[i][0]]]}
try = ->(start, reached = 0, w = 0) {
return memo[start][reached] if memo[start][reached]
now = kuras[start]
min_time = Float::INFINITY
min_order = nil
nr = reached | (1 << start)
w0 = w + now[2]
n.times do |nxt|
next if (nr & (1 << nxt)).nonzero?
time, order = try.(nxt, nr, w0)
time += edges[start][nxt] * (70 + w0).to_r / 2000
if time < min_time
min_time = time
min_order = [now[0]] + order
end
end
memo[start][reached] = [min_time, min_order]
}
puts (0...n).map {|i| try.(i)}.sort_by(&:first).first.last.join(" ")
その方向でやってみる。3.99秒でクリア。
0147 Fukushimaken
table = [0, 0, 0, 0, 0, 0, 14, 9, 4, 0, 0, 8, 3, 2, 0, 0, 15, 10, 15, 10, 6, 12, 7, 9, 11, 6, 23, 18, 13, 8, 3, 23, 18, 13, 8, 3, 34, 29, 24, 22, 17, 28, 23, 24, 19, 27, 34, 29, 35, 30, 28, 31, 28, 23, 24, 28, 42, 37, 32, 27, 22, 42, 37, 32, 27, 22, 53, 48, 43, 41, 36, 47, 42, 43, 38, 46, 64, 59, 54, 49, 44, 61, 56, 51, 46, 44, 72, 67, 62, 57, 52, 72, 67, 62, 57, 52, 83, 78, 73, 71] puts $<.readlines.map(&:to_i).map {|i| table[i]}
あらかじめ計算しておけばよい。table を得るためのコードは以下。
N = 100 S = 17 in_time = (0...N).map {|i| 5 * i} numbers = (0...N).map {|i| (i % 5 == 1) ? 5 : 2} eating_time = (0...N).map {|i| 17 * (i % 2) + 3 * (i % 3) + 19} finish_time = Array.new(N, -1) seats = Array.new(S, -1) waiting = [] waiting_time = Array.new(N, -1) 0.step do |now| # 食べ終わったグループの処理 N.times do |j| next unless finish_time[j] == now seats = seats.map {|i| i == j ? -1 : i} end # 入ってきたグループの処理 come_in = in_time.index(now) waiting << come_in if come_in # 座れる場合の処理 sittable = ->(i) { index = ->(size) { j = 0 while j < S return j if seats[j, size] == [-1] * size j += 1 end false } idx = index.(numbers[i]) if idx numbers[i].times {|j| seats[idx + j] = i} true else false end } while (head = waiting.first) and sittable.(head) waiting_time[head] = now - in_time[head] waiting.shift finish_time[head] = now + eating_time[head] end break if seats.all? {|i| i < 0} end p waiting_time
0148 Candy and Class Flag
result = $<.readlines.map(&:to_i).map do |a| sprintf "3C%02d", (i = a % 39).zero? ? 39 : i end puts result
0149 Eye Test
L = 4 table = [[1.1, Float::INFINITY], [0.6, 1.1], [0.2, 0.6], [0, 0.2]] left = Array.new(L, 0) right = Array.new(L, 0) count = ->(a, counter) { table.each_with_index do |d, i| counter[i] += 1 if d[0] <= a and a < d[1] end counter } $<.readlines.map {|l| l.split.map(&:to_f)}.each do |l, r| left = count.(l, left) right = count.(r, right) end L.times do |i| puts "#{left[i]} #{right[i]}" end
何だか冗長なコードになってしまった。
AOJ（問題集）14
AIZU ONLINE JUDGE: Programming Challenge
0130 Train
$<.gets.to_i.times do given = $<.gets.chomp.split(/(->|<-)/) train = [given.shift] while (dir = given.shift) car = given.shift next if train.include?(car) (dir == "->") ? train.push(car) : train.unshift(car) end puts train.join end
出来てみればじつに簡単なことなのに、ものすごく悩んだ。
0131 Doctor's Strange Particles
L = 10 $<.gets.to_i.times do field = Array.new(L) {$<.gets.split.map(&:to_i)}.flatten result = Array.new(L * L, 0) reverse = ->(x, y) { [[0, 0], [1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| x1 = x + dx y1 = y + dy next if x1 < 0 or x1 >= L or y1 < 0 or y1 >= L i = y1 * L + x1 field[i] = 1 - field[i] end } top_row = ->(i) { if i >= L tmp1 = field.dup tmp2 = result.dup while i < L * L if field[i - L] == 1 result[i] = 1 reverse.(i % L, i / L) end i += 1 end if field.all? {|i| i.zero?} puts result.each_slice(L).map {|a| a.join(" ")} true else field = tmp1 result = tmp2 false end else return true if top_row.(i + 1) result[i] = 1 reverse.(i % L, i / L) return true if top_row.(i + 1) reverse.(i % L, i / L) result[i] = 0 false end } top_row.(0) end
些細なミスが多かった。
0132 Jigsaw Puzzle
until (a = $<.gets.split.map(&:to_i)) == [0, 0] h, w = a puzzle = h.times.map {$<.gets.chomp} pieces = $<.gets.to_i.times.flat_map do ph, pw = $<.gets.split.map(&:to_i) tmp = [ph.times.map {$<.gets.chomp}] 3.times do tmp << tmp.last.reverse.map(&:chars).transpose.map(&:join) end tmp end $<.gets.to_i.times do k, *tn = $<.gets.split.map(&:to_i) tn = tn.map {|i| i - 1}.sort tn1 = tn.flat_map {|i| 4.times.map {|j| i * 4 + j}}.sort solve = ->(embeded, selected = [], selected_num = []) { return true if !embeded.join.index(".") and tn == selected_num adjust = ->(piece, piece_num) { idx = embeded.join.index(".") return false unless idx x, y = idx % w, idx / w p_idx = piece.join.index("#") pw = piece.first.length px = p_idx % pw return false if x + pw - px >= w return false if (x -= px) < 0 nxt = embeded.map(&:dup) piece.each_index do |i| piece[i].each_char.with_index do |c, j| if c == "#" if embeded[y + i][x + j] == "." nxt[y + i][x + j] = (piece_num / 4).to_s else return false end end end end nxt } (tn1 - selected).each do |pn| next unless selected.select {|i| i / 4 == pn / 4}.empty? if (nxt = adjust.(pieces[pn], pn)) return true if solve.(nxt, selected + [pn], (selected_num + [pn / 4]).sort) end end false } puts solve.(puzzle) ? "YES" : "NO" end end
時間オーバー。
until (a = $<.gets.split.map(&:to_i)) == [0, 0] h, w = a puzzle = h.times.map {$<.gets.chomp} pieces = (n = $<.gets.to_i).times.map do ph, pw = $<.gets.split.map(&:to_i) ph.times.map {$<.gets.chomp} end io.gets.to_i.times do k, *tn = $<.gets.split.map(&:to_i) tn = tn.map {|i| i - 1}.sort solve = ->(embeded, selected = []) { return true if !embeded.join.index(".") and tn == selected adjust = ->(piece) { idx = embeded.join.index(".") return false unless idx x, y = idx % w, idx / w p_idx = piece.join.index("#") pw = piece.first.length px = p_idx % pw return false if x + pw - px >= w return false if (x -= px) < 0 nxt = embeded.map(&:dup) piece.each_index do |i| piece[i].each_char.with_index do |c, j| if c == "#" if embeded[y + i][x + j] == "." nxt[y + i][x + j] = "#" else return false end end end end nxt } check = ->(piece_num) { candidate = pieces[piece_num] nexts = [] 4.times do if (nxt = adjust.(candidate)) nexts << nxt end candidate = candidate.reverse.map(&:chars).transpose.map(&:join) end nexts.empty? ? false : nexts } (tn - selected).each do |piece_num| if (nexts = check.(piece_num)) nexts.each do |nxt| return true if solve.(nxt, (selected + [piece_num]).sort) end end end false } puts solve.(puzzle) ? "YES" : "NO" end end
上も下もやり方は合っていると思うけれど、時間オーバー。Ruby では誰も解けていない。
0133 Rotation of a Pattern
given = $<.readlines.map(&:chomp) 3.times do |i| puts 90 * (i + 1) puts given = given.reverse.map(&:chars).transpose.map(&:join) end
突然簡単に。
0134 Exit Survey
n = $<.gets.to_i puts Array.new(n) {$<.gets.to_i}.sum / n
0135 Clock Short Hand and Long Hand
$<.gets.to_i.times do h, m = $<.gets.split(":").map(&:to_r) l, s = m * 6, (h * 60 + m) / 2 r = (l - s).abs r = 360 - r if r > 180 st = if 0 <= r and r < 30 "alert" elsif 90 <= r and r <= 180 "safe" else "warning" end puts st end
0136 Frequency Distribution of Height
度数分布。
L = 6 table = 165.0.step(185.0, 5.0).each_cons(2).to_a table = [[0, 165.0]] + table + [[185.0, Float::INFINITY]] count = Array.new(L, 0) $<.gets.to_i.times do h = $<.gets.to_f count[table.index {|a, b| a <= h and h < b}] += 1 end count.each_with_index {|i, j| puts "#{j + 1}:" + "*" * i}
0137 Middle-Square Method
平方採中法。
$<.gets.to_i.times do |i| num = $<.gets.to_i rnd = Enumerator.new do |y| loop do num = (num * num).to_s.rjust(8, "0")[2, 4].to_i y << num end end puts "Case #{i + 1}:" puts rnd.take(10) end
Ruby っぽいコードだと思います。Enumerator にぴったりな問題というのはあまりない気がする。
0138 Track and Field Competition
get = ->{ Array.new(8) {$<.gets.chomp.split} }
left = 3.times.flat_map do
given = get.().sort_by {|a| a.last.to_f}
puts given.shift.join(" ")
puts given.shift.join(" ")
given
end.sort_by {|a| a.last.to_f}
puts left.shift.join(" ")
puts left.shift.join(" ")
0139 Snakes
$<.gets $<.readlines.map(&:chomp).each do |line| s1 = /^>'(=+)#(=+)~$/.match(line) s2 = /^>\^(Q=)+~~$/.match(line) str = if s1 and s1[1] == s1[2] "A" elsif s2 "B" else "NA" end puts str end
正規表現を使うのはめずらしい。
AOJ（問題集）13
AIZU ONLINE JUDGE: Programming Challenge
0120 Patisserie
@memo = {} def length(circles) return @memo[circles] if @memo[circles] l = case (s = circles.size) when 0 then 0 when 1 then 0 when 2 r1, r2 = circles.first, circles.last Math.sqrt((r1 + r2) ** 2 - (r1 - r2) ** 2) else s1 = s / 2 length(circles[0..s1]) + length(circles[s1..-1]) end @memo[circles] = l end $<.readlines.map {|l| l.split.map(&:to_i)}.each do |w, *r| minimum = Float::INFINITY result = "NA" r.permutation do |circles| l = circles.first + length(circles) + circles.last minimum = [minimum, l].min if minimum <= w result = "OK" break end end puts result end
時間オーバー。まるで思いつかない。こういうパッキングの問題は決まった解法がないらしい。
他の人の回答を見た。
#!ruby -pal $c={} def f l,*a a[0]?($c[a.sort<<l]||=a.map{f(*a.rotate!)+(4*a[0]*l)**0.5}.min):l end m,*r=$F.map &:to_i $_=r.any?{f(*r.rotate!)+r[0]<=m}?:OK:"NA"
???
読めるように書き直してもわからない。
$c = {} def f(l, *a) if a[0] $c[a.sort << l] ||= a.map{ f(*a.rotate!) + (4 * a[0] * l) ** 0.5 }.min else l end end while (a = $<.gets) m, *r = a.split.map(&:to_i) puts r.any? {f(*r.rotate!) + r[0] <= m} ? "OK" : "NA" end
ははあ、なるほど、並び方の順番は結果に関係なくて、ただ両端のみ関係するのか。そうなのかな。だから rotate でやっているのね。ふーむ、よく考えてみよう。決して自明ではないと思う。
しかしこのコード超すごいな。これでメモ化までやっているとは。圧倒的なコード量の少なさだ。
ちなみにこの問題、Ruby では四人しか正解できていない。
0121 Seven Puzzle
A = [*0..7] memo = {A=>0} stack = [A + [0]] check = [A.join.to_i] while (board = stack.shift) swap = ->(a, b) { tmp = board.dup tmp[a], tmp[b] = tmp[b], tmp[a] tmp } move = case (i = board.index(0)) when 0 then [1, 4] when 1, 2 then [i - 1, i + 1, i + 4] when 3 then [2, 7] when 4 then [0, 5] when 5, 6 then [i - 1, i + 1, i - 4] when 7 then [3, 6] end move.each do |j| nxt = swap.(i, j) a = nxt[0, 8].join.to_i next if check.include?(a) nxt[8] += 1 memo[nxt[0, 8]] = nxt[8] check << a stack << nxt end end $<.readlines.map {|a| a.split.map(&:to_i)}.each do |given| puts memo[given] end
2.05秒かかった。最初苦し紛れで書いたのがヒントになった。あらかじめ全パターンを計算しておくという方法。ちなみに全パターンは 20160 通りある。
他の人の回答を参考にして、modify したバージョン。
A = "01234567" memo = {A=>0} stack = [[A, 0]] table = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [4, 6, 1], [5, 7, 2], [3, 6]].freeze while (board = stack.shift) swap = ->(a, b) { tmp = board.first.dup tmp[a], tmp[b] = tmp[b], tmp[a] [tmp, board.last] } i = board.first.index("0") table[i].each do |j| nxt = swap.(i, j) next if memo[nxt.first] nxt[1] += 1 memo[nxt.first] = nxt.last stack << nxt end end $<.readlines.map {|a| a.split.join}.each do |given| puts memo[given] end
これだと 0.16秒。Array を String に替え、冗長な部分を削った（不必要な check[] を無くした）。
0122 Summer of Pyonkichi
L = 10 movable = [[-1, -2], [0, -2], [1, -2], [-1, 2], [0, 2], [1, 2], [-2, -1], [-2, 0], [-2, 1], [ 2, -1], [ 2, 0], [ 2, 1]] until (a = $<.gets.split.map(&:to_i)) == [0, 0] px, py = a n = $<.gets.to_i result = "NA" sprinkler = $<.gets.split.map(&:to_i).each_slice(2).to_a try = ->(x, y, i = 0) { if i == n result = "OK" else s = sprinkler[i] movable.each do |dx, dy| nx = x + dx ny = y + dy check = ->{ nx.between?(s[0] - 1, s[0] + 1) && ny.between?(s[1] - 1, s[1] + 1) } next if nx < 0 or nx >= L or ny < 0 or ny >= L try.(nx, ny, i + 1) if check.() end end } try.(px, py) puts result end
コーディングは楽ではないけれど、バックトラック法とわかっているから助かる。
0123 Speed Skating Badge Test
table = [[35.5, 71.0, :AAA], [37.5, 77.0, :AA], [40.0, 83.0, :A], [43.0, 89.0, :B], [50.0, 105.0, :C], [55.0, 116.0, :D], [70.0, 148.0, :E]] $<.readlines.map {|l| l.split.map(&:to_f)}.each do |a, b| catch :jump do table.each do |ta, tb, cname| if a < ta and b < tb puts cname throw :jump end end puts "NA" end end
ひさしぶりに極簡単。ホッとするなあ。
0124 League Match Score Sheet
result = [] until (n = $<.gets.to_i).zero? teams = Array.new(n) do name, *nums = $<.gets.split po = nums.map(&:to_i).zip([3, 0, 1]).inject(0) {|acc, i| acc + i[0] * i[1]} [name, po] end.sort {|a, b| b[1] <=> a[1]} result << teams.map {|a| a.join(",") + "\n"}.join end puts result.join("\n")
0125 Day Count
require 'date' until (a = $<.gets.split.map(&:to_i)).index {|i| i < 0} puts (Date.new(*a[3, 3]) - Date.new(*a[0, 3])).to_i end
標準添付ライブラリを使うというインチキ。
0126 Puzzle
L = 9 T = L / 3 def check(line) co = Hash.new(0) line.each {|num| co[num] += 1} (0...L).select {|i| co[line[i]] > 1} end def square L.times {|i| yield(i % T, i / T)} end result = [] $<.gets.to_i.times do field = Array.new(L) {$<.gets.split.map(&:to_i)} marked = [] field.each_with_index do |row, i| marked += check(row).map {|j| i * L + j} end L.times do |i| col = Array.new(L) {|j| field[j][i]} marked += check(col).map {|k| k * L + i} end square do |x, y| sx, sy = x * T, y * T block = Array.new(L) {|i| field[sy + i / T][sx + i % T]} marked += check(block).map {|i| (sy + i / T) * L + sx + i % T} end result << field.flatten.map.with_index do |num, i| str = (marked.include?(i) ? "*" : " ") + num.to_s str + ((i % L == L - 1) ? "\n" : "") end.join end puts result.join("\n")
意外とむずかしい。というか面倒くさい。
0127 Pocket Pager Input
table = {"61"=>"z", "62"=>".", "63"=>"?", "64"=>"!", "65"=>" "}
25.times {|i| table["#{i / 5 + 1}#{i % 5 + 1}"] = (97 + i).chr}
$<.readlines.map(&:chomp).each do |cipher|
catch :jump do
text = ""
i = 0
while i < cipher.size
a = table[cipher[i, 2]]
unless a
puts "NA"
throw :jump
end
text += a
i += 2
end
puts text
end
end
0128 Abacus
そろばん。
L = 5 table = Array.new(10) {|i| [i / 5, i % 5]} r = $<.readlines.map {|l| l.chomp.rjust(L, "0").chars.map(&:to_i)}.map do |given| soroban = given.map do |place| high, low = table[place] ((high.zero? ? "* =" : " *=") + "*" * low + " " + "*" * (4 - low)).chars end soroban.transpose.map {|l| l.join + "\n"}.join end.join("\n") print r
0129 Hide-and-Seek Supporting System
かくれんぼう。
require 'matrix' until (num = $<.gets.to_i).zero? circles = Array.new(num) do x, y, r = $<.gets.split.map(&:to_r) [Vector[x, y], r] end $<.gets.to_i.times do tx, ty, sx, sy = $<.gets.split.map(&:to_r) ta = Vector[tx, ty] oni = Vector[sx, sy] v = ta - oni n = Vector[v[1], -v[0]].normalize f = circles.map do |o, r| pos1 = (oni - o).norm < r pos2 = (ta - o).norm < r if pos1 and pos2 false elsif !pos1 and !pos2 s, t = Matrix.columns([v, -n]).lup.solve(o - oni).to_a s.between?(0, 1) and t.abs <= r else true end end.any? puts f ? "Safe" : "Danger" end end
1.28秒かかった。他の人は瞬殺だけれど、それでも Ruby で解けているのは 3人しかいませんよ。自慢自慢。
AOJ（問題集）12
AIZU ONLINE JUDGE: Programming Challenge
0110 Alphametic
$<.readlines.map(&:chomp).map {|l| l.split(/\+|=/)}.each do |given| catch(:jump) do 10.times do |i| d = given.map {|a| a.gsub("X", i.to_s)} next unless d.select {|s| s.length >= 2 and s[0] == "0"}.empty? next unless d[0].to_i + d[1].to_i == d[2].to_i puts i throw(:jump) end puts "NA" end end
0111 Doctor's Memorable Codes
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"=>"?"}
table1 = table1.invert.sort_by {|a| a.first}
table2 = table2.invert
$<.readlines.map(&:chomp).each do |text|
result = ""
text.each_char {|c| result += table2[c]}
convert = ->(txt, converted = "") {
table1.each do |k, v|
l = k.length
converted = convert.(txt[l..-1], converted + v) if txt[0, l] == k
end
converted
}
puts convert.(result)
end
0112 A Milk Shop
until (num = $<.gets.to_i).zero? order = Array.new(num) {$<.gets.to_i}.sort[0..-2] each_wait = 0 puts order.map {|t| each_wait += t}.sum end
0113 Period
循環少数。
def calc(p, q) rems = [] place = [] begin rems << p place << p * 10 / q p = p * 10 % q return place.join if p.zero? end until (idx = rems.find_index(p)) result = (st = place.join) + "\n" result + " " * idx + "^" * (st.length - idx) end $<.readlines.map {|l| l.split.map(&:to_i)}.each do |p, q| puts calc(p % q, q) end
循環少数についてはここで考えておいたのが役立った。
0114 Electro-Fly
until (a = $<.gets.split.map(&:to_i)) == [0] * 6 po = [1, 1, 1] co = 0 result = loop do po = a.each_slice(2).zip(po).map {|am, i| am[0] * i % am[1]} co += 1 break co if po == [1, 1, 1] end puts result end
これでは例題すらフリーズする。高速化を考えないといけない。
よく考えたらわかった。
def calc(a, m) i = 1 1.step do |co| i = a * i % m return co if i == 1 end end until (a = $<.gets.split.map(&:to_i)) == [0] * 6 cx, cy, cz = a.each_slice(2).map {|a, m| calc(a, m)} puts cx.lcm(cy).lcm(cz) end
0115 Starship UAZ Advance
宇宙船 UAZ アドバンス号の巻です（参照）。ビームが当たるかを行列演算で求めている。
require 'matrix' myship, enemy, b1, b2, b3 = $<.readlines.map {|l| Vector[*l.split.map(&:to_r)]} v = enemy - myship va = b2 - b1 vb = b3 - b1 begin l, s, t = Matrix.columns([-v, va, vb]).lup.solve(myship - b1).to_a rescue puts "HIT" exit end puts 0 < l && l <= 1 && (s + t).between?(0, 1) && s >= 0 && t >= 0 ? "MISS" : "HIT"
うおお、俺スゲーって感じ。というか、本当は Ruby の Matrix がすごい。
Ruby で解けたのはいまのところ 6人だけ。その中でも自分のは圧倒的にコードのバイト数が少ない。ひゅー。
しかしまあ、数学の問題としては別にむずかしいものではない。手作業では計算が面倒というだけ。そこがプログラミングだな。
0116 Rectangular Searching
until (a = $<.gets.split.map(&:to_i)) == [0, 0] h, w = a field = Array.new(h) do $<.gets.chomp.chars.map {|a| (a == ".") ? "1" : "0"}.join.to_i(2) end max = 0 h.times do |i| result = field[i] (h - i).times do |j| result &= field[i + j] max_w = result.to_s(2).chars.chunk_while {|b, a| b == a and b == "1"} .select {|a| a.first == "1"}.map(&:size).max max_w ||= 0 s = max_w * (j + 1) max = s if s > max end end puts max end
時間オーバー。
def count(num) return 0 if num.zero? pl = Math.log2(num).to_i + 1 co = 0 max = 0 pl.times do if (num % 2).zero? co = 0 else co += 1 max = co if co > max end num /= 2 end max end until (a = $<.gets.split.map(&:to_i)) == [0, 0] h, w = a field = Array.new(h) do $<.gets.chomp.chars.map {|a| (a == ".") ? "1" : "0"}.join.to_i(2) end max = 0 h.times do |i| result = field[i] (h - i).times do |j| result &= field[i + j] max_w = count(result) s = max_w * (j + 1) max = s if s > max end end puts max end
これも時間オーバー。
メソッド count() をこう替えてみる。
def count(num, max = 0) return max if num.empty? num = num.drop_while {|e| e == "0"} l = num.take_while {|e| e == "1"}.size max = l if l > max count(num.drop_while {|e| e == "1"}, max) end
やはり時間オーバー。さらにメモ化をしてみても結果は同じ。根本的にアルゴリズムを変えないとダメだな。
他の人の答えを見る。
loop do h, w = $<.gets.split.map(&:to_i) break if h.zero? and w.zero? f = h.times.map { $<.gets.chomp } hseq = Array.new(h) {Array.new(w)} h.times.map do |y| hseq[y][0] = (f[y][0] == ".") ? 1 : 0 (1...w).each {|x| hseq[y][x] = (f[y][x] == ".") ? hseq[y][x - 1] + 1 : 0} end ans = 0 (w - 1).downto(0) do|x| h.times do |fy| tmp = w lim = h - fy (h - fy).times do |dy| tmp = [tmp, hseq[fy + dy][x]].min ans = [ans, tmp * (dy + 1)].max break if tmp * lim < ans end end end puts ans end
0117 A reward for a Carpenter
towns = Hash.new([]) n = $<.gets.to_i $<.gets.to_i.times do a, b, c, d = $<.gets.split(",").map(&:to_i) towns[a] += [[b, c]] towns[b] += [[a, d]] end s, g, v, p = $<.gets.split(",").map(&:to_i) travel = ->(start, goal) { minimum = Float::INFINITY walk = ->(town, visited, cost = 0) { if town == goal minimum = [minimum, cost].min else towns[town].each do |nxt, c| walk.(nxt, visited + [nxt], cost + c) unless visited.include?(nxt) end end } walk.(start, [start]) minimum } v -= travel.(s, g) v -= travel.(g, s) puts v - p
簡単なバックトラック法。
0118 Property Distribution
until (a = $<.gets.split.map(&:to_i)) == [0, 0] h, w = a field = Array.new(h) {$<.gets.chomp.chars} erase = ->(x, y, fruit) { stack = [[x, y]] while (a = stack.shift) x, y = a next if x < 0 or x >= w or y < 0 or y >= h next unless field[y][x] == fruit field[y][x] = "." [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| stack << [x + dx, y + dy] end end } num = 0 i = 0 loop do x, y = i % w, i / w i += 1 unless field[y][x] == "." erase.(x, y, field[y][x]) num += 1 end break if i >= w * h end puts num end
最初 erase.() を深さ優先探索でやっていて、どうしても Runtime Error が取れなかった。これは幅優先探索じゃないとダメなのかな。よくわからない。
0119 Taro's Obsession
table = Hash.new([]) m = $<.gets.to_i $<.gets.to_i.times do x, y = $<.gets.split.map(&:to_i) table[x] += [y] end check = ->(order) { order.map.with_index do |person, i| table[person].map {|b| i < order.index(b)}.all? end.all? } solve = ->(n, order) { if order.size == m if check.(order) puts order exit end else a = table[n] ([*1..m] - order - (a ? a : [])).each do |prev| solve.(prev, [prev] + order) end end } solve.(2, [2])
10問中 5問で時間オーバー。
table = Hash.new([]) m = io.gets.to_i io.gets.to_i.times do x, y = io.gets.split.map(&:to_i) table[y] += [x] end check = ->(order) { table.map do |k, v| v.map {|prev| order.index(prev) < order.index(k)}.all? end.all? } solve = ->(person, order) { if order.size == m if check.(order) puts order exit end else table[person].each do |prev| solve.(prev, [prev] + order) unless order.include?(prev) end ([*1..m] - table[person] - order).each do |prev| solve.(prev, [prev] + order) unless order.include?(prev) end end } solve.(2, [2])
10問中 4問で時間オーバー。どうもバックトラック法では無理だな。
他の人の回答を見た。
m = $<.gets.to_i n = $<.gets.to_i e = Array.new(m + 1) {[]} n.times do x, y = $<.gets.split.map(&:to_i) e[x] << y #後にあるのを入れている end r = [2] while r.size < m 1.upto(m) do |i| next if r.include?(i) catch(:a) do e[i].each do |j| throw(:a) unless r.include?(j) end r << i end end end puts r.reverse
なるほどー、後にあるのが確実になってから入れるのかあ。すごいなあ。
SSD の寿命を Linux で判断する
SSD(Intel X25-M)で寿命を確認するには at nkjmkzk.net
$ sudo smartctl -i /dev/sdc -d sat -a
smartctl 6.6 2016-05-31 r4324 [x86_64-linux-4.18.0-13-generic] (local build)
Copyright (C) 2002-16, Bruce Allen, Christian Franke, www.smartmontools.org
=== START OF INFORMATION SECTION ===
Device Model: SATA SSD
Serial Number: D61E076A1D2203758638
LU WWN Device Id: 5 000000 000000000
Firmware Version: SBFM10.6
User Capacity: 240,057,409,536 bytes [240 GB]
Sector Size: 512 bytes logical/physical
Rotation Rate: Solid State Device
Form Factor: < 1.8 inches
Device is: Not in smartctl database [for details use: -P showall]
ATA Version is: Unknown(0x0ff8) (minor revision not indicated)
SATA Version is: SATA 3.2, 6.0 Gb/s (current: 6.0 Gb/s)
Local Time is: Tue Jan 29 00:20:22 2019 JST
SMART support is: Available - device has SMART capability.
SMART support is: Enabled
=== START OF READ SMART DATA SECTION ===
SMART overall-health self-assessment test result: PASSED
General SMART Values:
Offline data collection status: (0x00) Offline data collection activity
was never started.
Auto Offline Data Collection: Disabled.
Self-test execution status: ( 0) The previous self-test routine completed
without error or no self-test has ever
been run.
Total time to complete Offline
data collection: (65535) seconds.
Offline data collection
capabilities: (0x79) SMART execute Offline immediate.
No Auto Offline data collection support.
Suspend Offline collection upon new
command.
Offline surface scan supported.
Self-test supported.
Conveyance Self-test supported.
Selective Self-test supported.
SMART capabilities: (0x0003) Saves SMART data before entering
power-saving mode.
Supports SMART auto save timer.
Error logging capability: (0x01) Error logging supported.
General Purpose Logging supported.
Short self-test routine
recommended polling time: ( 4) minutes.
Extended self-test routine
recommended polling time: ( 32) minutes.
Conveyance self-test routine
recommended polling time: ( 8) minutes.
SMART Attributes Data Structure revision number: 16
Vendor Specific SMART Attributes with Thresholds:
ID# ATTRIBUTE_NAME FLAG VALUE WORST THRESH TYPE UPDATED WHEN_FAILED RAW_VALUE
1 Raw_Read_Error_Rate 0x000b 100 100 050 Pre-fail Always - 0
9 Power_On_Hours 0x0012 100 100 000 Old_age Always - 6907
12 Power_Cycle_Count 0x0012 100 100 000 Old_age Always - 4379
168 Unknown_Attribute 0x0012 100 100 000 Old_age Always - 0
170 Unknown_Attribute 0x0003 093 093 010 Pre-fail Always - 180
173 Unknown_Attribute 0x0012 100 100 000 Old_age Always - 2490448
192 Power-Off_Retract_Count 0x0012 100 100 000 Old_age Always - 1372
194 Temperature_Celsius 0x0023 067 067 000 Pre-fail Always - 33 (Min/Max 33/33)
218 Unknown_Attribute 0x000b 100 100 050 Pre-fail Always - 0
231 Temperature_Celsius 0x0013 100 100 000 Pre-fail Always - 96
241 Total_LBAs_Written 0x0012 100 100 000 Old_age Always - 7107
SMART Error Log Version: 1
No Errors Logged
SMART Self-test log structure revision number 1
No self-tests have been logged. [To run self-tests, use: smartctl -t]
SMART Selective self-test log data structure revision number 0
Note: revision number not 1 implies that no selective self-test has ever been run
SPAN MIN_LBA MAX_LBA CURRENT_TEST_STATUS
1 0 0 Not_testing
2 0 0 Not_testing
3 0 0 Not_testing
4 0 0 Not_testing
5 0 0 Not_testing
Selective self-test flags (0x0):
After scanning selected spans, do NOT read-scan remainder of disk.
If Selective self-test is pending on power-up, resume after 0 minute delay.上の情報をどう読み取ればよいかわからなかったので、Windows 7 に CrystalDiskInfo をインストールして調べてみた。
「Crystal Disk Info」で、SSDの健康状態を把握しよう！ ｜ SSD徹底解説！
ただ、Wndows では ext4 が読み取れないので、下を参考に Ext2Fsd をインストールする。
ext4のパーティションをWindowsで読み書きする方法 | Linux Fan
以上の結果、下のように診断されました。
結果としては、Linux で smartctl を使ったのと同じ情報だが、なるほどこれはわかりやすい。
まだこの SSD は大丈夫みたいです。（2019/1/29）
AOJ（問題集）11
AIZU ONLINE JUDGE: Programming Challenge
0100 Sale Result
問題が曖昧。同じ社員が二度出てくるかどうかはっきりしない。
Border = 1_000_000 until (n = $<.gets.to_i).zero? data = Hash.new(0) entry = [] n.times do e, p, q = $<.gets.split.map(&:to_i) data[e] += p * q entry << e if data[e] >= Border end puts entry.empty? ? "NA" : entry.uniq end
0101 Aizu PR
$<.gets.to_i.times do text = $<.gets.chomp result = "" po = 0 while result.size < text.size if text[po, 7] == "Hoshino" result += "Hoshina" po += 7 else result += text[po] po += 1 end end puts result end
0102 Matrix-like Computation
until (n = $<.gets.to_i).zero? table = n.times.map do l = $<.gets.split.map(&:to_i) l + [l.sum] end last = (n + 1).times.map do |i| n.times.map {|j| table[j][i]}.sum end puts (table + [last]).map {|l| l.map {|i| sprintf("%5d", i)}.join } end
簡単な問題でも [提出] のボタンを押すときはドキドキするな。
0103 Baseball Simulation
$<.gets.to_i.times do bases = [0, 0, 0] out_count = 0 points = 0 while out_count < 3 case $<.gets.chomp when "OUT" out_count += 1 puts points if out_count >= 3 when "HIT" bases << 1 points += bases.shift when "HOMERUN" points += bases.sum + 1 bases = [0, 0, 0] else raise "error" end end end
0104 Magical Tiles
ひさしぶりにやる。
until (a = $<.gets.split.map(&:to_i)) == [0, 0] h, w = a tiles = h.times.map {$<.gets.chomp} positions = [0] x, y = 0, 0 result = loop do case tiles[y][x] when ">" then x += 1 when "<" then x -= 1 when "^" then y -= 1 when "v" then y += 1 when "." then break "#{x} #{y}" else raise "error" end po = y * w + x break "LOOP" if positions.include?(po) positions << po end puts result end
簡単だけれどドキドキするな。
0105 Book Index
index = Hash.new([]) $<.readlines.map do |l| a = l.chomp.split [a.first, a.last.to_i] end.each {|word, page| index[word] += [page]} index.keys.sort.each {|k| puts k, index[k].sort.join(" ")}
0106 Discounts of Buckwheat
table = [[200, 380, 5, 0.8], [300, 550, 4, 0.85], [500, 850, 3, 0.88]] A, B, C = table.map(&:first) calc = ->(shop, num) { t = table[shop] discount = (num / t[2]) * t[2] discount * t[1] * t[3] + (num - discount) * t[1] } until (soba = $<.gets.to_i).zero? min = Float::INFINITY (0..soba / C).each do |c| pay = calc.(2, c) soba1 = soba - c * C (0..soba1 / B).each do |b| pay1 = pay + calc.(1, b) soba2 = soba1 - b * B next if (soba2 % A).nonzero? pay2 = pay1 + calc.(0, soba2 / A) min = pay2 if pay2 < min end end puts min.to_i end
再帰で解いた方がよかったかな。ごちゃごちゃしたコードだ。
0107 Carry a Cheese
until (a = $<.gets.split.map(&:to_i)) == [0, 0, 0] $<.gets.to_i.times.map {$<.gets.to_i}.each do |r| result = a.combination(2).map do |w, h| Math.sqrt((w / 2.0) ** 2 + (h / 2.0) ** 2) < r end.any? puts result ? "OK" : "NA" end end
0108 Operation of Frequency of Appearance
def operation(ary, prev = [], i = 0) return i - 1, ary if ary == prev count = Hash.new(0) ary.each {|x| count[x] += 1} operation(ary.map {|x| count[x]}, ary, i + 1) end until $<.gets.to_i.zero? i, ary = operation($<.gets.split.map(&:to_i)) puts i, ary.join(" ") end
0109 Smart Calculator
$<.gets.to_i.times do splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/) output = [] stack = [] a = nil until (token = splited.shift) == ["="] token = token.first case token when "(" then stack << token when ")" then output << a until (a = stack.pop) == "(" when "*", "/" loop do a = stack.last break unless %w(* /).include?(a) output << stack.pop end stack << token when "+", "-" loop do a = stack.last break unless %w(+ - * /).include?(a) output << stack.pop end stack << token else output << token end end output << a while (a = stack.pop) stack = [] while (x = output.shift) if %w(+ - * /).include?(x) a, b = stack.pop, stack.pop stack << eval("#{b} #{x} #{a}").to_i else stack << x end end puts stack.first end
何がいけないのかわからない。
どうしてもわからないので他人の回答を見た。喰らった…。
$<.gets.to_i.times do splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/) a = nil # パーサー（逆ポーランド記法に変換） output = [] stack = [] until (token = splited.shift) == ["="] token = token.first case token when "(" then stack << token when ")" then output << a until (a = stack.pop) == "(" when "*", "/" loop do a = stack.last break unless %w(* /).include?(a) output << stack.pop end stack << token when "+", "-" loop do a = stack.last break unless %w(+ - * /).include?(a) output << stack.pop end stack << token else output << token.to_r end end output << a while (a = stack.pop) # 逆ポーランド記法を処理 stack = [] while (x = output.shift) if %w(+ - * /).include?(x) a, b = stack.pop, stack.pop if x == "/" and ((a < 0) ^ (b < 0)) stack << -(b.abs / a.abs) else stack << eval("#{b.to_i} #{x} #{a.to_i}").to_i end else stack << x end end puts stack.first.to_i end
これを見てほしい。
$ pry [1] pry(main)> -3/2 => -2
マジか！ -1 ではないのか！
div はメソッド / を呼びだし、floorを取ることで計算されます。
class Numeric (Ruby 2.5.0)
やられた。そういう Ruby の仕様なのね。勉強になりました。せっかくパーサー（操車場アルゴリズム）まで書いて頑張ったのに…。なお、皆さん演算子の再定義でやっておられる。自分もそれは考えたが、それではつまらん。
