AOJ（問題集）21
0200 Traveling Alone: One-way Ticket of Youth
until (given = gets.split.map(&:to_i)) == [0, 0] n, m = given edge = Array.new(m) {[]} h = Array.new(m) {[]} n.times do a, b, cost, time = gets.split.map(&:to_i) a -= 1 b -= 1 edge[a][b] = edge[b][a] = [cost, time] h[a] << b h[b] << a end gets.to_i.times do p, q, r = gets.split.map(&:to_i) p -= 1 q -= 1 shortest = Array.new(m, Float::INFINITY) done = m.times.map(&:itself) shortest[p] = 0 until done.empty? u = done.min {|a, b| shortest[a] <=> shortest[b]} done.delete(u) h[u].each do |v| if (a = shortest[u] + edge[u][v][r]) < shortest[v] shortest[v] = a end end end puts shortest[q] end end
ダイクストラ法なのだが、他の人の回答を見て徹底的に高速化する。これで 3.30秒。
0201 Wrought Gold Master
until (n = gets.to_i).zero? costs = n.times.map { gets.split.tap {|a| a[1] = a[1].to_i} }.to_h m = gets.to_i recipe = Hash.new {|hash, key| hash[key] = []} m.times do given = gets.split recipe[given[0]] += given[2..-1] end goal = gets.chomp try = ->(parent) { r = recipe[parent] c = costs[parent] if r.empty? c else made = r.map {|child| try.(child)}.sum [made, c].min end } puts try.(goal) end
0202 At Boss's Expense
require "prime" until (given = io.gets.split.map(&:to_i)) == [0, 0] dishes = given[0].times.map {io.gets.to_i} result = 0 dp = Array.new(given[1] + 1, false) dp[0] = true (1..given[1]).each do |i| dishes.each do |price| if i >= price && dp[i - price] dp[i] = true break end end result = i if dp[i] && i.prime? end puts result.zero? ? "NA" : result end
時間オーバー。これは Ruby ではかなり無理っぽい。出来ている人は一人しかいない。
0203 A New Plan of Aizu Ski Resort
loop do w, h = gets.split.map(&:to_i) break if w + h == 0 field = h.times.map {gets.split.map(&:to_i)} dp = Array.new(h) {Array.new(w, 0)} w.times {|x| dp[h - 1][x] = 1 if field[h - 1][x] != 1} (h - 2).downto(0) do |y| w.times do |x| case field[y][x] when 2 if y + 2 == h dp[y][x] = 1 else dp[y][x] = dp[y + 2][x] end when 0 s = 0 [-1, 0, 1].each do |dx| x1 = x + dx next if x1 < 0 || x1 == w next if dx.nonzero? && field[y + 1][x1] == 2 s += dp[y + 1][x1] end dp[y][x] = s end end end puts dp[0].sum end
0204 UFO Shooting Down Operation
class Ufo def initialize(x, y, r, v) @dist = Math.sqrt(x ** 2 + y ** 2) @x = x @y = y @r = r @v = v @ex = x / @dist @ey = y / @dist @vx = -v * @ex @vy = -v * @ey end attr_reader :x, :y, :r, :dist, :ex, :ey def move @dist -= @v @x += @vx @y += @vy end end loop do radius, n = gets.split.map(&:to_i) break if (radius + n).zero? ufos = n.times.map {Ufo.new(*gets.split.map(&:to_i))} count = 0 loop do ufos.each(&:move) ufos.sort_by! {|u| u.dist} ufos1 = ufos.select {|u| u.dist <= radius} count += ufos1.size ufos -= ufos1 break if ufos.size.zero? min = ufos.shift ufos = ufos.reject do |u| r = (min.y * u.x - min.x * u.y).abs / min.dist r < u.r && u.dist * (min.ex * u.ex + min.ey * u.ey) + Math.sqrt(u.r ** 2 - r ** 2) > radius end break if ufos.size.zero? end puts count end
これむずかしすぎでしょう。検索して初めてわかった。
0205 Rock, Paper, Scissors
until (a = gets.to_i).zero? given = [a] + 4.times.map {gets.to_i} hands = given.uniq if hands.size == 3 || hands.size == 1 result = [3] * 5 else point = (hands[0] - hands[1]) % 3 == 2 ? 1 : 2 result = given.map do |hand| hand == hands[0] ? point : 3 - point end end puts result end
突然簡単に。
0206 Next Trip
until (l = gets.to_i).zero? data = 12.times.map {gets.split.map(&:to_i)} month_number = "NA" acc = 0 data.each_with_index do |mn, i| acc += mn[0] - mn[1] if acc >= l month_number = i + 1 break end end puts month_number end
簡単。
0207 Block
Position = Struct.new(:x, :y) loop do w, h = gets.split.map(&:to_i) break if (w + h).zero? field = Array.new(h + 1) {Array.new(w + 1, 0)} xs, ys = gets.split.map(&:to_i) xg, yg = gets.split.map(&:to_i) start = Position.new(xs, ys) gets.to_i.times do color, direction, x, y = gets.split.map(&:to_i) width, height = direction.zero? ? [4, 2] : [2, 4] height.times do |h1| width.times {|w1| field[y + h1][x + w1] = color} end end start_color = field[ys][xs] field[ys][xs] = 100 stack = [start] result = "NG" while (po = stack.shift) if po.x == xg && po.y == yg result = "OK" break else [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy| next_x, next_y = po.x + dx, po.y + dy next if next_x <= 0 || next_x > w || next_y <= 0 || next_y > h if field[next_y][next_x] == start_color stack << Position.new(next_x, next_y) field[next_y][next_x] = 100 end end end end puts result end
幅優先探索。簡単。
0208 Room Numbers of a Hospital
Table = [0, 1, 2, 3, 3, 4 ,4, 5, 6, 7] def func(num) num1 = num.to_s.chars result = 0 loop do top = num1.shift.to_i digits = num1.size result += Table[top] * 8 ** digits break if digits.zero? end result end until (num = gets.to_i).zero? puts (1..9358757000).bsearch {|i| num <= func(i)} end
何かダメ。検索してみる。
Table = [0, 1, 2, 3, 5, 7, 8, 9] def f(n) f(n / 8) if n >= 8 print Table[n % 8] end until (num = gets.to_i).zero? f(num) puts end
世の中にはかしこい人がいますな。
0209 Scene in a Picture
loop do n, m = gets.split.map(&:to_i) break if (n + m).zero? scene = n.times.map {gets.split.map(&:to_i)} picture = m.times.map {gets.split.map(&:to_i)} pictures = [] 4.times do pictures << picture picture = picture.reverse.transpose #右回転 end check = ->{ result = [] (0..n - m).each do |y| (0..n - m).each do |x| pictures.each do |pic| catch :jump { nx = ny = nil m.times do |dy| m.times do |dx| next if pic[dy][dx] == -1 nx, ny = x + dx, y + dy unless nx throw :jump if pic[dy][dx] != scene[y + dy][x + dx] end end result << [nx + 1, ny + 1] } end end return result unless result.empty? end "NA" } result = check.() if result != "NA" result = result.sort! {|a, b| (a[1] <=> b[1]).nonzero? || a[0] <=> b[0]}[0].join(" ") end puts result end
凡庸なコード。でも Ruby では三人しか出来ていないね。
