AOJ（問題集）9

AOJ Ruby

AIZU ONLINE JUDGE: Programming Challenge
　

0081 A Symmetric Point

require 'matrix'

$<.readlines.map {|l| l.split(",").map(&:to_f)}.each do |x1, y1, x2, y2, xq, yq|
  p1 = Vector[x1, y1]
  n  = Vector[y2 - y1, x1 - x2].normalize
  q  = Vector[xq, yq]
  d = (p1 - q).dot(n)
  r = q + (2 * d) * n
  printf "%.6f %.6f\n", r[0], r[1]
end

わりとうまく解けた。
　

0082 Flying Jenny

table = [4, 1, 4, 1, 2, 1, 2, 1]

$<.readlines.map {|l| l.split.map(&:to_i)}.each do |persons|
  result = (0..7).map do |i|
    order = table.rotate(i)
    left = persons.map.with_index do |n, j|
      a = n - order[j]
      a < 0 ? 0 : a
    end.sum
    [left, order]
  end.sort_by {|d| d.first}
  min = result.first.first
  result = result.select {|d| d.first == min}.sort_by {|d| d.last.join.to_i}.first
  puts result.last.join(" ")
end

　

0083 Era Name Transformation

require 'date'

table = [["pre-meiji", [   1,  1,  1], [1868,  9,  7]],
         ["meiji"    , [1868,  9,  8], [1912,  7, 29]],
         ["taisho"   , [1912,  7, 30], [1926, 12, 24]],
         ["showa"    , [1926, 12, 25], [1989,  1,  7]],
         ["heisei"   , [1989,  1,  8], [2020,  1,  1]]]
table.map! {|n, d1, d2| [n, Date.new(*d1), Date.new(*d2)]}

$<.readlines.map {|l| Date.new(*l.split.map(&:to_i))}.each do |day|
  table.each do |name, d1, d2|
    if day.between?(d1, d2)
      if name == "pre-meiji"
        puts name
      else
        puts "#{name} #{day.year - d1.year + 1} #{day.month} #{day.day}"
      end
    end
  end
end

　

0084 Search Engine

text = $<.gets.chomp
puts text.split(/[ \.,]/).select {|w| w.length.between?(3, 6)}.join(" ")

　

0085 Joseph's Potato

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  n, m = a
  circle = [*1..n]
  try = ->(po) {
    return circle.first if circle.size == 1
    po += m - 1
    po -= circle.size while po >= circle.size
    circle = circle[0...po] + circle[po + 1..-1]
    try.(po)
  }
  puts try.(n)
end

　

0086 Patrol

loop do
  roots = Hash.new([])
  i = 0
  loop do
    exit unless (l = io.gets)
    break if (l = l.split.map(&:to_i)) == [0, 0]
    a, b = l
    roots[a] += [[b, i]]
    roots[b] += [[a, i]]
    i += 1
  end
  
  try = ->(spot, visited) {
    if spot == 2
      return true if visited == 2 ** i - 1
    else
      roots[spot].each do |nxt, root|
        next if (2 ** root & visited).nonzero?
        return true if try.(nxt, 2 ** root | visited)
      end
    end
    false
  }
  puts try.(1, 0) ? "OK" : "NG"
end

これは時間オーバー。バックトラック法しか思いつかない。ちょっと他の人の回答を見たい。

例えばこの回答。

loop do
  spots = []
 
  loop do
    line = $<.gets
    exit if line.nil?
    p0, p1 = line.chomp.split(" ").map(&:to_i)
    break if p0.zero? and p1.zero?
    p0 -= 1
    p1 -= 1
    spots[p0] = spots[p0] ? (spots[p0] + 1) : 1
    spots[p1] = spots[p1] ? (spots[p1] + 1) : 1
  end
  #p spots
 
  ok = true
 
  if spots[0].even? or spots[1].even?
    ok = false
  else
    (2...spots.length).each do |i|
      if spots[i].odd?
        ok = false
        break
      end
    end
  end
 
  puts ok ? "OK" : "NG"
end

これは…、瞬殺である。配列 spots はその場所から出ている道の数を表わしている。
なるほど、道が一筆書きになればよいわけだな。そんな簡単なことに気づかなかったとは！
　

0087 Strange Mathematical Expression

逆ポーランド記法。

$<.readlines.map {|l| l.chomp.split}.each do |data|
  stack = []
  while (x = data.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      stack << eval("#{b}.to_f #{x} #{a}")
    else
      stack << x
    end
  end
  printf "%.6f\n", stack.first
end

　

0088 The Code A Doctor Loved

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"=>"?"}

$<.readlines.each do |line|
  line.chomp!
  text = ""
  line.each_char {|c| text += table1[c]}
  l = text.length % 5
  text += "0" * (5 - l) if l > 0
  
  result = ""
  until text.empty?
     result += table2[text[0, 5]]
     text = text[5..-1]
  end
  puts result
end

　

0089 The Shortest Path on A Rhombic Path

lines = $<.readlines.map {|l| l.split(",").map(&:to_i)}
ln = lines.size / 2 + 1

up = ->(n, sums) {
  return sums if n == ln
  nxt = Array.new(n + 1, 0)
  sums.each_index do |i|
    nxt[i] = sums[i] + lines[n][i] if i.zero?
    nxt[i + 1] = sums[i, 2].max + lines[n][i + 1]
  end
  up.(n + 1, nxt)
}
mid = up.(1, lines.first)

down = ->(n, sums) {
  return sums.first if sums.size == 1
  nxt = sums.each_cons(2).map.with_index do |pair, i|
    lines[n][i] + pair.max
  end
  down.(n + 1, nxt)
}
puts down.(ln, mid)

こんな面倒なやり方しか思いつかなかった。むずかしかったので一発でいってよかった。ダメだったら考え直す気力がない…。
　

0090 Overlaps of Seals

全然思いつかない…。他人の回答を見る（自己流に改変しています）。

require 'matrix'

DELTA = 1e-6
 
until (n = $<.gets.to_i).zero?
  points = []
  n.times do
    points << Vector[*$<.gets.chomp.split(",").map(&:to_f)]
  end
 
  cps = []
  points.each_with_index do |p0, i|
    (i + 1...n).each do |j|
      p1 = points[j]
      v = p1 - p0
      d = v.norm
      if d <= 1.0 + DELTA
        hd = d / 2
        ul = Math.sqrt(1.0 - hd * hd)
 
        u = Vector[-v[1], v[0]] / d * ul
        c = (p0 + p1) / 2
 
        cps << c + u
        cps << c - u
      end
    end
  end
 
  max_ov = 1
  cps.each do |cp|
    ov = 0
    points.each do |point|
      ov += 1 if (point - cp).norm <= 1.0 + DELTA
    end
    max_ov = ov if max_ov < ov
  end
  puts max_ov
end

いやあ、すごい。これは思いつかなかったなあ…。
20190102162110