AOJ（問題集）12

AIZU ONLINE JUDGE: Programming Challenge
　

0110 Alphametic

$<.readlines.map(&:chomp).map {|l| l.split(/\+|=/)}.each do |given|
  catch(:jump) do
    10.times do |i|
      d = given.map {|a| a.gsub("X", i.to_s)}
      next unless d.select {|s| s.length >= 2 and s[0] == "0"}.empty?
      next unless d[0].to_i + d[1].to_i == d[2].to_i
      puts i
      throw(:jump)
    end
    puts "NA"
  end
end

0111 Doctor's Memorable Codes

table1 = {"'"=>"000000", ","=>"000011", "-"=>"10010001", "."=>"010001",
  "?"=>"000001", "A"=>"100101", "B"=>"10011010", "C"=>"0101", "D"=>"0001",
  "E"=>"110", "F"=>"01001", "G"=>"10011011", "H"=>"010000", "I"=>"0111",
  "J"=>"10011000", "K"=>"0110", "L"=>"00100", "M"=>"10011001",
  "N"=>"10011110", "O"=>"00101", "P"=>"111", "Q"=>"10011111", "R"=>"1000",
  "S"=>"00110", "T"=>"00111", "U"=>"10011100", "V"=>"10011101",
  "W"=>"000010", "X"=>"10010010", "Y"=>"10010011", "Z"=>"10010000", " "=>"101"}
table2 = {"00000"=>"A", "00001"=>"B", "00010"=>"C", "00011"=>"D", "00100"=>"E",
  "00101"=>"F", "00110"=>"G", "00111"=>"H", "01000"=>"I", "01001"=>"J",
  "01010"=>"K", "01011"=>"L", "01100"=>"M", "01101"=>"N", "01110"=>"O",
  "01111"=>"P", "10000"=>"Q", "10001"=>"R", "10010"=>"S", "10011"=>"T",
  "10100"=>"U", "10101"=>"V", "10110"=>"W", "10111"=>"X", "11000"=>"Y",
  "11001"=>"Z", "11010"=>" ", "11011"=>".", "11100"=>",", "11101"=>"-",
  "11110"=>"'", "11111"=>"?"}
table1 = table1.invert.sort_by {|a| a.first}
table2 = table2.invert

$<.readlines.map(&:chomp).each do |text|
  result = ""
  text.each_char {|c| result += table2[c]}
  
  convert = ->(txt, converted = "") {
    table1.each do |k, v|
      l = k.length
      converted = convert.(txt[l..-1], converted + v) if txt[0, l] == k
    end
    converted
  }
  puts convert.(result)
end

0112 A Milk Shop

until (num = $<.gets.to_i).zero?
  order = Array.new(num) {$<.gets.to_i}.sort[0..-2]
  each_wait = 0
  puts order.map {|t| each_wait += t}.sum
end

0113 Period

循環少数。

def calc(p, q)
  rems = []
  place = []
  begin
    rems  << p
    place << p * 10 / q
    p = p * 10 % q
    return place.join if p.zero?
  end until (idx = rems.find_index(p))
  result = (st = place.join) + "\n"
  result + " " * idx + "^" * (st.length - idx)
end

$<.readlines.map {|l| l.split.map(&:to_i)}.each do |p, q|
  puts calc(p % q, q)
end

循環少数についてはここで考えておいたのが役立った。
　

0114 Electro-Fly

until (a = $<.gets.split.map(&:to_i)) == [0] * 6
  po = [1, 1, 1]
  co = 0
  result = loop do
    po = a.each_slice(2).zip(po).map {|am, i| am[0] * i % am[1]}
    co += 1
    break co if po == [1, 1, 1]
  end
  puts result
end

これでは例題すらフリーズする。高速化を考えないといけない。
よく考えたらわかった。

def calc(a, m)
  i = 1
  1.step do |co|
    i = a * i % m
    return co if i == 1
  end
end

until (a = $<.gets.split.map(&:to_i)) == [0] * 6
  cx, cy, cz = a.each_slice(2).map {|a, m| calc(a, m)}
  puts cx.lcm(cy).lcm(cz)
end

0115 Starship UAZ Advance

宇宙船 UAZ アドバンス号の巻です（参照）。ビームが当たるかを行列演算で求めている。

require 'matrix'

myship, enemy, b1, b2, b3 = $<.readlines.map {|l| Vector[*l.split.map(&:to_r)]}
v = enemy - myship
va = b2 - b1
vb = b3 - b1
begin
  l, s, t = Matrix.columns([-v, va, vb]).lup.solve(myship - b1).to_a
rescue
  puts "HIT"
  exit
end

puts 0 < l && l <= 1 && (s + t).between?(0, 1) && s >= 0 && t >= 0 ? "MISS" : "HIT"

うおお、俺スゲーって感じ。というか、本当は Ruby の Matrix がすごい。
Ruby で解けたのはいまのところ 6人だけ。その中でも自分のは圧倒的にコードのバイト数が少ない。ひゅー。
しかしまあ、数学の問題としては別にむずかしいものではない。手作業では計算が面倒というだけ。そこがプログラミングだな。
　

0116 Rectangular Searching

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  field = Array.new(h) do
    $<.gets.chomp.chars.map {|a| (a == ".") ? "1" : "0"}.join.to_i(2)
  end
  
  max = 0
  h.times do |i|
    result = field[i]
    (h - i).times do |j|
      result &= field[i + j]
      max_w = result.to_s(2).chars.chunk_while {|b, a| b == a and b == "1"}
                    .select {|a| a.first == "1"}.map(&:size).max
      max_w ||= 0
      s = max_w * (j + 1)
      max = s if s > max
    end
  end
  puts max
end

時間オーバー。

def count(num)
  return 0 if num.zero?
  pl = Math.log2(num).to_i + 1
  co = 0
  max = 0
  pl.times do
    if (num % 2).zero?
      co = 0
    else
      co += 1
      max = co if co > max
    end
    num /= 2
  end
  max
end

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  field = Array.new(h) do
    $<.gets.chomp.chars.map {|a| (a == ".") ? "1" : "0"}.join.to_i(2)
  end
  
  max = 0
  h.times do |i|
    result = field[i]
    (h - i).times do |j|
      result &= field[i + j]
      max_w = count(result)
      s = max_w * (j + 1)
      max = s if s > max
    end
  end
  puts max
end

これも時間オーバー。
メソッド count() をこう替えてみる。

def count(num, max = 0)
  return max if num.empty?
  num = num.drop_while {|e| e == "0"}
  l = num.take_while {|e| e == "1"}.size
  max = l if l > max
  count(num.drop_while {|e| e == "1"}, max)
end

やはり時間オーバー。さらにメモ化をしてみても結果は同じ。根本的にアルゴリズムを変えないとダメだな。
他の人の答えを見る。

loop do
  h, w = $<.gets.split.map(&:to_i)
  break if h.zero? and w.zero?
  f = h.times.map { $<.gets.chomp }
  hseq = Array.new(h) {Array.new(w)}
  
  h.times.map do |y|
    hseq[y][0] = (f[y][0] == ".") ? 1 : 0
    (1...w).each {|x| hseq[y][x] = (f[y][x] == ".") ? hseq[y][x - 1] + 1 : 0}
  end
  ans = 0
   
  (w - 1).downto(0) do|x|
    h.times do |fy|
      tmp = w
      lim = h - fy
      (h - fy).times do |dy|
        tmp = [tmp, hseq[fy + dy][x]].min
        ans = [ans, tmp * (dy + 1)].max
        break if tmp * lim < ans
      end
    end
  end
  puts ans
end

なるほどー、時々あるアルゴリズム（動的計画法？）だが、いつもこれが思い浮かばないのだよなあ。勉強になりました。
　

0117 A reward for a Carpenter

towns = Hash.new([])
n = $<.gets.to_i
$<.gets.to_i.times do
  a, b, c, d = $<.gets.split(",").map(&:to_i)
  towns[a] += [[b, c]]
  towns[b] += [[a, d]]
end
s, g, v, p = $<.gets.split(",").map(&:to_i)

travel = ->(start, goal) {
  minimum = Float::INFINITY
  walk = ->(town, visited, cost = 0) {
    if town == goal
      minimum = [minimum, cost].min
    else
      towns[town].each do |nxt, c|
        walk.(nxt, visited + [nxt], cost + c) unless visited.include?(nxt)
      end
    end
  }
  walk.(start, [start])
  minimum
}

v -= travel.(s, g)
v -= travel.(g, s)
puts v - p

簡単なバックトラック法。
　

0118 Property Distribution

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  field = Array.new(h) {$<.gets.chomp.chars}
  
  erase = ->(x, y, fruit) {
    stack = [[x, y]]
    while (a = stack.shift)
      x, y = a
      next if x < 0 or x >= w or y < 0 or y >= h
      next unless field[y][x] == fruit
      field[y][x] = "."
      [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
        stack << [x + dx, y + dy]
      end
    end
  }
  
  num = 0
  i = 0
  loop do
    x, y = i % w, i / w
    i += 1
    unless field[y][x] == "."
      erase.(x, y, field[y][x])
      num += 1
    end
    break if i >= w * h
  end
  puts num
end

最初 erase.() を深さ優先探索でやっていて、どうしても Runtime Error が取れなかった。これは幅優先探索じゃないとダメなのかな。よくわからない。
　

0119 Taro's Obsession

table = Hash.new([])

m = $<.gets.to_i
$<.gets.to_i.times do
  x, y = $<.gets.split.map(&:to_i)
  table[x] += [y]
end

check = ->(order) {
  order.map.with_index do |person, i|
    table[person].map {|b| i < order.index(b)}.all?
  end.all?
}

solve = ->(n, order) {
  if order.size == m
    if check.(order)
      puts order
      exit
    end
  else
    a = table[n]
    ([*1..m] - order - (a ? a : [])).each do |prev|
      solve.(prev, [prev] + order)
    end
  end
}
solve.(2, [2])

10問中 5問で時間オーバー。

table = Hash.new([])

m = io.gets.to_i
io.gets.to_i.times do
  x, y = io.gets.split.map(&:to_i)
  table[y] += [x]
end

check = ->(order) {
  table.map do |k, v|
    v.map {|prev| order.index(prev) < order.index(k)}.all?
  end.all?
}

solve = ->(person, order) {
  if order.size == m
    if check.(order)
      puts order
      exit
    end
  else
    table[person].each do |prev|
      solve.(prev, [prev] + order) unless order.include?(prev)
    end
    ([*1..m] - table[person] - order).each do |prev|
      solve.(prev, [prev] + order) unless order.include?(prev)
    end
  end
}
solve.(2, [2])

10問中 4問で時間オーバー。どうもバックトラック法では無理だな。
他の人の回答を見た。

m = $<.gets.to_i
n = $<.gets.to_i
e = Array.new(m + 1) {[]}
n.times do
  x, y = $<.gets.split.map(&:to_i)
  e[x] << y    #後にあるのを入れている
end
r = [2]

while r.size < m
  1.upto(m) do |i|
    next if r.include?(i)
    catch(:a) do
      e[i].each do |j|
        throw(:a) unless r.include?(j)
      end
      r << i
    end
  end
end
puts r.reverse

なるほどー、後にあるのが確実になってから入れるのかあ。すごいなあ。