AOJ（問題集）8 - Marginalia

AIZU ONLINE JUDGE: Programming Challenge
　

0071 Bombs Chain

$<.gets.to_i.times do |co|
  $<.gets
  field = Array.new(8) {$<.gets.chomp.chars.map(&:to_i)}
  xi, yi = $<.gets.to_i, $<.gets.to_i
  
  blast = ->(x, y) {
    field[y][x] = 2
    3.times do |i|
      [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
        x1, y1 = x + dx * (i + 1), y + dy * (i + 1)
        next if x1 < 0 or x1 >= 8 or y1 < 0 or y1 >= 8
        if field[y1][x1] == 1
          blast.(x1, y1)
        else
          field[y1][x1] = 2
        end
      end
    end
  }
  blast.(xi - 1, yi - 1)
  
  puts "Data #{co + 1}:"
  puts field.map {|line| line.map {|a| a == 2 ? 0 : a}.join}
end

0072 Carden Lantern

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}
  table.map! {|a, b, d| [a, b, d / 100 - 1]}
  
  min = Float::INFINITY
  (1..m).each do |i|
    table.combination(i) do |paths|
      next unless paths.inject([]) {|a, path| a + path[0, 2]}.uniq.sort == [*0...n]
      n = paths.map{|path| path.last}.sum
      min = n if n < min
    end
  end
  puts min
end

まずはこれで解ける筈だが、時間オーバー。そりゃそうだ。
ふと、動的計画法で解けることに気がつく。これはよいアイデア。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  field = []
  Array.new(m) {$<.gets.split(",").map(&:to_i)}.each do |a, b, d|
    n = d / 100 - 1
    field += field.map {|spots, num| [(spots + [a, b]).uniq, num + n]}
    field << [[a, b], n]
  end
  puts field.select {|x| x.first.size == n}.sort_by {|x| x.last}.first.last
end

しかしメモリオーバー。ならばと訪れた史跡のチェックをビット演算でおこない、さらに配列の代わりにハッシュを使って省メモリ化。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  field = {0=>0}
  Array.new(m) {$<.gets.split(",").map(&:to_i)}.each do |a, b, d|
    n = d / 100 - 1
    added = {}
    field.each do |spots, num|
      spots |= 2 ** a
      spots |= 2 ** b
      added[spots] = num + n if !added[spots] or num + n < added[spots]
    end
    field.merge!(added) {|spots, b, f| [b, f].min}
  end
  puts field[2 ** n - 1]
end

それでもメモリオーバー。うーん。いきづまった。
まったく別の考え方で。後戻りも含めて幅優先探索し、適当なところで打ち切る。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  cpd = Hash.new([])
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}
  table.map! {|a, b, d| [a, b, d / 100 - 1]}
  table.each_with_index do |x, i|
    cpd[x[0]] += [i]
    cpd[x[1]] += [i]
  end
  stack = [[0, 1, 0, 0]]    # 現在位置、行った場所、灯籠の数、使った道
  result = loop do
    nxt = stack.shift
    cpd[nxt[0]]
    .map {|tn| [tn, (table[tn][0, 2] - [nxt[0]]).first, table[tn].last]}
    .each do |tn, spot, n|
      nxt_lnt = nxt[2]
      nxt_lnt += n if (2 ** spot & nxt[1]).zero?
      stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** tn | nxt[3]]
    end
    tmp1 = stack.select {|x| x[1] == 2 ** n - 1}
    tmp2 = tmp1 .select {|x| x[3] == 2 ** m - 1}
    break tmp1 unless tmp2.empty?
  end
  puts result.map {|x| x[2]}.min
end

今度は時間オーバー。うーむ。
後戻りは一度しかできないとする。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  cpd = Hash.new([])
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}
  table.map! {|a, b, d| [a, b, d / 100 - 1]}
  table.each_with_index do |x, i|
    cpd[x[0]] += [i]
    cpd[x[1]] += [i]
  end
  result = []
  stack = [[0, 1, 0, 0, 0]]    # 現在位置、行った場所、灯籠の数、使った道、道は戻ったことがあるか
  while (nxt = stack.shift)
    if nxt[1] == 2 ** n - 1
      result << nxt[2]
    else
      cpd[nxt[0]]
      .map {|path| [path, (table[path][0, 2] - [nxt[0]]).first, table[path].last]}
      .each do |path, spot, n|
        next if (nxt[4] & 2 ** path).nonzero?    # 道を戻るのは一度だけ
        # 行った場所で使っていない道だとダメ
        next if (2 ** spot & nxt[1]).nonzero? and (2 ** path & nxt[3]).zero?
        nxt_lnt = nxt[2]
        nxt_lnt += n if (2 ** spot & nxt[1]).zero?
        f = nxt[4]
        f |= 2 ** path if (2 ** path & nxt[3]).nonzero?
        stack << [spot, 2 ** spot | nxt[1], nxt_lnt, 2 ** path | nxt[3], f]
      end
    end
  end
  puts result.min
end

今度も時間オーバー。うーん、ここまで考えたのだが。
またまったく別の方法。すべて足しておいて、削れるだけ削る。

until (n = $<.gets.to_i).zero?
  m = $<.gets.to_i
  init_spots = Array.new(m, 0)
  tourou = 0
  table = Array.new(m) {$<.gets.split(",").map(&:to_i)}.map do |a, b, d|
    init_spots[a] += 1
    init_spots[b] += 1
    n = d / 100 - 1
    tourou += n
    [a, b, n]
  end
  min = tourou
  solve = ->(i, spots, t) {
    min = t if t < min
    return if i == m
    solve.(i + 1, spots, t)
    now = table[i]
    return if spots[now[0]] == 1 or spots[now[1]] == 1
    spots[now[0]] -= 1
    spots[now[1]] -= 1
    solve.(i + 1, spots, t - now[2])
    spots[now[0]] += 1
    spots[now[1]] += 1
  }
  solve.(0, init_spots, tourou)
  puts min
end

これも時間オーバー。

他の人の回答（参照）。

until (n = $<.gets.chomp.to_i).zero?
  edges = []
  $<.gets.chomp.to_i.times do
    e = $<.gets.chomp.split(",").map(&:to_i)
    e[2] = e[2] / 100 - 1
    edges << e
  end
  #p [n, m, edges]
  
  #灯籠の数の少ない順に並べる
  edges.sort! {|a, b| a[2] <=> b[2]}
 
  nodes = Array.new(n, false)
 
  connected = [0]
  nodes[0] = true
 
  sumw = 0
 
  while connected.length < n
    (0...edges.length).each |i|
      n0, n1, w = edges[i]
 
      if nodes[n0] or nodes[n1]
        if !nodes[n0]
          nodes[n0] = true
          connected << n0
          sumw += w
        elsif !nodes[n1]
          nodes[n1] = true
          connected << n1
          sumw += w
        end
 
        edges.delete_at(i)
        break
      end
    end
  end
 
  puts sumw
end

なるほど、灯籠の少ない順にならべておいて、あとは史跡 0 から順に繋げていくと。なるほどなあー。
　

0073 Surface Area of Quadrangular Pyramid

loop do
  x, h = $<.gets.to_i, $<.gets.to_i
  break if x.zero? and h.zero?
  puts x * x + Math.sqrt(h * h + (x / 2.0) ** 2) * x * 2
end

0074 Videotape

loop do
  t, h, s = $<.gets.split.map(&:to_i)
  break if t == -1 and h == -1 and s == -1
  left = 120 * 60 - (t * 3600 + h * 60 + s)
  output = ->(t) {
    printf "%02d:%02d:%02d\n", h = t / 3600, (m = t / 60) - h * 60, t - m * 60
  }
  output.(left)
  output.(left * 3)
end

0075 BMI

$<.readlines.map {|l| l.split(",").map(&:to_f)}
  .select {|s, w, h| w / h ** 2 >= 25.0}.each {|a| puts a.first.to_i}

0076 Treasure Hunt II

until (n = $<.gets.to_i) == -1
  x, y = 1.0, 0.0
  (n - 1).times do
    l = Math.sqrt(x ** 2 + y ** 2)
    x, y = x - y / l, y + x / l
  end
  puts x, y
end

0077 Run Length

$<.readlines.map(&:chomp).each do |given|
  po = 0
  text = ""
  while po < given.length
    if given[po] == "@"
      text += given[po + 2] * given[po + 1].to_i
      po += 3
    else
      text += given[po]
      po += 1
    end
  end
  puts text
end

0078 Magic Square

until (n = $<.gets.to_i).zero?
  square = Array.new(n) {[0] * n}
  
  set = ->(i, x, y) {
    return if i > n * n
    if x < 0
      set.(i, n - 1, y)
    elsif x >= n
      set.(i, 0, y)
    elsif y >= n
      set.(i, x, 0)
    elsif square[y][x].nonzero?
      set.(i, x - 1, y + 1)
    else
      square[y][x] = i
      set.(i + 1, x + 1, y + 1)
    end
  }
  set.(1, n / 2, n / 2 + 1)
  
  square.each do |l|
    puts l.map {|x| sprintf("%4d", x)}.join
  end
end

0079 Area of Polygon

多角形の面積。

include Math

points = $<.readlines.map {|l| Complex(*l.split(",").map(&:to_f))}
start_po = p0 = points.sort_by(&:imaginary).last
prev_arg = PI
  
e = Enumerator.new do |y|
  loop do
    points -= [start_po]
    break if points.empty?
    selected = points.map {|po| [po - start_po, po]}
      .reject {|pos| pos.first == 0}
      .sort_by {|pos| a = pos.first.angle + PI - prev_arg; a >= 0 ? a : a + 2 * PI}
      .first.last
    y << selected
    prev_arg = (selected - start_po).angle + PI
    start_po = selected
  end
end

result = e.each_cons(2).map do |p1, p2|
  a = (p1 - p0).abs
  b = (p2 - p0).abs
  c = (p2 - p1).abs
  z = (a + b + c) / 2.0
  sqrt(z * (z - a) * (z - b) * (z - c))
end.sum
puts result

意外とむずかしくて、かなり大袈裟なことをしている。0068 の回答参照。
他の人の回答にはすごいのがあって、例えばどうしてこれで求まるのかわからない。
ああ、そうか、問題をよく読んでいなかったのか！　よくあるな、これ。点が順番に並んでいるのだ。じゃあ簡単だ…。

これでOK。

require 'matrix'

p0, *points = $<.readlines.map {|l| Vector[*l.split(",").map(&:to_f)]}
result = points.each_cons(2).map do |p1, p2|
  a = (p1 - p0).norm
  b = (p2 - p0).norm
  c = (p2 - p1).norm
  z = (a + b + c) / 2
  Math.sqrt(z * (z - a) * (z - b) * (z - c))
end.sum
puts result

前の回答だと、点の並びが任意でも計算できる。
　

0080 Third Root

until (q = $<.gets.to_f) == -1
  x = q / 2.0
  result = loop do
    x -= (x ** 3 - q) / (3 * x ** 2)
    break x if (x ** 3 - q).abs < 0.00001 * q
  end
  puts result
end