AOJ（問題集）14

AOJ Ruby

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

正規表現を使うのはめずらしい。