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)

苦労して考えたにしてはあっさり正解。動的計画法。Ruby だといつもの常連さんしか出来ていない（笑）。
　

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

何だか冗長なコードになってしまった。