AOJ（問題集）20

AIZU ONLINE JUDGE: Programming Challenge
　

0190 Eleven Puzzle

素直に幅優先探索を実行して死んだので、ここを参考に解いた。「両側探索」というらしい。

start = "fff0fff" "ff123ff" "f45678f" "ff9abff" "fff0fff"
result1 = {}
result1[start] = 0
stack = [start]

# 一方からの探索
while (nxt = stack.shift)
  next if result1[nxt] >= 10
  doit1 = ->(idx) {
    [1, -1, 7, -7].each do |di|
      next_index = idx + di
      next if next_index < 0 or next_index >= 35
      next if (c = nxt[next_index]) == "f" or c == "0"
      next_field = nxt.dup
      next_field[idx] = c
      next_field[next_index] = "0"
      next if result1[next_field]
      result1[next_field] = result1[nxt] + 1
      stack << next_field
    end
  }
  doit1.(nxt.index("0"))
  doit1.(nxt.rindex("0"))
end

# 反対側からの探索
pat = Array.new(5)
until (pat[0] = gets.to_i) == -1
  pat[0] = pat[0].to_s(16).center(7, "f")
  4.times {|i| pat[i + 1] = gets.split.map {|a| a.to_i.to_s(16)}.join.center(7, "f") }
  
  if (ans = result1[start = pat.join])
    puts ans
    next
  end
  
  result2 = {}
  result2[start] = 0
  stack = [start]
  str = "NA"
  f = true
  
  while (nxt = stack.shift) and f
    next if result2[nxt] >= 10
    doit2 = ->(idx) {
      [1, -1, 7, -7].each do |di|
        next_index = idx + di
        next if next_index < 0 or next_index >= 35
        next if (c = nxt[next_index]) == "f" or c == "0"
        next_field = nxt.dup
        next_field[idx] = c
        next_field[next_index] = "0"
        next if result2[next_field]
        if result1[next_field]
          str = (result1[next_field] + result2[nxt] + 1).to_s
          return false
        end
        result2[next_field] = result2[nxt] + 1
        stack << next_field
      end
      true
    }
    f = doit2.(nxt.index("0"))
    f = doit2.(nxt.rindex("0")) if f
  end
  puts str
end

0191 Baby Tree

until (given = gets.split.map(&:to_i)) == [0, 0]
  n, m = given
  g = n.times.map {gets.split.map(&:to_f)}
  memo = Array.new(101) {Array.new(101)}
  
  compost = ->(num, left) {
    return memo[num][left] if memo[num][left]
    memo[num][left] = if left.zero?
      1.0
    else
      n.times.map {|j| g[num][j] * compost.(j, left - 1)}.max
    end
  }
  printf "%.02f\n", n.times.map {|i| compost.(i, m - 1)}.max.round(2)
end

アホなミスをしていた。メモ化で値が存在するときに return を忘れているという…（笑）
　

0192 Multistory Parking Lot

class Car
  num = 1
  
  define_method(:initialize) do |waiting_time|
    @num = num
    num += 1
    @time = waiting_time
  end
  attr_reader   :num
  attr_accessor :time
  
  define_singleton_method(:clear) {num = 1}
end

class ParkingLot
  Space = Struct.new(:upper, :lower)
  
  def initialize(num)
    @spaces = num.times.map {|i| Space.new}
  end
  
  def add_car(waiting_time)
    idx = @spaces.index {|sp| sp.lower.nil?}
    if idx
      @spaces[idx].lower = Car.new(waiting_time)   #下のスペースが空いている
    else
      return false if @spaces.all?(&:upper)        #満車
      
      #下は空いていないが満車でない場合
      idxs = @spaces.map.with_index {|sp, i| i unless sp.upper}.compact
      idx = idxs.map do |i|
        diff = @spaces[i].lower.time - waiting_time
        diff >= 0 ? [diff, i] : nil
      end.compact.sort.first&.last
      unless idx
        idx = idxs.map {|i| [waiting_time - @spaces[i].lower.time, i]}.sort.first.last
      end
      
      @spaces[idx].upper = @spaces[idx].lower
      @spaces[idx].lower = Car.new(waiting_time)
    end
    true
  end
  
  def next
    @spaces.each do |sp|
      if sp.lower
        sp.lower.time -= 1
        sp.upper.time -= 1 if sp.upper
      end
    end
    
    out = []
    2.times do
      @spaces.each do |sp|
        if sp.lower and sp.lower.time <= 0
          out << sp.lower.num
          sp.lower = sp.upper
          sp.upper = nil
        end
      end
    end
    
    out
  end
  
  #車庫が空か
  def empty?
    @spaces.all? {|sp| sp.lower.nil?}
  end
end


until (given = gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  parking_time = n.times.map {gets.to_i}
  pl = ParkingLot.new(m)
  result = []
  wait = []
  Car.clear
  t = 0
  
  loop do
    result += pl.next
    
    wait << parking_time.shift if (t % 10).zero?
    t += 1
    while (wait_time = wait.shift)
      unless pl.add_car(wait_time)
        wait.unshift(wait_time)    #満車の場合
        break
      end
    end
    
    break if pl.empty?
  end
  
  puts result.join(" ")
end

だいぶ勘違いをしていた。Ruby では三人しか出来ていないですよ。
　

0194 Delivery Company

MaxTime = 100

Truck = Struct.new(:x, :y, :dir, :time)

def get_hv(str)
  h, v = str.split("-")
  [h.bytes.first - 97, v.to_i - 1]
end

def signal_wait(x, y, signals, next_dir, time)
  signal = false
  movable = true
  signals.each do |hv, k|
    if x == hv[1] && y == hv[0]
      signal = true
      if (i = time / k).odd?    #東西方向が青？
        movable = false if next_dir.odd?
      else
        movable = false if next_dir.even?
      end
    end
  end
  [movable, signal]
end

def under_construction?(stat, x, y, constructions)
  constructions.each do |hv1, hv2|
    return true if stat.x == hv1[1] && stat.y == hv1[0] && x == hv2[1] && y == hv2[0]
    return true if stat.x == hv2[1] && stat.y == hv2[0] && x == hv1[1] && y == hv1[0]
  end
  false
end

def add_holdup(stat, x, y, holdups)
  next_time = stat.time
  holdups.each do |hv1, hv2, d|
    f1 = (stat.x == hv1[1] && stat.y == hv1[0] && x == hv2[1] && y == hv2[0])
    f2 = (stat.x == hv2[1] && stat.y == hv2[0] && x == hv1[1] && y == hv1[0])
    next_time += d if f1 || f2
  end
  next_time
end


until (mn = gets.split.map(&:to_i)) == [0, 0]
  d0 = gets.to_i
  signals = gets.to_i.times.map do
    hv, k = gets.chomp.split
    [get_hv(hv), k.to_i]
  end
  constructions = gets.to_i.times.map do
    hv1, hv2 = gets.chomp.split
    [get_hv(hv1), get_hv(hv2)]
  end
  holdups = gets.to_i.times.map do
    hv1, hv2, d = gets.chomp.split
    [get_hv(hv1), get_hv(hv2), d.to_i]
  end
  start, goal = gets.split.map {|hv| get_hv(hv)}
  field = Array.new(mn[0]) {Array.new(mn[1])}
  queue = [Truck.new(start[1], start[0], 0, 0)]
  field[start[0]][start[1]] = queue.first
  min_time = Float::INFINITY
  
  go = ->(stat, dir) {
    next_dir = (stat.dir + dir) % 4
    dx, dy = [[1, 0], [0, -1], [-1, 0], [0, 1]][next_dir]
    x = stat.x + dx
    y = stat.y + dy
    return [] if x < 0 || x >= mn[1] || y < 0 || y >= mn[0]
    
    return [] if under_construction?(stat, x, y, constructions)
    next_time = d0 + add_holdup(stat, x, y, holdups)
    movable, signal = signal_wait(x, y, signals, next_dir, next_time)
    return [] unless movable
    
    return [] if next_time > MaxTime
    
    next_stat = Truck.new(x, y, next_dir, next_time)
    tmp = field[y][x]
    
    return [next_stat] if signal
    if tmp
      return [] if tmp.time <= next_time
    end
    [field[y][x] = next_stat]
  }
  
  while (now = queue.shift)
    if now.x == goal[1] && now.y == goal[0]
      min_time = now.time if min_time > now.time
    else
      queue += go.(now, 0)
      queue += go.(now, 1)
      queue += go.(now, -1)
    end
  end
  
  puts min_time
end

10秒で時間オーバー。
　

0195 What is the Most Popular Shop in Tokaichi?

Shop = "ABCDE"
N = Shop.length

until (data = [gets.chomp]) == ["0 0"]
  data.concat (N - 1).times.map {gets}
  result = data.map.with_index {|d, i| [d.split.map(&:to_i).sum, i]}.sort.last
  puts "#{Shop[result[1]]} #{result[0]}"
end

0196 Baseball Championship

until (n = gets.to_i).zero?
  data = n.times.map {gets.chomp.split}
  scores = data.map {|n, *r| [n, r.count("0"), r.count("1")]}
               .sort {|a, b| (b[1] <=> a[1]).nonzero? || a[2] <=> b[2]}
  puts scores.map(&:first)
end

複数キーのソート。
　

0197 Greatest Common Divisor: Euclidean Algorithm

until (given = gets.chomp) == "0 0"
  x, y = given.split.map(&:to_i)
  x, y = y, x if x < y
  count = 0
  until y.zero?
    x = x % y
    x, y = y, x
    count += 1
  end
  puts "#{x} #{count}"
end

0198 Trouble in Shinagawa's Artifacts

table = [[0, 1, 2, 3, 4, 5], [3, 1, 0, 5, 4, 2], [1, 5, 2, 3, 0, 4],
         [4, 0, 2, 3, 5, 1], [2, 1, 5, 0, 4, 3], [0, 2, 4, 1, 3, 5],
         [0, 3, 1, 4, 2, 5], [5, 1, 3, 2, 4, 0], [1, 2, 0, 5, 3, 4],
         [4, 3, 0, 5, 2, 1], [3, 0, 4, 1, 5, 2], [3, 5, 1, 4, 0, 2],
         [5, 4, 2, 3, 1, 0], [2, 5, 4, 1, 0, 3], [1, 3, 5, 0, 2, 4],
         [2, 0, 1, 4, 5, 3], [4, 2, 5, 0, 3, 1], [0, 4, 3, 2, 1, 5],
         [1, 0, 3, 2, 5, 4], [4, 5, 3, 2, 0, 1], [5, 3, 4, 1, 2, 0],
         [5, 2, 1, 4, 3, 0], [2, 4, 0, 5, 1, 3], [3, 4, 5, 0, 1, 2]]
color_table = %w(Red Yellow Blue Magenta Green Cyan).map
                .with_index {|c, i| [c, i]}.to_h

until (n = gets.to_i).zero?
  dices = n.times.map { gets.split.map {|c_name| color_table[c_name]} }
  pool = []
  count = 0
  
  dices.each do |color|
    check_f = true
    table.each do |t|
      next_dice = t.map {|idx| color[idx]}
      if pool.include?(next_dice)
        count += 1 if check_f
        check_f = false
      else
        pool << next_dice
      end
    end
  end
  
  puts count
end

0199 Chairs Where Demanding People Sit

def a(seats)
  seats[seats.index("#")] = "A"
end

def b(seats, n)
  (n - 1).downto(0) do |i|
    if (i - 1 < 0 || seats[i - 1] != "A") && seats[i + 1] != "A" &&
        seats[i] == "#"
      seats[i] = "B"
      return
    end
  end
  seats[seats.index("#")] = "B"
end

def c(seats, n)
  if seats.count("#") == n
    idx = n / 2
  else
    n.times do |i|
      if seats[i] != "#"
        if seats[i + 1] == "#"
          idx = i + 1
          break
        elsif i - 1 >= 0 && seats[i - 1] == "#"
          idx = i - 1
          break
        end
      end
    end
  end
  seats[idx] = "C"
end

def d(seats, n)
  idx = 0
  if seats.count("#") != n
    max_dist = 0
    n.times do |i|
      d = nearest_dist(seats, i)
      if d > max_dist
        max_dist = d
        idx = i
      end    
    end
  end
  seats[idx] = "D"
end

def nearest_dist(seats, i)
  dist = 0
  dist += 1 until /[A-D]/ =~ seats[i + dist] ||
                  (i - dist >= 0 && /[A-D]/ =~ seats[i - dist])
  dist
end


until (given = gets.split.map(&:to_i)) == [0, 0]
  n, m = given
  seats = "#" * n
  m.times do
    case gets.chomp
    when "A" then a(seats)
    when "B" then b(seats, n)
    when "C" then c(seats, n)
    when "D" then d(seats, n)
    end
  end
  puts seats
end