AOJ（問題集）16

AIZU ONLINE JUDGE: Programming Challenge
　

0150 Twin Prime

N = 10007

sieve = [*0..N]
2.upto(Math.sqrt(N).to_i) do |i|
  next if sieve[i].zero?
  2.upto(N / i) {|j| sieve[i * j] = 0}
end
sieve = sieve[2..-1].reject {|x| x.zero?}

until (n = $<.gets.to_i).zero?
  idx = sieve.index {|i| i > n} - 1
  i = 0
  i += 1 until sieve[idx - i] - sieve[idx - i - 1] == 2
  puts "#{sieve[idx - i - 1]} #{sieve[idx - i]}"
end

N = 10000 ではダメなことになかなか気づかなかった。
　

0151 Grid

def count(line)
  line.chunk {|i| i.nonzero?}.select(&:first).map {|l| l.last.size}.max || 0
end

until (n = $<.gets.to_i).zero?
  field = n.times.map {$<.gets.chomp.chars.map(&:to_i)}
  
  max_l = field.map {|l| count(l)}.max
  max_l = [field.transpose.map {|l| count(l)}.max, max_l].max
  l = n - 1
  n.times do |i|
    line = (i + 1).times.map {|j| field[i - j][j]}
    tmp1 = count(line)
    line = (i + 1).times.map {|j| field[l - i + j][l - j]}
    tmp2 = count(line)
    line = (i + 1).times.map {|j| field[i - j][l - j]}
    tmp3 = count(line)
    line = (i + 1).times.map {|j| field[l - i + j][j]}
    tmp4 = count(line)
    max_l = [tmp1, tmp2, tmp3, tmp4, max_l].max
  end
  
  puts max_l
end

0.50秒。素朴にやった。まあまあか。
　

0152 Bowling

until (m = $<.gets.to_i).zero?
  result = m.times.map do
    id, *score = $<.gets.split.map(&:to_i)
    th = 0
    
    final_point = 10.times.map do |i|
      if i == 9
        if score[th] == 10 or score[th, 2].sum == 10
          score[th, 3].sum
        else
          score[th, 2].sum
        end
      elsif score[th] == 10
        th += 1
        10 + score[th, 2].sum
      elsif score[th, 2].sum == 10
        th += 2
        10 + score[th]
      else
        th += 2
        score[th - 2, 2].sum
      end
    end.sum
    
    [id, final_point]
  end.sort {|a, b| (b[1] <=> a[1]).nonzero? || a[0] <=> b[0]}
  puts result.map {|a| a.join(" ")}
end

複数キーのソートはここを参考にしました。
　

0153 Triangle and Circle

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  [s, (h - p).norm]
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i
  
  f1 = (p1 - c).norm
  f2 = (p2 - c).norm
  f3 = (p3 - c).norm
  
  g1 = (f1 <= r and f2 >= r) or (f1 >= r and f2 <= r)
  g2 = (f2 <= r and f3 >= r) or (f2 >= r and f3 <= r)
  g3 = (f3 <= r and f1 >= r) or (f3 >= r and f1 <= r)
  
  s, l = perpendicular_foot(p1, p2, c)
  h1 = (0 <= s and s <= 1) and (f1 >= r and f2 >= r) and l <= r
  e1 = l >= r and f1 > r and f2 > r
  s, l = perpendicular_foot(p2, p3, c)
  h2 = (0 <= s and s <= 1) and (f2 >= r and f3 >= r) and l <= r
  e2 = l >= r and f2 > r and f3 > r
  s, l = perpendicular_foot(p3, p1, c)
  h3 = (0 <= s and s <= 1) and (f3 >= r and f1 >= r) and l <= r
  e3 = l >= r and f3 > r and f1 > r
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if e0 and e1 and e2 and e3
    "a"
  elsif f1 <= r and f2 <= r and f3 <= r
    "b"
  elsif g1 or g2 or g3 or h1 or h2 or h3
    "c"
  else
    "d"
  end
  
  puts result
end

Wrong Answer.

require 'matrix'

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  (h - p).norm
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i
  
  f1 = (p1 - c).norm
  f2 = (p2 - c).norm
  f3 = (p3 - c).norm
  
  l = perpendicular_foot(p1, p2, c)
  h1 = l > r
  e1 = l >= r and f1 > r and f2 > r
  l = perpendicular_foot(p2, p3, c)
  h2 = l > r
  e2 = l >= r and f2 > r and f3 > r
  l = perpendicular_foot(p3, p1, c)
  h3 = l > r
  e3 = l >= r and f3 > r and f1 > r
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if e0 and e1 and e2 and e3
    "a"
  elsif f1 <= r and f2 <= r and f3 <= r
    "b"
  elsif f1 > r and f2 > r and f3 > r and h1 and h2 and h3 
    "d"
  else
    "c"
  end
  
  puts result
end

Wrong Answer.

require 'matrix'

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  (h - p).norm
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i
  
  f1 = (p1 - c).norm
  f2 = (p2 - c).norm
  f3 = (p3 - c).norm
  
  h1 = perpendicular_foot(p1, p2, c)
  h2 = perpendicular_foot(p2, p3, c)
  h3 = perpendicular_foot(p3, p1, c)
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if h1 >= r and h2 >= r and h3 >= r and e0 
    "a"
  elsif h1 > r and h2 > r and h3 > r and !e0
    "d"
  elsif f1 <= r and f2 <= r and f3 <= r
    "b"
  else
    "c"
  end
  
  puts result
end

Wrong Answer.

require 'matrix'

def perpendicular_foot(a, b, p)
  s = Rational((p - a).dot(b - a), (b - a).dot(b - a))
  h = a + (b - a) * s
  (h - p).dot(h - p)
end

def triangle_inside(a, b, c, p)
  s, t = Matrix.columns([b - a, c - a]).lup.solve(p - a).to_a
  s > 0 and t > 0 and 0 < s + t and s + t < 1
end

until (p1 = $<.gets.split.map(&:to_i)) == [0, 0]
  p1 = Vector[*p1]
  p2 = Vector[*$<.gets.split.map(&:to_i)]
  p3 = Vector[*$<.gets.split.map(&:to_i)]
  c  = Vector[*$<.gets.split.map(&:to_i)]
  r = $<.gets.to_i ** 2
  
  f1 = (p1 - c).dot(p1 - c)
  f2 = (p2 - c).dot(p2 - c)
  f3 = (p3 - c).dot(p3 - c)
  
  h1 = perpendicular_foot(p1, p2, c)
  h2 = perpendicular_foot(p2, p3, c)
  h3 = perpendicular_foot(p3, p1, c)
  
  e0 = triangle_inside(p1, p2, p3, c)
  
  result = if f1 <= r and f2 <= r and f3 <= r
    "b"
  elsif f1 > r and f2 > r and f3 > r
    min_h = [h1, h2, h3].min
    if e0 and min_h >= r
      "a"
    elsif !e0 and min_h > r
      "d"
    else
      "c"
    end
  else
    "c"
  end
  
  puts result
end

Wrong Answer.
　

0154 Sum of Cards

until (m = $<.gets.to_i).zero?
  cards = m.times.map {$<.gets.split.map(&:to_i)}
  ln = cards.map {|a, b| a * b}.sum
  table = [0]
  cards.each do |a, b|
    table = table.flat_map do |num|
      (b + 1).times.map {|i| num + a * i}
    end
  end
  
  $<.gets.to_i.times do
    puts table.count($<.gets.to_i)
  end
end

20.9秒もかかったのに accept された。
他の人の回答を見てみた。

until (m = $<.gets.to_i).zero?
  cards = m.times.map {$<.gets.split.map(&:to_i)}
  memo = Array.new(cards.size + 1) {[]}
  $<.gets.to_i.times do
    count = ->(i, left) {
      return memo[i][left] if memo[i][left]
      if i >= cards.length
        co = left.zero? ? 1 : 0
      else
        co = 0
        a, b = cards[i]
        (b + 1).times do |j|
          nxt = left - a * j
          break if nxt < 0
          co += count.(i + 1, nxt)
        end
      end
      memo[i][left] = co
    }
    puts count.(0, $<.gets.to_i)
  end
end

0.07秒…。何でこれに気づかない…。
　

0155 Spider Jin

until (n = $<.gets.to_i).zero?
  buildings = n.times.map {$<.gets.split.map(&:to_i)}
  sg = $<.gets.to_i.times.map {$<.gets.split.map(&:to_i)}
  table = Hash.new {|h, k| h[k] = {}}
  buildings.combination(2) do |a, b|
    ida, xa, ya = a
    idb, xb, yb = b
    dist = (xa - xb) ** 2 + (ya - yb) ** 2
    next if dist > 50 ** 2
    table[ida][idb] = Math.sqrt(dist)
    table[idb][ida] = Math.sqrt(dist)
  end
  h = table.map {|k, v| [k, v.keys]}.to_h
  
  sg.each do |s, g|
    shortest = Hash.new(Float::INFINITY)
    pred = {}
    done = h.keys.map {|k| [k, false]}.to_h
    shortest[s] = 0
    
    loop do
      u = nil
      h.each_key do |node|
        next if done[node]
        u = node if !u or shortest[node] < shortest[u]
      end
      break unless u
      done[u] = true
      
      h[u].each do |v|
        if (a = shortest[u] + table[u][v]) < shortest[v]
          shortest[v] = a
          pred[v] = u
        end
      end
    end
    
    result = if pred[g]
      order = []
      while g
        order.unshift(g)
        g = pred[g]
      end
      order.join(" ")
    else
      "NA"
    end
    puts result
  end
end

ダイクストラ法。
　

0156

until (a = io.gets.split.map(&:to_i)) == [0, 0]
  n, m = a
  field = m.times.map {io.gets.chomp.chars}
  i = field.flatten.index("&")
  
  numbering = ->(x, y, num) {
    type = field[y][x]
    queue = [[x, y]]
    while (a = queue.shift)
      x0, y0 = a
      field[y0][x0] = num
      [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
        x1 = x0 + dx
        y1 = y0 + dy
        return num if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m
        next if field[y1][x1] != type
        next if ![".", "#", "&"].include?(field[y1][x1])
        queue << [x1, y1]
      end
    end
    false
  }
  
  catch :jump do
    x, y = i % n, i / n
    [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
      x1 = x + dx
      y1 = y + dy
      if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m
        puts 0
        throw :jump
      else
        num = (field[y1][x1] == "#") ? 0 : 1
        num = numbering.(x1, y1, num)
        if num
          puts 0
          throw :jump
        end
      end
    end
    
    puts -1
  end
  puts field.map(&:join)
end

考え中。
　

0157 Russian Dolls

until (n = $<.gets.to_i).zero?
  ichiro = n.times.map {$<.gets.split.map(&:to_i)}
            .sort {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]}
  m = $<.gets.to_i
  jiro = m.times.map {$<.gets.split.map(&:to_i)}
          .sort {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]}
  
  memo = {}
  
  try = ->(h, r, ichi, ji) {
    key = "#{h},#{r},#{ichi},#{ji}"
    return memo[key] if memo[key]
    return 0 if ichi >= n and ji >= m
    co1 = co2 = 0
    if ichiro[ichi]
      if h > ichiro[ichi][0] and r > ichiro[ichi][1]
        co1 = 1 + try.(ichiro[ichi][0], ichiro[ichi][1], ichi + 1, ji)
      else
        co1 = try.(h, r, ichi + 1, ji)
      end
    end
    if jiro[ji]
      if h > jiro[ji][0] and r > jiro[ji][1]
        co2 = 1 + try.(jiro[ji][0], jiro[ji][1], ichi, ji + 1)
      else
        co2 = try.(h, r, ichi, ji + 1)
      end
    end
    memo[key] = (co1 > co2) ? co1 : co2
  }
  puts try.(Float::INFINITY, Float::INFINITY, 0, 0)
end

これで 0.14秒。自力で考えたオレはえらいが、これは DAG（閉路なし有向グラフ）の最長経路問題なのだった。
なので、動的計画法で解くのがふつうらしい。こんな感じ。

until (n = $<.gets.to_i).zero?
  dolls = n.times.map {$<.gets.split.map(&:to_i)}
  m = $<.gets.to_i
  dolls += m.times.map {$<.gets.split.map(&:to_i)}
  dolls.sort! {|a, b| (b[0] <=> a[0]).nonzero? || b[1] <=> a[1]}
  
  longest = Array.new(n + m, 0)
  
  (0..n + m - 2).each do |i|
    (i + 1...n + m).each do |j|
      if dolls[i][0] > dolls[j][0] and dolls[i][1] > dolls[j][1]
        if (a = longest[i] + 1) > longest[j]
          longest[j] = a
        end
      end
    end
  end
  puts longest.last + 1
end

これで 0.06秒。
　

0158 Collatz's Problem

@memo = {}

def try(n)
  return @memo[n] if @memo[n]
  return 0 if n == 1
  co = if n.even?
    try(n / 2)
  else
    try(n * 3 + 1)
  end
  @memo[n] = co + 1
end

until (n = $<.gets.to_i).zero?
  puts try(n)
end

0159 The Best Body

until (n = $<.gets.to_i).zero?
  min_dif = Float::INFINITY
  persons = []
  n.times.map {$<.gets.split.map(&:to_i)}.each do |p, h, w|
    h = Rational(h, 100)
    dif = (Rational(w, h * h) - 22).abs
    if dif < min_dif
      persons = [p]
      min_dif = dif
    elsif dif == min_dif
      persons << p
    end
  end
  puts persons.sort.first
end