AOJ (Introduction to Algorithms and Data Structures)

AIZU ONLINE JUDGE: Programming Challenge
 
ALDS1_1_A

#挿入ソート
gets
ar = gets.split.map(&:to_i)
n = ar.size
putout = ->{puts ar.join(" ")}

putout.()
1.upto(n - 1) do |i|
  v = ar[i]
  j = i - 1
  while j >= 0 and ar[j] > v
    ar[j + 1] = ar[j]
    j -= 1
  end
  ar[j + 1] = v
  putout.()
end

ALDS1_1_B

#最大公約数
gcd = ->(x, y) {
  return x if y.zero?
  gcd.(y, x % y)
}
puts gcd.(*gets.split.map(&:to_i))

ALDS1_1_C

#高速な素数の判定
is_prime = ->(n) {
  return false if n < 2
  return true  if n == 2 or n == 3
  return false if (n % 2).zero? or (n % 3).zero?
  k, step = 5, 2
  guard = Math.sqrt(n).to_i
  while k <= guard
    return false if (n % k).zero?
    k += step
    step = 6 - step
  end
  true
}

gets
co = 0
$stdin.readlines.map(&:to_i).each {|num| co += 1 if is_prime.(num)}
puts co

ALDS1_1_D

#FX取引の利益の最大値
n = gets.to_i
r = []
n.times {r << gets.to_i}

min_r = r[0]
max = -Float::INFINITY
(n - 1).times do |i|
  a = r[i + 1]
  dif = a - min_r
  max = dif if dif > max
  min_r = a if a < min_r
end
puts max

 
ALDS1_2_A

#バブルソート
gets
ar = gets.split.map(&:to_i)
co = 0
(ar.size - 2).downto(0) do |i|
  (i + 1).times do |j|
    if ar[j] > ar[j + 1]
      ar[j], ar[j + 1] = ar[j + 1], ar[j]
      co += 1
    end
  end
end
puts ar.join(" ")
puts co

ALDS1_2_B

#選択ソート
gets
ar = gets.split.map(&:to_i)
l = ar.size
co = 0
(l - 1).times do |i|
  min = i
  (i + 1).upto(l - 1) {|j| min = j if ar[j] < ar[min]}
  ar[min], ar[i] = ar[i], ar[min]
  co += 1 if i != min
end
puts ar.join(" ")
puts co

ALDS1_2_C

n = gets.to_i
cards = gets.split

value = ->(card) {
  card[1].to_i
}

bubble_sort = ->(ar) {
  n.times do |i|
    (n - 1).downto(i + 1) do |j|
      ar[j], ar[j - 1] = ar[j - 1], ar[j] if value.(ar[j]) < value.(ar[j - 1])
    end
  end
  ar
}

selection_sort = ->(ar) {
  result = "Stable"
  n.times do |i|
    minj = i
    f = false
    (i + 1).upto(n - 1) do |j|
      f = true if value.(ar[i]) == value.(ar[j])
      if value.(ar[j]) < value.(ar[minj])
        minj = j
        result = "Not stable" if f
      end
    end
    ar[i], ar[minj] = ar[minj], ar[i]
  end
  return ar, result
}

puts bubble_sort.(cards.dup).join(" ")
puts "Stable"
ar, result = selection_sort.(cards)
puts ar.join(" ")
puts result

ALDS1_2_D
制限時間ギリギリだった。

#シェルソート
n = gets.to_i
a = Array.new(n, 0)
n.times {|i| a[i] = gets.to_i}
cnt = 0

insertion_sort = ->(a, g) {
  g.upto(n - 1) do |i|
    v = a[i]
    j = i - g
    while j >= 0 and a[j] > v
      a[j + g] = a[j]
      j -= g
      cnt += 1
    end
    a[j + g] = v
  end
}

i = (n == 1) ? 1 : n / 2
g = []
while i > 0
  g << i
  i /= 2
end
m = g.size
g.each {|i| insertion_sort.(a, i)}

puts m
puts g.join(" ")
puts cnt
puts a

 
ALDS1_3_A

#逆ポーランド記法
data = gets.chomp.split
stack = []

while (x = data.shift)
  if /^[\+\-\*]$/.match(x)
    a, b = stack.pop, stack.pop
    stack << eval(b + x + a).to_s
  else
    stack << x
  end
end
puts stack.last

ALDS1_3_B

#ラウンドロビンスケジューリング
n, q = gets.split.map(&:to_i)
queue = []
n.times do
  name, time = gets.chomp.split
  queue << [name, time.to_i]
end
t = 0

while (x = queue.shift)
  if x[1] <= q
    t += x[1]
    puts "#{x[0]} #{t}"
  else
    t += q
    queue << [x[0], x[1] - q]
  end
end

ALDS1_3_C
制限時間オーバーしているのに許されている(笑)。でも Ruby でこれ以上速くってたぶん無理だよね。

n = gets.to_i
commands = []
n.times {commands << gets.chomp.split}
list = []

commands.each do |co|
  case co[0]
  when "insert"
    list.unshift(co[1])
  when "delete"
    i = list.index(co[1])
    list.delete_at(i) if i
  when "deleteFirst"
    list.shift
  when "deleteLast"
    list.pop
  end
end
puts list.join(" ")

ALDS1_3_D
むずかしかったー。何とか正解。よくこんなの解けたな。模範解答はどうなのだろう。
このアルゴリズムだと highest.() を何度も呼ばないといけない。これが無駄なのだけれど、O(n) でいけるのかねえ。

#Areas on the Cross-Section Diagram
diagram = gets.chomp.chars

upper_skip = ->{
  loop do
    a = diagram[0]
    return false if a == "\\"
    return true unless a
    diagram.shift
  end
}

downer_skip = ->(target_height) {
  height = index = 0
  until height == target_height
    height -= 1 if diagram.shift == "\\"
    index += 1
  end
  index
}

highest = ->{
  index = height = 0
  max_height = -Float::INFINITY 
  diagram.size.times do |j|
    case diagram[j]
    when "\\"
      height -= 1
    when "/"
      height += 1
      max_height, index = height, j if max_height < height
      return [0, j] if height.zero?
    end
  end
  [max_height, index]
}

calc_area = ->(from, to) {
  depth = area = 0
  from.upto(to) do
    case diagram.shift
    when "\\"
      area += depth + 1/2r
      depth += 1
    when "_"
      area += depth
    when "/"
      depth -= 1
      area += depth + 1/2r
    end
  end
  area.to_i
}


pools = []
loop do
  break if upper_skip.()
  height, last_index = highest.()
  if height == -Float::INFINITY
    break
  else
    first_index = downer_skip.(height)
    pools << calc_area.(first_index, last_index)
  end
end

if pools.empty?
  puts 0, 0
else
  puts pools.inject(&:+)
  puts pools.size.to_s + " " + pools.join(" ")
end

別解。思いついたのだが、こちらの方が遅い。コードも読みにくい。

diagram = gets.chomp.chars

search = ->{
  max = min = height = 0
  diagram.each_with_index do |x, i|
    case x
    when "\\"
      height -= 1
      min = height if height < min
    when "/"
      height += 1
      max = height if height > max
    end
  end
  [max - min, max]
}

n, level = search.()
table = Array.new(n) {[]}

diagram.each_with_index do |x, i|
  case x
  when "\\"
    table[level] << i
    level += 1
  when "/"
    level -= 1
    a = table[level].last
    table[level] << i if a
  end
  table
end
table.map! do |one_level|
  one_level.each_slice(2).with_object([]) {|x, ar| ar << x if x.size == 2}
end

calc_area = ->(pair, level) {
  area = pair[1] - pair[0]
  return area if level == n
  one_level = table[level]
  table[level].each do |downer_pair|
    if pair[0] < downer_pair[0] and downer_pair[1] < pair[1]
      one_level -= [downer_pair]
      area += calc_area.(downer_pair, level + 1)
    end
  end
  table[level] = one_level
  area
}

pools = []
solve = ->{
  min = [[Float::INFINITY, 0], 0]
  table.each_with_index do |one_level, i|
    next if one_level.empty?
    pair = one_level[0]
    min = [pair, i] if pair[0] < min[0][0]
  end
  table[min[1]] -= [min[0]]
  pools << calc_area.(min[0], min[1] + 1) if min[0][0] != Float::INFINITY
  solve.() unless table.flatten.empty?
}

solve.() unless table.empty?

if pools.empty?
  puts 0, 0
else
  puts pools.inject(&:+)
  puts pools.size.to_s + " " + pools.join(" ")
end

模範解答的なのは例えばこれ。すごいですね…。
 
ALDS1_4_A

#Linear Search
n = gets.to_i
s = gets.split.map(&:to_i)
q = gets.to_i
t = gets.split.map(&:to_i)

count = 0
s.each do |x|
  t1 = t
  t.each do |y|
    if x == y
      count += 1
      t1 -= [y]
      break
    end
  end
  t = t1
end
puts count

ALDS1_4_B

#Binary Search
n = gets.to_i
s = gets.split.map(&:to_i)
q = gets.to_i
t = gets.split.map(&:to_i).sort

count = 0
i = j = 0
while i < n and j < q
  if s[i] == t[j]
    count += 1
    i += 1
    j += 1
  elsif s[i] < t[j]
    i += 1
  else
    j += 1
  end
end
puts count

ALDS1_4_C
最初時間オーバーばかりしていて苦労してもダメだったが、解決策はコロンブスの卵だった…。

#Dictionary
require 'set'

n = gets.to_i
commands = []
n.times {commands << gets.chomp.split}

dict = Set.new
commands.each do |c, str|
  case c
  when "insert"
    dict << str
  when "find"
    puts dict.include?(str) ? "yes" : "no"
  end
end

ALDS1_4_D
むずかしい。模範解答を参考にした。

n, k = gets.split.map(&:to_i)
weights = []
n.times {weights << gets.to_i}

#最大積載量pのとき積める荷物の数
pack_num = ->(p) {
  i = truck_n = 0
  while truck_n < k
    truck_w = 0
    while i < n
      truck_w += weights[i]
      break if truck_w > p.to_i
      i += 1
    end
    truck_n += 1
  end
  i
}

left, right = 0.0, 100_000 * 10_000
until right - left < 1
  mid = (left + right) / 2
  num = pack_num.(mid)
  if num >= n
    right = mid
  else
    left  = mid
  end
end
puts right.to_i

 
ALDS1_5_A
制限時間以内にできない。模範解答を参考にした。メモ化は自分で加えた。

#全探索
n = gets.to_i
a = gets.split.map(&:to_i)
q = gets.to_i
m = gets.split.map(&:to_i)

memo = {}

solve = ->(i, m) {
  return memo[[i, m]] if memo.has_key?([i, m])
  return true if m.zero?
  return false if i >= n || m < 0
  memo[[i, m]] = solve.(i + 1, m) || solve.(i + 1, m - a[i])
}

m.each do |target|
  puts solve.(0, target) ? "yes" : "no"
end

ALDS1_5_B
指定してある擬似コードどおりにコーディングすると、時間オーバーになるのですが…。そもそも擬似コードに無駄がある。
Rubyでの高速な解答例を見ると、インチキしてあるのが多い。ひどいな。

#マージソート
n = gets.to_i
s = gets.split.map(&:to_i)
$co = 0

class Array
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result.push((a[0] <= b[0]) ? a.shift : b.shift)
      end
      result + a + b
    }
    
    l = length
    return self if l <= 1
    q = l / 2
    $co += l
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end

puts s.merge_sort.join(" ")
puts $co

ALDS1_5_C

#コッホ曲線
require 'matrix'
include Math

n = gets.to_i
rot = ->(v, θ) {
  t = θ / 180.0 * PI
  Matrix[[cos(t), -sin(t)], [sin(t), cos(t)]] * v
}
result = []

koch_curve = ->(p1, p2, level) {
  if level == n
    result << p1
    result << p2
  else
    l1 = (p2 - p1) / 3
    l2 = rot.(l1, 60)
    koch_curve.(p1, p3 = p1 + l1, level + 1)
    koch_curve.(p3, p4 = p3 + l2, level + 1)
    koch_curve.(p4, p5 = p3 + l1, level + 1)
    koch_curve.(p5, p2, level + 1)
  end
}

koch_curve.(Vector[0.0, 0.0], Vector[100.0, 0.0], 0)
([result[0]] + result + [result[-1]]).each_slice(2) do |a, _|
  printf "%.8f %.8f\n", a[0], a[1]
end

ALDS1_5_D
これはわからなかった。解答例を見てみたら、マージソートを使っている。なるほど。これはすごい。

#反転数
n = gets.to_i
a = gets.split.map(&:to_i)
$co = 0

class Array
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result << if a[0] <= b[0]
          a.shift
        else
          $co += a.size
          b.shift
        end
      end
      result + a + b
    }
    
    l = length
    return self if l <= 1
    q = l / 2
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end

a.merge_sort
puts $co

 
ALDS1_6_A

#計数ソート
n = gets.to_i
a = gets.split.map(&:to_i)

equal = Array.new(10001, 0)
n.times {|i| equal[a[i]] += 1}

equal[-1] = 0
10000.times {|i| equal[i] += equal[i - 1]}

result = Array.new(n)
n.times do |i|
  result[equal[a[i] - 1]] = a[i]
  equal[a[i] - 1] += 1
end

puts result.join(" ")

ALDS1_6_B

#分割
n = gets.to_i
a = gets.split.map(&:to_i)

class Array
  def partition
    x = self[-1]
    i = -1
    (size - 1).times do |j|
      if self[j] <= x
        i += 1
        self[i], self[j] = self[j], self[i]
      end
    end
    self[i + 1], self[-1] = self[-1], self[i + 1]
    i + 1
  end
end

r = a.partition
puts a[0, r].join(" ") + " [#{a[r]}] " + a[r + 1..-1].join(" ")

ALDS1_6_C
クイックソートの安定性は、安定なソートであるマージソートの結果と比較している。

#クイックソート
n = gets.to_i
cards = []
n.times do
  a, b = gets.chomp.split
  cards << [a, b.to_i]
end

class Array
  def partition(p, r)
    x = self[r][1]
    i = p - 1
    p.upto(r - 1) do |j|
      if self[j][1] <= x
        i += 1
        self[i], self[j] = self[j], self[i]
      end
    end
    self[i + 1], self[r] = self[r], self[i + 1]
    i + 1
  end
  
  def quick_sort(p, r)
    return if p >= r
    q = partition(p, r)
    quick_sort(p, q - 1)
    quick_sort(q + 1, r)
  end
  
  def merge_sort
    merge = ->(a, b) {
      result = []
      while a.size > 0 and b.size > 0
        result.push((a[0][1] <= b[0][1]) ? a.shift : b.shift)
      end
      result + a + b
    }
    
    l = length
    return self if l <= 1
    q = l / 2
    merge.(self[0...q].merge_sort, self[q..-1].merge_sort)
  end
end

another_cards = cards.merge_sort
cards.quick_sort(0, n - 1)
puts (cards == another_cards) ? "Stable" : "Not stable"
puts cards.map {|x| x.join(" ")}

 
ALDS1_7_A

#根付き木
n = gets.to_i
tree = Struct.new(:parent, :depth, :type, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = ar[2..-1]
  node[ar[0]].parent = -1
  node[ar[0]].type = "leaf"
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i}
  nd.type = "internal node" unless nd.children.empty?
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}
node[root_index].type = "root"

search = ->(index, depth) {
  node[index].depth = depth
  children = node[index].children
  return if children.empty?
  children.each {|child| search.(child, depth + 1)}
}
search.(root_index, 0)

node.each_with_index do |nd, i|
  puts "node #{i}: parent = #{nd.parent}, depth = #{nd.depth}, #{nd.type}, #{nd.children.inspect}"
end

ALDS1_7_B

#二分木
n = gets.to_i
tree = Struct.new(:parent, :sibling, :degree, :depth, :height, :type, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = a = ar[1..-1].reject {|x| x == -1}
  node[ar[0]].degree = a.size
  node[ar[0]].parent = -1
  node[ar[0]].sibling = -1
  node[ar[0]].type = "internal node"
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i}
  case nd.degree
  when 0
    nd.type = "leaf"
    nd.height = 0
  when 1
    node[nd.children[0]].sibling = -1
  when 2
    node[nd.children[0]].sibling = nd.children[1]
    node[nd.children[1]].sibling = nd.children[0]
  end
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}
node[root_index].type = "root"

search = ->(index, depth) {
  node[index].depth = depth
  children = node[index].children
  height_max = 0
  children.each do |child|
    h = search.(child, depth + 1) + 1
    height_max = h if h > height_max
  end
  node[index].height = height_max
}
search.(root_index, 0)

node.each_with_index do |nd, i|
  puts "node #{i}: parent = #{nd.parent}, sibling = #{nd.sibling}, degree = #{nd.degree}, depth = #{nd.depth}, height = #{nd.height}, #{nd.type}"
end

上はたまたま通過したけれども、不備がある。改善したコード。

n = gets.to_i
tree = Struct.new(:parent, :sibling, :degree, :depth, :height, :type, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = ar[1..-1]
  node[ar[0]].degree = ar[1..-1].reject {|x| x == -1}.size
  node[ar[0]].parent = -1
  node[ar[0]].sibling = -1
  node[ar[0]].type = "internal node"
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i unless child == -1}
  case nd.degree
  when 0
    nd.type = "leaf"
    nd.height = 0
  else
    node[nd.children[0]].sibling = nd.children[1] unless nd.children[0] == -1
    node[nd.children[1]].sibling = nd.children[0] unless nd.children[1] == -1
  end
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}
node[root_index].type = "root"

search = ->(index, depth) {
  node[index].depth = depth
  children = node[index].children.reject {|x| x == -1}
  return 0 if children.empty?
  height_max = 0
  children.each do |child|
    h = search.(child, depth + 1) + 1
    height_max = h if h > height_max
  end
  node[index].height = height_max
}
search.(root_index, 0)

node.each_with_index do |nd, i|
  puts "node #{i}: parent = #{nd.parent}, sibling = #{nd.sibling}, degree = #{nd.degree}, depth = #{nd.depth}, height = #{nd.height}, #{nd.type}"
end

ALDS1_7_C

#木の巡回
n = gets.to_i
tree = Struct.new(:parent, :children)
node = Array.new(n) {tree.new}
n.times do
  ar = gets.split.map(&:to_i)
  node[ar[0]].children = ar[1..-1]
  node[ar[0]].parent = -1
end

node.each_with_index do |nd, i|
  nd.children.each {|child| node[child].parent = i unless child == -1}
end

root_index = 0
node.each_with_index {|nd, i| root_index = i if nd.parent == -1}

preorder = ->(root) {
  @result << root
  a = node[root].children[0]
  preorder.(a) unless a == -1
  a = node[root].children[1]
  preorder.(a) unless a == -1
}

inorder = ->(root) {
  a = node[root].children[0]
  inorder.(a) unless a == -1
  @result << root
  a = node[root].children[1]
  inorder.(a) unless a == -1
}

postorder = ->(root) {
  a = node[root].children[0]
  postorder.(a) unless a == -1
  a = node[root].children[1]
  postorder.(a) unless a == -1
  @result << root
}

def putout(title)
  @result = []
  puts title
  yield
  puts @result.map {|x| " " + x.to_s}.join
end

putout("Preorder")  {preorder .(root_index)}
putout("Inorder")   {inorder  .(root_index)}
putout("Postorder") {postorder.(root_index)}

ALDS1_8_A

#二分探索木I
node = Struct.new(:key, :parent, :left, :right)
root = nil

insert = ->(z) {
  pa = nil
  x = root
  while x
    pa = x
    x = (z.key < x.key) ? x.left : x.right
  end
  z.parent = pa
  
  if pa.nil?
    root = z
  elsif z.key < pa.key
    pa.left  = z
  else
    pa.right = z
  end
}

inorder = ->(x) {
  a = x.left
  inorder.(a) if a
  print " " + x.key.to_s
  a = x.right
  inorder.(a) if a
}

preorder = ->(x) {
  print " " + x.key.to_s
  a = x.left
  preorder.(a) if a
  a = x.right
  preorder.(a) if a
}

gets.to_i.times do
  command = gets.split(" ")
  case command[0]
  when "insert"
    z = node.new
    z.key = command[1].to_i
    insert.(z)
  when "print"
    inorder .(root)
    puts
    preorder.(root)
    puts
  end
end

ALDS1_8_B
これだとタイムオーバーしてしまう。

node = Struct.new(:key, :parent, :left, :right)
root = nil

insert = ->(z) {
  pa = nil
  x = root
  while x
    pa = x
    x = (z.key < x.key) ? x.left : x.right
  end
  z.parent = pa
  
  if pa.nil?
    root = z
  elsif z.key < pa.key
    pa.left  = z
  else
    pa.right = z
  end
}

inorder = ->(x) {
  a = x.left
  inorder.(a) if a
  print " " + x.key.to_s
  a = x.right
  inorder.(a) if a
}

preorder = ->(x) {
  print " " + x.key.to_s
  a = x.left
  preorder.(a) if a
  a = x.right
  preorder.(a) if a
}

memo = []

gets.to_i.times do
  command = gets.split(" ")
  case command[0]
  when "insert"
    z = node.new
    memo << z.key = command[1].to_i
    insert.(z)
  when "print"
    inorder .(root)
    puts
    preorder.(root)
    puts
  when "find"
    puts memo.include?(command[1].to_i) ? "yes" : "no"
  end
end

他の回答を参考にして find.() を書き直した。find.() は二分木の特性を利用して最短でのルートで探索する。ついでに insert.() も修正。

node = Struct.new(:key, :left, :right)
root = nil

insert = ->(pa, z) {
  if pa.key > z
    if pa.left
      insert.(pa.left, z)
    else
      pa.left = node.new(z)
    end
  else
    if pa.right
      insert.(pa.right, z)
    else
      pa.right = node.new(z)
    end
  end
}

inorder = ->(x) {
  a = x.left
  inorder.(a) if a
  print " " + x.key.to_s
  a = x.right
  inorder.(a) if a
}

preorder = ->(x) {
  print " " + x.key.to_s
  a = x.left
  preorder.(a) if a
  a = x.right
  preorder.(a) if a
}

find = ->(x, k, bool) {
  if x.key == k
    bool = true
  else
    if x.left && x.key > k
      bool = find.(x.left,  k, bool)
    end
    if x.right && x.key < k
      bool = find.(x.right, k, bool)
    end
  end
  bool
}

gets.to_i.times do
  command = gets.split(" ")
  case command[0]
  when "insert"
    if root
      insert.(root, command[1].to_i)
    else
      root = node.new(command[1].to_i)
    end
  when "print"
    inorder .(root)
    puts
    preorder.(root)
    puts
  when "find"
    puts find.(root, command[1].to_i, false) ? "yes" : "no"
  end
end