AOJ(問題集)17

AIZU ONLINE JUDGE: Programming Challenge
 

0160 Delivery Fee

table = [[60, 2, 600], [80, 5, 800], [100, 10, 1000],
         [120, 15, 1200], [140, 20, 1400], [160, 25, 1600]]

until (n = $<.gets.to_i).zero?
  result = n.times.map {$<.gets.split.map(&:to_i)}.map do |x, y, h, w|
    idx = table.index {|d| x + y + h <= d[0] and w <= d[1]}
    idx ? table[idx].last : 0
  end.sum
  puts result
end

 

0161 Sport Meet

until (n = $<.gets.to_i).zero?
  result = n.times.map {$<.gets.split.map(&:to_i)}.map do |id, *d|
    [id, d.each_slice(2).map {|m, s| 60 * m + s}.sum]
  end.sort {|a, b| a[1] <=> b[1]}.map(&:first)
  puts result[0], result[1], result[-2]
end

 

0162 Hamming Numbers

L = 1000000

table = []
(0..19).each do |a|
  table << (x1 = 2 ** a)
  (1..12).each do |b|
    table << (x2 = 3 ** b)
    y1 = x1 * x2
    table << y1 if y1 <= L
    (1..8).each do |c|
      table << (x3 = 5 ** c)
      y2 = x2 * x3
      y3 = x1 * x3
      y4 = y1 * x3
      table << y2 if y2 <= L
      table << y3 if y3 <= L
      table << y4 if y4 <= L
    end
  end
end
table.uniq!.sort!

until (n = $<.gets.chomp) == "0"
  m, n = n.split.map(&:to_i)
  a = table.bsearch_index {|x| x >= m}
  b = table.bsearch_index {|x| x > n}
  b = b ? b : table.size
  puts b - a
end

 

0163 Highway Toll

toll = [[0, 300, 500, 600, 700, 1350, 1650],
        [0, 0, 350, 450, 600, 1150, 1500],
        [0, 0, 0, 250, 400, 1000, 1350],
        [0, 0, 0, 0, 250, 850, 1300],
        [0, 0, 0, 0, 0, 600, 1150],
        [0, 0, 0, 0, 0, 0, 500]]
S, E = 17 * 60 + 30, 19 * 60 + 30

until (d = $<.gets.to_i).zero?
  h, m = $<.gets.split.map(&:to_i)
  td = h * 60 + m
  a = $<.gets.to_i
  h, m = $<.gets.split.map(&:to_i)
  ta = h * 60 + m
  
  d, a = a, d if d > a
  f = if (a == 6 and d == 1) or (a == 7 and d <= 3)
    false
  elsif td.between?(S, E) or ta.between?(S, E)
    true
  else
    false
  end
  
  result = toll[d - 1][a - 1]
  result /= 2 if f
  puts ((result / 50.0).ceil * 50).to_i
end

td, ta が S と E の間にあればよいということがなかなかわからなかった。
 

0164 Ohajiki Game

until (n = $<.gets.to_i).zero?
  ary = $<.gets.split.map(&:to_i)
  ohajiki = 32
  loop do
    ohajiki -= (ohajiki - 1) % 5
    puts ohajiki
    a = ary.first
    if ohajiki <= a
      ohajiki = 0
    else
      ohajiki -= a
    end
    puts ohajiki
    break if ohajiki.zero?
    ary.rotate!
  end
end

 

0165 Lottery

MP = 999983

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

until (n = $<.gets.to_i).zero?
  account = n.times.map do
    p, m = $<.gets.split.map(&:to_i)
    s = sieve.bsearch_index {|i| i >= p - m}
    e = sieve.bsearch_index {|i| i > p + m} || sieve.size
    prize = e - s
    prize.zero? ? -1 : prize - 1
  end.sum
  puts account
end

 

0166 Area of Polygon

until (m = $<.gets.to_i).zero?
  poly1 = (m - 1).times.map {$<.gets.to_i}
  poly1 << 360 - poly1.sum
  n = $<.gets.to_i
  poly2 = (n - 1).times.map {$<.gets.to_i}
  poly2 << 360 - poly2.sum
  
  area1 = poly1.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum
  area2 = poly2.map {|i| Math.sin(i / 180.0 * Math::PI)}.sum
  
  result = case
           when area1 == area2 then 0
           when area1 > area2  then 1
           else 2
           end
  puts result
end

 

0167 Bubble Sort

def bubble_sort(ary)
  n = ary.size
  co = 0
  (n - 1).downto(1) do |i|
    i.times do |j|
      if ary[j] > ary[j + 1]
        ary[j], ary[j + 1] = ary[j + 1], ary[j]
        co += 1
      end
    end
  end
  co
end

until (n = $<.gets.to_i).zero?
  puts bubble_sort(n.times.map {$<.gets.to_i})
end

 

0168 Kannondou

@memo = {}

def count(n)
  return @memo[n] if @memo[n]
  result = case n
           when 1 then 1
           when 2 then 2
           when 3 then 4
           else
             count(n - 1) + count(n - 2) + count(n - 3)
           end
  @memo[n] = result
end

until (n = $<.gets.to_i).zero?
  days = Rational(count(n), 10).ceil
  puts Rational(days, 365).ceil
end

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

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

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

AOJ(問題集)14

AIZU ONLINE JUDGE: Programming Challenge
 

0130 Train

$<.gets.to_i.times do
  given = $<.gets.chomp.split(/(->|<-)/)
  train = [given.shift]
  while (dir = given.shift)
    car = given.shift
    next if train.include?(car)
    (dir == "->") ? train.push(car) : train.unshift(car)
  end
  puts train.join
end

出来てみればじつに簡単なことなのに、ものすごく悩んだ。
 

0131 Doctor's Strange Particles

L = 10

$<.gets.to_i.times do
  field = Array.new(L) {$<.gets.split.map(&:to_i)}.flatten
  result = Array.new(L * L, 0)
  
  reverse = ->(x, y) {
    [[0, 0], [1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
      x1 = x + dx
      y1 = y + dy
      next if x1 < 0 or x1 >= L or y1 < 0 or y1 >= L
      i = y1 * L + x1
      field[i] = 1 - field[i]
    end
  }
  
  top_row = ->(i) {
    if i >= L
      tmp1 = field.dup
      tmp2 = result.dup
      while i < L * L
        if field[i - L] == 1
          result[i] = 1
          reverse.(i % L, i / L)
        end
        i += 1
      end
      if field.all? {|i| i.zero?}
        puts result.each_slice(L).map {|a| a.join(" ")}
        true
      else
        field  = tmp1
        result = tmp2
        false
      end
    else
      return true if top_row.(i + 1)
      
      result[i] = 1
      reverse.(i % L, i / L)
      return true if top_row.(i + 1)
      reverse.(i % L, i / L)
      result[i] = 0
      false
    end
  }
  top_row.(0)
end

些細なミスが多かった。
 

0132 Jigsaw Puzzle

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  puzzle = h.times.map {$<.gets.chomp}
  pieces = $<.gets.to_i.times.flat_map do
    ph, pw = $<.gets.split.map(&:to_i)
    tmp = [ph.times.map {$<.gets.chomp}]
    3.times do
      tmp << tmp.last.reverse.map(&:chars).transpose.map(&:join)
    end
    tmp
  end
  
  $<.gets.to_i.times do
    k, *tn = $<.gets.split.map(&:to_i)
    tn = tn.map {|i| i - 1}.sort
    tn1 = tn.flat_map {|i| 4.times.map {|j| i * 4 + j}}.sort
    
    solve = ->(embeded, selected = [], selected_num = []) {
      return true if !embeded.join.index(".") and tn == selected_num
      
      adjust = ->(piece, piece_num) {
        idx = embeded.join.index(".")
        return false unless idx
        x, y = idx % w, idx / w
        
        p_idx = piece.join.index("#")
        pw = piece.first.length
        px = p_idx % pw
        return false if x + pw - px >= w
        return false if (x -= px) < 0
        
        nxt = embeded.map(&:dup)
        piece.each_index do |i|
          piece[i].each_char.with_index do |c, j|
            if c == "#"
              if embeded[y + i][x + j] == "."
                nxt[y + i][x + j] = (piece_num / 4).to_s
              else
                return false
              end
            end
          end
        end
        nxt
      }
      
      (tn1 - selected).each do |pn|
        next unless selected.select {|i| i / 4 == pn / 4}.empty?
        if (nxt = adjust.(pieces[pn], pn))
          return true if solve.(nxt, selected + [pn], (selected_num + [pn / 4]).sort)
        end
      end
      false
    }
    puts solve.(puzzle) ? "YES" : "NO"
  end
end

時間オーバー。

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  puzzle = h.times.map {$<.gets.chomp}
  pieces = (n = $<.gets.to_i).times.map do
    ph, pw = $<.gets.split.map(&:to_i)
    ph.times.map {$<.gets.chomp}
  end
  
  io.gets.to_i.times do
    k, *tn = $<.gets.split.map(&:to_i)
    tn = tn.map {|i| i - 1}.sort
    
    solve = ->(embeded, selected = []) {
      return true if !embeded.join.index(".") and tn == selected
      
      adjust = ->(piece) {
        idx = embeded.join.index(".")
        return false unless idx
        x, y = idx % w, idx / w
        
        p_idx = piece.join.index("#")
        pw = piece.first.length
        px = p_idx % pw
        return false if x + pw - px >= w
        return false if (x -= px) < 0
        
        nxt = embeded.map(&:dup)
        piece.each_index do |i|
          piece[i].each_char.with_index do |c, j|
            if c == "#"
              if embeded[y + i][x + j] == "."
                nxt[y + i][x + j] = "#"
              else
                return false
              end
            end
          end
        end
        nxt
      }
      check = ->(piece_num) {
        candidate = pieces[piece_num]
        nexts = []
        4.times do
          if (nxt = adjust.(candidate))
            nexts << nxt
          end
          candidate = candidate.reverse.map(&:chars).transpose.map(&:join)
        end
        nexts.empty? ? false : nexts
      }
      
      (tn - selected).each do |piece_num|
        if (nexts = check.(piece_num))
          nexts.each do |nxt|
            return true if solve.(nxt, (selected + [piece_num]).sort)
          end
        end
      end
      false
    }
    puts solve.(puzzle) ? "YES" : "NO"
  end
end

上も下もやり方は合っていると思うけれど、時間オーバー。Ruby では誰も解けていない。
 

0133 Rotation of a Pattern

given = $<.readlines.map(&:chomp)
3.times do |i|
  puts 90 * (i + 1)
  puts given = given.reverse.map(&:chars).transpose.map(&:join)
end

突然簡単に。
 

0134 Exit Survey

n = $<.gets.to_i
puts Array.new(n) {$<.gets.to_i}.sum / n

 

0135 Clock Short Hand and Long Hand

$<.gets.to_i.times do
  h, m = $<.gets.split(":").map(&:to_r)
  l, s = m * 6, (h * 60 + m) / 2
  r = (l - s).abs
  r = 360 - r if r > 180
  st = if 0 <= r and r < 30
    "alert"
  elsif 90 <= r and r <= 180
    "safe"
  else
    "warning"
  end
  puts st
end

 

0136 Frequency Distribution of Height

度数分布。

L = 6
table = 165.0.step(185.0, 5.0).each_cons(2).to_a 
table = [[0, 165.0]] + table + [[185.0, Float::INFINITY]]
count = Array.new(L, 0)

$<.gets.to_i.times do
  h = $<.gets.to_f
  count[table.index {|a, b| a <= h and h < b}] += 1
end

count.each_with_index {|i, j| puts "#{j + 1}:" + "*" * i}

 

0137 Middle-Square Method

平方採中法。

$<.gets.to_i.times do |i|
  num = $<.gets.to_i
  rnd = Enumerator.new do |y|
    loop do
      num = (num * num).to_s.rjust(8, "0")[2, 4].to_i
      y << num
    end
  end
  puts "Case #{i + 1}:"
  puts rnd.take(10)
end

Ruby っぽいコードだと思います。Enumerator にぴったりな問題というのはあまりない気がする。
 

0138 Track and Field Competition

get = ->{ Array.new(8) {$<.gets.chomp.split} }

left = 3.times.flat_map do
  given = get.().sort_by {|a| a.last.to_f}
  puts given.shift.join(" ")
  puts given.shift.join(" ")
  given
end.sort_by {|a| a.last.to_f}
puts left.shift.join(" ")
puts left.shift.join(" ")

 

0139 Snakes

$<.gets
$<.readlines.map(&:chomp).each do |line|
  s1 = /^>'(=+)#(=+)~$/.match(line)
  s2 = /^>\^(Q=)+~~$/.match(line)
  str = if s1 and s1[1] == s1[2]
    "A"
  elsif s2
    "B"
  else
    "NA"
  end
  puts str
end

正規表現を使うのはめずらしい。

AOJ(問題集)13

AIZU ONLINE JUDGE: Programming Challenge
 

0120 Patisserie

@memo = {}

def length(circles)
  return @memo[circles] if @memo[circles]
  l = case (s = circles.size)
      when 0 then 0
      when 1 then 0
      when 2
        r1, r2 = circles.first, circles.last
        Math.sqrt((r1 + r2) ** 2 - (r1 - r2) ** 2)
      else
        s1 = s / 2
        length(circles[0..s1]) + length(circles[s1..-1])
      end
  @memo[circles] = l
end

$<.readlines.map {|l| l.split.map(&:to_i)}.each do |w, *r|
  minimum = Float::INFINITY
  result = "NA"
  r.permutation do |circles|
    l = circles.first + length(circles) + circles.last
    minimum = [minimum, l].min
    if minimum <= w
      result = "OK"
      break
    end
  end
  puts result
end

時間オーバー。まるで思いつかない。こういうパッキングの問題は決まった解法がないらしい。
他の人の回答を見た。

#!ruby -pal
$c={}
def f l,*a
a[0]?($c[a.sort<<l]||=a.map{f(*a.rotate!)+(4*a[0]*l)**0.5}.min):l
end
m,*r=$F.map &:to_i
$_=r.any?{f(*r.rotate!)+r[0]<=m}?:OK:"NA"

???
読めるように書き直してもわからない。

$c = {}

def f(l, *a)
  if a[0]
    $c[a.sort << l] ||= a.map{ f(*a.rotate!) + (4 * a[0] * l) ** 0.5 }.min
  else
    l
  end
end

while (a = $<.gets)
  m, *r = a.split.map(&:to_i)
  puts r.any? {f(*r.rotate!) + r[0] <= m} ? "OK" : "NA"
end

ははあ、なるほど、並び方の順番は結果に関係なくて、ただ両端のみ関係するのか。そうなのかな。だから rotate でやっているのね。ふーむ、よく考えてみよう。決して自明ではないと思う。
しかしこのコード超すごいな。これでメモ化までやっているとは。圧倒的なコード量の少なさだ。
ちなみにこの問題、Ruby では四人しか正解できていない。
 

0121 Seven Puzzle

A = [*0..7]
memo = {A=>0}

stack = [A + [0]]
check = [A.join.to_i]

while (board = stack.shift)
  swap = ->(a, b) {
    tmp = board.dup
    tmp[a], tmp[b] = tmp[b], tmp[a]
    tmp
  }
  move = case (i = board.index(0))
         when 0 then [1, 4]
         when 1, 2 then [i - 1, i + 1, i + 4]
         when 3 then [2, 7]
         when 4 then [0, 5]
         when 5, 6 then [i - 1, i + 1, i - 4]
         when 7 then [3, 6]
         end
  move.each do |j|
    nxt = swap.(i, j)
    a = nxt[0, 8].join.to_i
    next if check.include?(a)
    nxt[8] += 1
    memo[nxt[0, 8]] = nxt[8]
    check << a
    stack << nxt
  end
end

$<.readlines.map {|a| a.split.map(&:to_i)}.each do |given|
  puts memo[given]
end

2.05秒かかった。最初苦し紛れで書いたのがヒントになった。あらかじめ全パターンを計算しておくという方法。ちなみに全パターンは 20160 通りある。
他の人の回答を参考にして、modify したバージョン。

A = "01234567"
memo = {A=>0}

stack = [[A, 0]]
table = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7],
         [0, 5], [4, 6, 1], [5, 7, 2], [3, 6]].freeze

while (board = stack.shift)
  swap = ->(a, b) {
    tmp = board.first.dup
    tmp[a], tmp[b] = tmp[b], tmp[a]
    [tmp, board.last]
  }
  i = board.first.index("0")
  table[i].each do |j|
    nxt = swap.(i, j)
    next if memo[nxt.first]
    nxt[1] += 1
    memo[nxt.first] = nxt.last
    stack << nxt
  end
end

$<.readlines.map {|a| a.split.join}.each do |given|
  puts memo[given]
end

これだと 0.16秒。Array を String に替え、冗長な部分を削った(不必要な check[] を無くした)。
 

0122 Summer of Pyonkichi

L = 10
movable = [[-1, -2], [0, -2], [1, -2],
           [-1,  2], [0,  2], [1,  2],
           [-2, -1], [-2, 0], [-2, 1],
           [ 2, -1], [ 2, 0], [ 2, 1]]

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  px, py = a
  n = $<.gets.to_i
  result = "NA"
  sprinkler = $<.gets.split.map(&:to_i).each_slice(2).to_a
  
  try = ->(x, y, i = 0) {
    if i == n
      result = "OK"
    else
      s = sprinkler[i]
      movable.each do |dx, dy|
        nx = x + dx
        ny = y + dy
        check = ->{
          nx.between?(s[0] - 1, s[0] + 1) && ny.between?(s[1] - 1, s[1] + 1)
        }
        next if nx < 0 or nx >= L or ny < 0 or ny >= L
        try.(nx, ny, i + 1) if check.()
      end
    end
  }
  
  try.(px, py)
  puts result
end

コーディングは楽ではないけれど、バックトラック法とわかっているから助かる。
 

0123 Speed Skating Badge Test

table = [[35.5, 71.0, :AAA], [37.5, 77.0, :AA], [40.0, 83.0, :A], [43.0, 89.0, :B],
         [50.0, 105.0, :C], [55.0, 116.0, :D], [70.0, 148.0, :E]]

$<.readlines.map {|l| l.split.map(&:to_f)}.each do |a, b|
  catch :jump do
    table.each do |ta, tb, cname|
      if a < ta and b < tb
        puts cname
        throw :jump
      end
    end
    puts "NA"
  end
end

ひさしぶりに極簡単。ホッとするなあ。
 

0124 League Match Score Sheet

result = []
until (n = $<.gets.to_i).zero?
  teams = Array.new(n) do
    name, *nums = $<.gets.split
    po = nums.map(&:to_i).zip([3, 0, 1]).inject(0) {|acc, i| acc + i[0] * i[1]}
    [name, po]
  end.sort {|a, b| b[1] <=> a[1]}
  result << teams.map {|a| a.join(",") + "\n"}.join
end
puts result.join("\n")

 

0125 Day Count

require 'date'

until (a = $<.gets.split.map(&:to_i)).index {|i| i < 0}
  puts (Date.new(*a[3, 3]) - Date.new(*a[0, 3])).to_i
end

標準添付ライブラリを使うというインチキ。
 

0126 Puzzle

数独ソルバではなくて、数独チェッカーみたいなもの。

L = 9
T = L / 3

def check(line)
  co = Hash.new(0)
  line.each {|num| co[num] += 1}
  (0...L).select {|i| co[line[i]] > 1}
end

def square
  L.times {|i| yield(i % T, i / T)}
end

result = []

$<.gets.to_i.times do
  field = Array.new(L) {$<.gets.split.map(&:to_i)}
  marked = []
  
  field.each_with_index do |row, i|
    marked += check(row).map {|j| i * L + j}
  end
  L.times do |i|
    col = Array.new(L) {|j| field[j][i]}
    marked += check(col).map {|k| k * L + i}
  end
  square do |x, y|
    sx, sy = x * T, y * T
    block = Array.new(L) {|i| field[sy + i / T][sx + i % T]}
    marked += check(block).map {|i| (sy + i / T) * L + sx + i % T}
  end
  
  result << field.flatten.map.with_index do |num, i|
    str = (marked.include?(i) ? "*" : " ") + num.to_s
    str + ((i % L == L - 1) ? "\n" : "")
  end.join
end

puts result.join("\n")

意外とむずかしい。というか面倒くさい。
 

0127 Pocket Pager Input

table = {"61"=>"z", "62"=>".", "63"=>"?", "64"=>"!", "65"=>" "}
25.times {|i| table["#{i / 5 + 1}#{i % 5 + 1}"] = (97 + i).chr}

$<.readlines.map(&:chomp).each do |cipher|
  catch :jump do
    text = ""
    i = 0
    while i < cipher.size
      a = table[cipher[i, 2]]
      unless a
        puts "NA"
        throw :jump
      end
      text += a
      i += 2
    end
    puts text
  end
end

 

0128 Abacus

そろばん。

L = 5
table = Array.new(10) {|i| [i / 5, i % 5]}

r = $<.readlines.map {|l| l.chomp.rjust(L, "0").chars.map(&:to_i)}.map do |given|
  soroban = given.map do |place|
    high, low = table[place]
    ((high.zero? ? "* =" : " *=") + "*" * low + " " + "*" * (4 - low)).chars
  end
  soroban.transpose.map {|l| l.join + "\n"}.join
end.join("\n")

print r

 

0129 Hide-and-Seek Supporting System

かくれんぼう。

require 'matrix'

until (num = $<.gets.to_i).zero?
  circles = Array.new(num) do
    x, y, r = $<.gets.split.map(&:to_r)
    [Vector[x, y], r]
  end
  
  $<.gets.to_i.times do
    tx, ty, sx, sy = $<.gets.split.map(&:to_r)
    ta  = Vector[tx, ty]
    oni = Vector[sx, sy]
    v = ta - oni
    n = Vector[v[1], -v[0]].normalize
    
    f = circles.map do |o, r|
      pos1 = (oni - o).norm < r
      pos2 = (ta  - o).norm < r
      if pos1 and pos2
        false
      elsif !pos1 and !pos2
        s, t = Matrix.columns([v, -n]).lup.solve(o - oni).to_a
        s.between?(0, 1) and t.abs <= r
      else
        true
      end
    end.any?
    
    puts f ? "Safe" : "Danger"
  end
end

1.28秒かかった。他の人は瞬殺だけれど、それでも Ruby で解けているのは 3人しかいませんよ。自慢自慢。

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

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

SSD の寿命を Linux で判断する

SSD(Intel X25-M)で寿命を確認するには at nkjmkzk.net

$ sudo smartctl -i /dev/sdc -d sat -a
smartctl 6.6 2016-05-31 r4324 [x86_64-linux-4.18.0-13-generic] (local build)
Copyright (C) 2002-16, Bruce Allen, Christian Franke, www.smartmontools.org

=== START OF INFORMATION SECTION ===
Device Model:     SATA SSD
Serial Number:    D61E076A1D2203758638
LU WWN Device Id: 5 000000 000000000
Firmware Version: SBFM10.6
User Capacity:    240,057,409,536 bytes [240 GB]
Sector Size:      512 bytes logical/physical
Rotation Rate:    Solid State Device
Form Factor:      < 1.8 inches
Device is:        Not in smartctl database [for details use: -P showall]
ATA Version is:   Unknown(0x0ff8) (minor revision not indicated)
SATA Version is:  SATA 3.2, 6.0 Gb/s (current: 6.0 Gb/s)
Local Time is:    Tue Jan 29 00:20:22 2019 JST
SMART support is: Available - device has SMART capability.
SMART support is: Enabled

=== START OF READ SMART DATA SECTION ===
SMART overall-health self-assessment test result: PASSED

General SMART Values:
Offline data collection status:  (0x00)	Offline data collection activity
					was never started.
					Auto Offline Data Collection: Disabled.
Self-test execution status:      (   0)	The previous self-test routine completed
					without error or no self-test has ever 
					been run.
Total time to complete Offline 
data collection: 		(65535) seconds.
Offline data collection
capabilities: 			 (0x79) SMART execute Offline immediate.
					No Auto Offline data collection support.
					Suspend Offline collection upon new
					command.
					Offline surface scan supported.
					Self-test supported.
					Conveyance Self-test supported.
					Selective Self-test supported.
SMART capabilities:            (0x0003)	Saves SMART data before entering
					power-saving mode.
					Supports SMART auto save timer.
Error logging capability:        (0x01)	Error logging supported.
					General Purpose Logging supported.
Short self-test routine 
recommended polling time: 	 (   4) minutes.
Extended self-test routine
recommended polling time: 	 (  32) minutes.
Conveyance self-test routine
recommended polling time: 	 (   8) minutes.

SMART Attributes Data Structure revision number: 16
Vendor Specific SMART Attributes with Thresholds:
ID# ATTRIBUTE_NAME          FLAG     VALUE WORST THRESH TYPE      UPDATED  WHEN_FAILED RAW_VALUE
  1 Raw_Read_Error_Rate     0x000b   100   100   050    Pre-fail  Always       -       0
  9 Power_On_Hours          0x0012   100   100   000    Old_age   Always       -       6907
 12 Power_Cycle_Count       0x0012   100   100   000    Old_age   Always       -       4379
168 Unknown_Attribute       0x0012   100   100   000    Old_age   Always       -       0
170 Unknown_Attribute       0x0003   093   093   010    Pre-fail  Always       -       180
173 Unknown_Attribute       0x0012   100   100   000    Old_age   Always       -       2490448
192 Power-Off_Retract_Count 0x0012   100   100   000    Old_age   Always       -       1372
194 Temperature_Celsius     0x0023   067   067   000    Pre-fail  Always       -       33 (Min/Max 33/33)
218 Unknown_Attribute       0x000b   100   100   050    Pre-fail  Always       -       0
231 Temperature_Celsius     0x0013   100   100   000    Pre-fail  Always       -       96
241 Total_LBAs_Written      0x0012   100   100   000    Old_age   Always       -       7107

SMART Error Log Version: 1
No Errors Logged

SMART Self-test log structure revision number 1
No self-tests have been logged.  [To run self-tests, use: smartctl -t]

SMART Selective self-test log data structure revision number 0
Note: revision number not 1 implies that no selective self-test has ever been run
 SPAN  MIN_LBA  MAX_LBA  CURRENT_TEST_STATUS
    1        0        0  Not_testing
    2        0        0  Not_testing
    3        0        0  Not_testing
    4        0        0  Not_testing
    5        0        0  Not_testing
Selective self-test flags (0x0):
  After scanning selected spans, do NOT read-scan remainder of disk.
If Selective self-test is pending on power-up, resume after 0 minute delay.



上の情報をどう読み取ればよいかわからなかったので、Windows 7CrystalDiskInfo をインストールして調べてみた。
「Crystal Disk Info」で、SSDの健康状態を把握しよう! | SSD徹底解説!
ただ、Wndows では ext4 が読み取れないので、下を参考に Ext2Fsd をインストールする。
ext4のパーティションをWindowsで読み書きする方法 | Linux Fan
以上の結果、下のように診断されました。
20190129010121
結果としては、Linux で smartctl を使ったのと同じ情報だが、なるほどこれはわかりやすい。
まだこの SSD は大丈夫みたいです。(2019/1/29)

AOJ(問題集)11

AIZU ONLINE JUDGE: Programming Challenge
 

0100 Sale Result

問題が曖昧。同じ社員が二度出てくるかどうかはっきりしない。

Border = 1_000_000

until (n = $<.gets.to_i).zero?
  data = Hash.new(0)
  entry = []
  n.times do
    e, p, q = $<.gets.split.map(&:to_i)
    data[e] += p * q
    entry << e if data[e] >= Border
  end
  puts entry.empty? ? "NA" : entry.uniq
end

 

0101 Aizu PR

$<.gets.to_i.times do
  text = $<.gets.chomp
  result = ""
  po = 0
  while result.size < text.size
    if text[po, 7] == "Hoshino"
      result += "Hoshina"
      po += 7
    else
      result += text[po]
      po += 1
    end
  end
  puts result
end

 

0102 Matrix-like Computation

until (n = $<.gets.to_i).zero?
  table = n.times.map do
    l = $<.gets.split.map(&:to_i)
    l + [l.sum]
  end
  last = (n + 1).times.map do |i|
    n.times.map {|j| table[j][i]}.sum
  end
  puts (table + [last]).map {|l| l.map {|i| sprintf("%5d", i)}.join }
end

簡単な問題でも [提出] のボタンを押すときはドキドキするな。
 

0103 Baseball Simulation

$<.gets.to_i.times do
  bases = [0, 0, 0]
  out_count = 0
  points = 0
  while out_count < 3
    case $<.gets.chomp
    when "OUT"
      out_count += 1
      puts points if out_count >= 3
    when "HIT"
      bases << 1
      points += bases.shift
    when "HOMERUN"
      points += bases.sum + 1
      bases = [0, 0, 0]
    else
      raise "error"
    end
  end
end

 

0104 Magical Tiles

ひさしぶりにやる。

until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  h, w = a
  tiles = h.times.map {$<.gets.chomp}
  positions = [0]
  x, y = 0, 0
  
  result = loop do
    case tiles[y][x]
    when ">" then x += 1
    when "<" then x -= 1
    when "^" then y -= 1
    when "v" then y += 1
    when "." then break "#{x} #{y}"
    else raise "error"
    end
    po = y * w + x
    break "LOOP" if positions.include?(po)
    positions << po
  end
  puts result
end

簡単だけれどドキドキするな。
 

0105 Book Index

index = Hash.new([])

$<.readlines.map do |l|
  a = l.chomp.split
  [a.first, a.last.to_i]
end.each {|word, page| index[word] += [page]}

index.keys.sort.each {|k| puts k, index[k].sort.join(" ")}

 

0106 Discounts of Buckwheat

table = [[200, 380, 5, 0.8], [300, 550, 4, 0.85], [500, 850, 3, 0.88]]
A, B, C = table.map(&:first)

calc = ->(shop, num) {
  t = table[shop]
  discount = (num / t[2]) * t[2]
  discount * t[1] * t[3] + (num - discount) * t[1]
}

until (soba = $<.gets.to_i).zero?
  min = Float::INFINITY
  (0..soba / C).each do |c|
    pay = calc.(2, c)
    soba1 = soba - c * C
    
    (0..soba1 / B).each do |b|
      pay1 = pay + calc.(1, b)
      soba2 = soba1 - b * B
      
      next if (soba2 % A).nonzero?
      pay2 = pay1 + calc.(0, soba2 / A)
      min = pay2 if pay2 < min
    end
    
  end
  puts min.to_i
end

再帰で解いた方がよかったかな。ごちゃごちゃしたコードだ。
 

0107 Carry a Cheese

until (a = $<.gets.split.map(&:to_i)) == [0, 0, 0]
  $<.gets.to_i.times.map {$<.gets.to_i}.each do |r|
    result = a.combination(2).map do |w, h|
      Math.sqrt((w / 2.0) ** 2 + (h / 2.0) ** 2) < r
    end.any?
    puts result ? "OK" : "NA"
  end
end

 

0108 Operation of Frequency of Appearance

def operation(ary, prev = [], i = 0)
  return i - 1, ary if ary == prev
  count = Hash.new(0)
  ary.each {|x| count[x] += 1}
  operation(ary.map {|x| count[x]}, ary, i + 1)
end

until $<.gets.to_i.zero?
  i, ary = operation($<.gets.split.map(&:to_i))
  puts i, ary.join(" ")
end

 

0109 Smart Calculator

$<.gets.to_i.times do
  splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/)
  output = []
  stack = []
  a = nil
  until (token = splited.shift) == ["="]
    token = token.first
    case token
    when "(" then stack << token
    when ")" then
      output << a until (a = stack.pop) == "("
    when "*", "/"
      loop do
        a = stack.last
        break unless %w(* /).include?(a)
        output << stack.pop
      end
      stack << token
    when "+", "-"
      loop do
        a = stack.last
        break unless %w(+ - * /).include?(a)
        output << stack.pop
      end
      stack << token
    else
      output << token
    end
  end
  output << a while (a = stack.pop)
  
  stack = []
  while (x = output.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      stack << eval("#{b} #{x} #{a}").to_i
    else
      stack << x
    end
  end
  puts stack.first
end

何がいけないのかわからない。
どうしてもわからないので他人の回答を見た。喰らった…。

$<.gets.to_i.times do
  splited = $<.gets.chomp.scan(/([0-9\.]+|\+|\-|\*|\/|\(|\)|=)/)
  a = nil
  
  # パーサー(逆ポーランド記法に変換)
  output = []
  stack = []
  until (token = splited.shift) == ["="]
    token = token.first
    case token
    when "(" then stack << token
    when ")" then
      output << a until (a = stack.pop) == "("
    when "*", "/"
      loop do
        a = stack.last
        break unless %w(* /).include?(a)
        output << stack.pop
      end
      stack << token
    when "+", "-"
      loop do
        a = stack.last
        break unless %w(+ - * /).include?(a)
        output << stack.pop
      end
      stack << token
    else
      output << token.to_r
    end
  end
  output << a while (a = stack.pop)
  
  # 逆ポーランド記法を処理
  stack = []
  while (x = output.shift)
    if %w(+ - * /).include?(x)
      a, b = stack.pop, stack.pop
      if x == "/" and ((a < 0) ^ (b < 0))
        stack << -(b.abs / a.abs)
      else
        stack << eval("#{b.to_i} #{x} #{a.to_i}").to_i
      end
    else
      stack << x
    end
  end
  puts stack.first.to_i
end

これを見てほしい。

$ pry
[1] pry(main)> -3/2
=> -2

マジか! -1 ではないのか!

div はメソッド / を呼びだし、floorを取ることで計算されます。

class Numeric (Ruby 2.5.0)

やられた。そういう Ruby の仕様なのね。勉強になりました。せっかくパーサー(操車場アルゴリズム)まで書いて頑張ったのに…。なお、皆さん演算子の再定義でやっておられる。自分もそれは考えたが、それではつまらん。

AOJ(問題集)10

AIZU ONLINE JUDGE: Programming Challenge
 

0091 Blur

L = 10
table = [[[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2], [-1, 2], [-2, 2], [1, 2],
  [2, 2], [0, 3], [-1, 3], [1, 3], [0, 4]],
  [[0, 0], [1, 0], [2, 0], [0, 1], [1, 1], [2, 1], [0, 2], [1, 2], [2, 2]],
  [[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2]]]

n = $<.gets.to_i
cloth = $<.readlines.map {|l| l.split.map(&:to_i)}

copy = ->(ary) { ary.map {|l| l.dup} }
form = ->(x, y, i) {
  case (j = 3 - i)
  when 1 then "#{x} #{y + 1} #{j}"
  when 2 then "#{x + 1} #{y + 1} #{j}"
  when 3 then "#{x} #{y + 2} #{j}"
  else nil
  end
}

try = ->(place, field, co, order = []) {
  # にじみがあるまでスキップ
  x = y = nil
  loop do
    return false if place >= L * L
    x, y = place % L, place / L
    break if field[y][x].nonzero?
    place += 1
  end
  
  result = false
  # 大、中、小の滴を順に試す
  table.each_with_index do |drip, i|
    tmp = copy.(field)
    
    catch(:jump) do
      # 滴を試す(適合しなければ大域脱出で次の滴へ)
      drip.each do |po|
        x1, y1 = x + po[0], y + po[1]
        throw(:jump) if x1 < 0 or x1 >= L or y1 >= L or tmp[y1][x1].zero?
        tmp[y1][x1] -= 1
      end
      
      # 滴が適合した場合の処理
      co -= 1
      prc = form.(x, y, i)
      if co.zero?
        if tmp.flatten.map(&:zero?).all?
          return order + [prc]    #解が発見された場合(一気にリターン)
        else
          co += 1
          throw(:jump)
        end
      end
      
      result = try.(place, tmp, co, order + [prc])
      return result if result
      co += 1
    end
    
  end
  result
}
puts try.(0, cloth, n)

よくこんなのできたな。いまのところ Ruby で解けたのは 5人だけで、タイムは自分が最速。うれしい。
 

0092 Square Searching

until (n = $<.gets.to_i).zero?
  field = Array.new(n) {$<.gets.chomp}
  max = 0
  
  check = ->(x, y, num) {
    num.times do |i|
      num.times do |j|
        return false if x + j >= n or y + i >= n
        return false if field[y + i][x + j] == "*"
      end
    end
    true
  }
  
  (0...n * n).each do |i|
    x, y = i % n, i / n
    (max + 1..n - x).each do |width|
      max = width if check.(x, y, width)
    end
  end
  puts max
end

これだと時間オーバー。ちょっと素朴すぎるか。
高速化に挑戦。チェックをビット演算に切り替える。

until (n = $<.gets.to_i).zero?
  field = Array.new(n) {$<.gets.chomp}
  field.map! {|st| eval("0b" + st.gsub(/\./, "0").gsub(/\*/, "1"))}
  max = 0
  
  n.times do |y|
    l = field[y]
    break unless n - y > max
    (n - y).times do |i|
      l |= field[y + i]
      if l.to_s(2).rjust(n, "0").include?("0" * (i + 1))
        max = i + 1 if i + 1 > max
      end
    end
  end
  puts max
end

いちおう通ったけれども、3.91秒もかかってしまった。判定時にわざわざ文字列に直しているのがよくないのだけれど。
判定時に文字列を使わないバージョンも作ってみたのだが、余計に遅くなってしまった。正解者の結果を見ると 3.91秒というのは真ん中くらいで、そんなに悪い数字ではなかったようだ。Ruby だとしようがないのね。
 

0093 Leap Year

stack = []
until (years = $<.gets.split.map(&:to_i)) == [0, 0]
  is_uruu = ->(year) {
    (year % 4).zero? and ((year % 100).nonzero? or (year % 400).zero?)
  }
  result = (years.first..years.last).map {|i| is_uruu.(i) ? i : nil}.compact
  result << "NA" if result.empty?
  stack << result.join("\n") 
end
print stack.join("\n\n") + "\n"

 

0094 Calculation of Area

a, b = $<.gets.split.map(&:to_i)
printf "%.5f\n", a * b / 3.305785

 

0095 Surf Smelt Fishing Contest

$<.gets
data = $<.readlines.map {|l| l.split.map(&:to_i)}.sort_by(&:last)
max = data.last.last
num = data.select {|a| a.last == max}.sort_by(&:first).first.first
puts "#{num} #{max}"

sort_bysort と書くタイポがあって、なかなか気づけなかった。
 

0096 Sum of 4 Integers II

L = 1000
@memo = {}

def doit(s, n = 1)
  return (s <= L) ? 1 : 0 if n == 4
  key = [s, n]
  return @memo[key] if @memo.has_key?(key)
  co = 0
  a = (s <= L) ? s : L
  (0..a).each do |i|
    co += doit(s - i, n + 1)
  end
  @memo[key] = co
end

$<.readlines.map(&:to_i).each do |s|
  puts doit(s)
end

これだと時間オーバー。メモ化はしているのだけれど、もっと工夫しないといけない。

L = 1000
memo = {}

f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6}
f2 = ->(n) {(n ** 2 + 3 * n + 2) / 2}
f3 = ->(n) {n + 1}

f = ->(s, n) {
  case n
  when 1 then f1.(s)
  when 2 then f2.(s)
  when 3 then f3.(s)
  when 4 then 1
  else nil
  end
}

doit = ->(s, n = 1) {
  co = 0
  return f.(s, n) if s <= L
  return 0 if n == 4
  
  key = [s, n]
  return memo[key] if memo.has_key?(key)
  
  (0..L).each do |i|
    co += doit.(s - i, n + 1)
  end
  memo[key] = co
}

$<.readlines.map(&:to_i).each do |s|
  puts doit.(s)
end

これも時間オーバーだが、正しい答えを出すようだ。これがひな型になる。

f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6}
f2 = ->(n) {
  n1 = n - 1000
  (335337002 + 1004001 * n1 + 998 * n1 ** 2 - n1 ** 3) / 2
}
f3 = ->(n) {
  n1 = n - 2001
  (1337336000 - 4002 * n1 - 1999 * n1 ** 2 + n1 ** 3) / 2
}
f4 = ->(n) {
  n1 = n - 3002
  (999999000 - 2999999 * n1 + 3000 * n1 ** 2 - n1 ** 3) / 6
}

$<.readlines.map(&:to_i).each do |s|
  result = case s
           when    0..1000 then f1.(s)
           when 1001..2001 then f2.(s)
           when 2002..3002 then f3.(s)
           when 3003..4000 then f4.(s)
           end
  puts result
end

ほとんどインチキ。瞬殺である。WolframAlpha に助けを借りたのはナイショ。
他の人の回答。

MAX_SUM = 4000
MAX_I = 1000
K = 4
 
$sn_cache = Array.new(K + 1) {[]}
 
def check_sum(k, n)
  unless $sn_cache[k][n]
    count = 0
    max_i = [MAX_I, n].min
 
    (0..max_i).each do |i|
      count += check_sum(k - 1, n - i)
    end
 
    $sn_cache[k][n] = count
  end
  
  $sn_cache[k][n]
end
 
$sn_cache[1] = Array.new(MAX_I + 1, 1) + Array.new(MAX_SUM - MAX_I, 0)
 
while (line = gets)
  n = line.chomp.to_i
  puts check_sum(K, n)
end

これで 0.81秒なのだが、自分の最初の答えとよく似ている。しかし、自分のだと 6.51秒で時間オーバー。どこがちがうのだろう。
わかった、メモ化の際の配列の作り方がちがっているのだ。ハッシュを多重配列に直す。

L = 1000
@memo = Array.new(3) {[]}

def doit(s, n = 1)
  return (s <= L) ? 1 : 0 if n == 4
  return @memo[n - 1][s] if @memo[n - 1][s]
  co = 0
  a = (s <= L) ? s : L
  (0..a).each do |i|
    co += doit(s - i, n + 1)
  end
  @memo[n - 1][s] = co
end

$<.readlines.map(&:to_i).each do |s|
  puts doit(s)
end

これだけのことで 0.83秒で解けた。うーん、めっちゃ勉強になるなあ。
この最後のコードがいちばん好きだな。
なお、メモ化をハッシュにして、キーを key = "#{s},#{n}" という感じにしてやってもまあまあいけて、2.25秒で出来た。しかし、数字でいける場合はやはり配列が速いのは当り前か。
 

0097 Sum of Integers II

L = 100
@memo = Array.new(9) {Array.new(101) {[]}}

def solve(num, start, sum)
  return 0 if sum < 0 or start > L
  return (start <= sum and sum <= L) ? 1 : 0 if num == 1
  a = @memo[num - 1][start][sum]
  return a if a
  
  co = 0
  lim = [L, (2 * sum - num ** 2 + num) / (2 * num)].min
  (start..lim).each do |i|
    co += solve(num - 1, i + 1, sum - i)
  end
  @memo[num - 1][start][sum] = co
end
  
until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  puts solve(a.first, 0, a.last)
end

1.11秒かかった。lim を求めるのは少し凝ってみた。lim = [L, sum].min とやるより少し効率がよい。
 

0098 Maximum Sum Sequence II

matrix = Array.new(n = $<.gets.to_i) {$<.gets.split.map(&:to_i)}
max = -Float::INFINITY
memo = {}

try = ->(x, y, w, h) {
  return 0 if x >= n or y >= n or w <= 0 or h <= 0
  key = "#{x},#{y},#{w},#{h}"
  return memo[key] if memo[key]
  
  if h == 1 and w == 1
    num = matrix[y][x]
  else
    try.(x, y + 1, w, h - 1)
    try.(x, y    , w, h - 1)
    try.(x + 1, y, w - 1, h)
    try.(x    , y, w - 1, h)
    num = try.(x, y, 1, 1) + try.(x + 1, y, w - 1, 1) +
          try.(x, y + 1, 1, h - 1) + try.(x + 1, y + 1, w - 1, h - 1)
  end
  max = num if num > max
  memo[key] = num
}

try.(0, 0, n, n)
puts max

メモ化しても時間オーバー。
他の人の回答(参照)を見る。コードは自分の好みに改変してあります。

n = $<.gets.to_i
matrix = (1..n).map { $<.gets.split.map(&:to_i) }
# 各行の数字を左から加算していった配列
accum = matrix.map {|row| row.inject([0]) {|s, x| s + [s[-1] + x]} }
 
max = 0 
[*1..n].repeated_combination(2) do |i, j|
  sum = 0 
  (0..n - 1).each do |k|
    sum += accum[k][j] - accum[k][i - 1]
    max = sum if sum > max
    sum = 0 if sum < 0
  end
end
 
matrix.flatten!
puts matrix.any? {|x| x >= 0} ? max : matrix.max

瞬殺。うーん、すごい、これは思いつかなかった。でもあらかじめ数字を加算しておいた配列を作るのいうのは、確かに時々見る手法。
 

0099 Surf Smelt Fishing Contest II

Node = Struct.new(:key, :value, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key, value)
    unless @root
      @root = Node.new(key, value)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key, value)
          break
        end
      elsif key > node.key
        if node.right
          node = node.right
        else
          node.right = Node.new(key, value)
          break
        end
      else
        if block_given?
          node.value = yield(key, node.value, value)
        else
          node.value = value
        end
        break
      end
    end
  end
  
  def []=(key, value)
    insert(key, value)
  end
  
  def search(key)
    node = @root
    while node
      if key < node.key
        node = node.left
      elsif key > node.key
        node = node.right
      else
        return node
      end
    end
    nil
  end
  
  def [](key)
    search(key)&.value
  end
  
  def delete(key)
    delete_min = ->(node) {
      return node.right unless node.left
      node.left = delete_min.(node.left)
      node
    }
    search_min = ->(node) {
      node = node.left while node.left
      node
    }
    del = ->(node) {
      if node
        if key == node.key
          if node.left.nil?
            return node.right
          elsif node.right.nil?
            return node.left
          else
            min_node = search_min.(node.right)
            node.key = min_node.key
            node.value = min_node.value
            node.right = delete_min.(node.right)
          end
        elsif key < node.key
          node.left  = del.(node.left)
        else
          node.right = del.(node.right)
        end
      end
      node
    }
    
    @root = del.(@root)
  end
  
  def maximum
    search_max = ->(node) {
      node = node.right while node.right
      node
    }
    raise "error" unless @root
    node = search_max.(@root)
    raise "error" unless node
    node.key
  end
end

n, q = $<.gets.split.map(&:to_i)
entry = []
fish_num = Hash.new(0)
t = Tree.new

delete = ->(fish, member) {
  t[fish] -= [member]
  t.delete(fish) if t[fish].empty?
}

q.times do
  member, fs = $<.gets.split.map(&:to_i)
  tmp = fish_num[member]
  fish_num[member] += fs
  t.insert(fish_num[member], [member]) {|k, v1, v2| v1 + v2}
  if entry.include?(member)
    delete.(tmp, member)
  else
    entry << member
  end
  max_fish = t.maximum
  puts "#{t[max_fish].sort.first} #{max_fish}"
end

惜しい、22課題中21課題までいって時間オーバー(9秒99)。二分探索木を実装して頑張った。しかしこれではダメのようだから、平衡二分探索木を実装しないといけないのか。
いや、シンプルに考え直してみる。

fish = Hash.new(0)
max = 0
max_fishers = []
selected_fisher = nil

n, q = $<.gets.split.map(&:to_i)
q.times do
  a, v = $<.gets.split.map(&:to_i)
  fish[a] += v
  if v > 0
    if fish[a] > max
      max = fish[a]
      puts "#{a} #{max}"
      max_fishers = [a]
      selected_fisher = a
    elsif fish[a] == max
      max_fishers << a
      puts "#{selected_fisher = max_fishers.min} #{max}"
    else
      puts "#{selected_fisher} #{max}"
    end
  else
    if fish[a] - v == max
      if max_fishers.size == 1
        max = fish.values.max
        max_fishers = fish.keys.select {|k| fish[k] == max}
        puts "#{selected_fisher = max_fishers.min} #{max}"
      else
        max_fishers.delete(a)
        puts "#{selected_fisher = max_fishers.min} #{max}"
      end
    else
      puts "#{selected_fisher} #{max}"
    end
  end
end

これで 0.23秒で通った。なんと Ruby での通過者中最速だった。C と C++ 以外には負けないぜ!