AOJ（問題集）22

0210 The Squares

むずかしかった。何とか自力で出来た。

Table = %W(E N W S)

Man = Struct.new(:x, :y, :dir, :next_x, :next_y) do
  def next
    dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][self.dir]
    self.next_x, self.next_y = self.x + dx, self.y + dy
  end
  
  def move(field)
    field[self.y][self.x] = "."
    self.x, self.y = self.next_x, self.next_y
    self.next
    if field[self.y][self.x] == "X"
      return [self, true]
    else
      field[self.y][self.x] = Table[self.dir]
      return [self, false]
    end
  end
  
  def turn(field)
    [-1, 0, 1, 2].each do |step|
      next_dir = (self.dir + step) % 4
      dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][next_dir]
      type = field[self.y + dy][self.x + dx]
      if type == "." || type == "X"
        self.dir = next_dir
        field[self.y][self.x] = Table[next_dir]
        self.next
        return
      end
    end
  end
end


def passage(persons, field)
  h = Hash.new([])
  persons.each do |man|
    next_type = field[man.next_y][man.next_x]
    next unless next_type == "." || next_type == "X"
    h[[man.next_x, man.next_y]] += [man]
  end
  h.values
end


loop do
  w, h = gets.split.map(&:to_i)
  break if (w + h).zero?
  
  field = h.times.map {gets.chomp.chars}
  
  persons = []
  field.each_with_index do |row, y|
    row.each_with_index do |po, x|
      idx = Table.index(po)
      persons << Man.new(x, y, idx) if idx
    end
  end
  persons.each(&:next)
  
  t = 1
  loop do
    persons.each {|man| man.turn(field)}
    
    passage(persons, field).each do |ary|
      man, flag = if ary.size == 1
        ary[0].move(field)
      else
        ary.sort_by {|man0| (man0.dir + 2) % 4}[0].move(field)
      end
      persons.delete(man) if flag
    end
    
    break if t > 180
    break if persons.empty?
    t += 1
  end
  
  puts (t > 180) ? "NA" : t
end

0211 Jogging

until (n = gets.to_i).zero?
  data = n.times.map {gets.split.map(&:to_i)}.map {|a, b| Rational(a, b)}
  lcm = data.map(&:denominator).inject(:lcm)
  nums = data.map {|d| Rational(1, d * lcm)}
  
  lcm = nums.map(&:denominator).inject(:lcm)
  puts nums.map {|n| (n * lcm).to_i}
end

だいぶ考えた。しかし Ruby は大きい整数を扱うのがラクなので、そんなにむずかしくない。
　

0212 Highway Express Bus

require "set"

INF = (1 << 31) - 1
TownMax = 100

until (given = gets.chomp) == "0 0 0 0 0"
  c, n, m, s, d = given.split.map(&:to_i)
  s -= 1
  d -= 1
  data = m.times.map {gets.split.map(&:to_i)}
  
  fares = Array.new(n) {[]}
  route_map = Array.new(n, [])
  towns = Set.new
  
  data.each do |a, b, f|
    a -= 1
    b -= 1
    route_map[a] += [b]
    route_map[b] += [a]
    fares[a][b] = fares[b][a] = f
    towns << a
    towns << b
  end
  
  shortest = Array.new(c + 1) {Array.new(TownMax, INF)}
  done = Array.new(c + 1) {Array.new(TownMax, false)}
  
  shortest[0][s] = 0
  
  loop do
    u0 = u1 = nil
    (c + 1).times do |ticket|
      towns.each do |town|
        next if done[ticket][town]
        if !u0 or shortest[ticket][town] < shortest[u0][u1]
          u0, u1 = ticket, town
        end
      end
    end
    break unless u0
    done[u0][u1] = true
    
    route_map[u1].each do |to|
      if (a0 = shortest[u0][u1] + fares[u1][to]) < shortest[u0][to]
        shortest[u0][to] = a0
      end
      if u0 + 1 <= c
        if (a1 = shortest[u0][u1] + fares[u1][to] / 2) < shortest[u0 + 1][to]
          shortest[u0 + 1][to] = a1
        end
      end
    end
  end
  
  puts shortest.map {|a| a[d]}.min
end

拡張ダイクストラ法だって。わけがわからない。ここを参考にした。
これが圧倒的に速い。たぶん単純なバックトラック。うーむ。
　

0213 Subdivide The Land

バックトラック法なのだけれど、時間オーバー。頑張って実装したのだけれどなあ。

class Field
  def initialize(width, height)
    @w, @h = width, height
    @field = Array.new(height) {Array.new(width, 0)}
  end
  
  def write(x, y, width, height, num, delete = false)
    tmp = @field.dup.map {|row| row.dup}
    height.times do |i|
      yy = y + i
      return false if yy < 0 || yy >= @h
      width.times do |j|
        xx = x + j
        return false if xx < 0 || xx >= @w
        type = tmp[yy][xx]
        return false if type.nonzero? && !delete
        tmp[yy][xx] = num
        tmp
      end
    end
    @field = tmp
    true
  end
  
  def to_s
    @field.map {|row| row.join(" ")}
  end
end

def search(field_area)
  (1..Math.sqrt(field_area).to_i).each do |i|
    n0 = field_area % i
    if n0.zero?
      yield(i, n = field_area / i)
      yield(n, i) if i != n
    end
  end
end


until (xyn = gets.chomp) == "0 0 0"
  x, y, n = xyn.split.map(&:to_i)
  field_areas = n.times.map {gets.split.map(&:to_i)}.sort.map(&:last)
  init_field = y.times.map {gets.split.map(&:to_i)}
    
  if field_areas.sum != x * y
    puts "NA"
    exit
  end
  
  field_num = Array.new(n)
  init_field.each_with_index do |row, y0|
    row.each_with_index do |num, x0|
      field_num[num - 1] = [x0, y0] if num.nonzero?
    end
  end
  
  field = Field.new(x, y)
  result = nil
  
  try = ->(customer){
    if customer == n
      if result
        result = "NA"
        false
      else
        result = field.to_s
        true
      end
    else
      search(field_areas[customer]) do |width, height|
        x0, y0 = field_num[customer]
        height.times do |dy|
          width.times do |dx|
            f = field.write(x0 - dx, y0 - dy, width, height, customer + 1)
            next unless f
            return false unless try.(customer + 1)
            field.write(x0 - dx, y0 - dy, width, height, 0, true)
          end
        end
      end
      true
    end
  }
  try.(0)
  
  result = "NA" unless result
  puts result
end

0216 Cutting Down Water Bills

while (w = gets.to_i) >= 0
  water_rate = case
               when w <= 10 then 1150
               when w <= 20 then 1150 + 125 * (w - 10)
               when w <= 30 then 2400 + 140 * (w - 20)
               else 3800 + 160 * (w - 30)
               end
  puts 4280 - water_rate
end

0217 Walking in the Hospital

until (n = gets.to_i).zero?
  result = n.times.map {gets.split.map(&:to_i)}
            .map {|p, d1, d2| [p, d1 + d2]}
            .max {|a, b| a[1] <=> b[1]}
  puts result.join(" ")
end

0218 Dividing Students

until (n = gets.to_i).zero?
  n.times.map {gets.split.map(&:to_i)}.each do |m, e, j|
    math_eng_av = (m + e) / 2.0
    three_av = (m + e + j) / 3.0
  
    klass = case
            when [m, e, j].include?(100) then :A
            when math_eng_av >= 90 then :A
            when three_av >= 80 then :A
            when three_av >= 70 then :B
            when three_av >= 50 && [m, e].max >= 80 then :B
            else :C
            end
    puts klass
  end
end

0219 A Popular Ice-cream Shop

ICE = 10

until (n = gets.to_i).zero?
  count = Array.new(ICE, 0)
  n.times.map {gets.to_i}.each {|type| count[type] += 1}
  
  puts count.map {|num| num.zero? ? "-" : "*" * num}
end