AOJ(Introduction to Algorithms and Data Structures)その1

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.map {$<.gets.to_i}

min_r = r.first
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

別様にやってみた(2019/3/12)。

#根付き木
Node = Struct.new(:id, :c, :parent, :depth, :type)

nodes = $<.gets.to_i.times.map do
  id, k, *c = $<.gets.split.map(&:to_i)
  Node.new(id, c)
end.sort_by(&:id)

h = nodes.map {|n| [n.id, n]}.to_h
nodes.each {|n| n.c.each {|c| h[c].parent = n.id} }

root = nodes.find {|n| !n.parent}
root.parent = -1

search = ->(node, depth) {
  node.depth = depth
  if node.c.empty?
    node.type = "leaf"
  else
    node.type = "internal node"
    node.c.each {|c| search.(h[c], depth + 1)}
  end
}
search.(root, 0)
root.type = "root"

puts nodes.map {|n| "node #{n.id}: parent = #{n.parent}, depth = #{n.depth}, #{n.type}, #{n.c}"}

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

別様にやってみた。(2019/3/12)

#二分木
n = $<.gets.to_i
Node = Struct.new(:id, :left, :right, :depth, :type, :sibling, :degree, :parent, :height)

nodes = n.times.map { Node.new(*$<.gets.split.map(&:to_i)) }.sort_by(&:id)
root = [*0...n] - nodes.flat_map {|n| [n.left, n.right]}.uniq
root = nodes[root.first]
h = nodes.map {|n| [n.id, n]}.to_h

build_tree = ->(node, depth) {
  node.depth = depth
  l, r = node.left, node.right
  degree = 0
  hi1 = hi2 = 0
  try = ->(next_node, s) {
    next_node.sibling = s
    next_node.parent = node.id
    build_tree.(next_node, depth + 1)
    degree += 1
    next_node.height + 1
  }
  hi1 = try.(h[l], r) if l != -1
  hi2 = try.(h[r], l) if r != -1
  node.degree = degree
  if l == -1 and r == -1
    node.height = 0
    node.type = "leaf"
  else
    node.height = [hi1, hi2].max
    node.type = "internal node"
  end
}
build_tree.(root, 0)

root.type = "root"
root.sibling = -1
root.parent = -1

puts nodes.map {|n| "node #{n.id}: parent = #{n.parent}, sibling = #{n.sibling}, " +
  "degree = #{n.degree}, depth = #{n.depth}, height = #{n.height}, #{n.type}"}

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

別様にやってみた。(201/3/12)

#二分探索木I
Node = Struct.new(:key, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key)
    unless @root
      @root = Node.new(key)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key)
          break
        end
      else
        if node.right
          node = node.right
        else
          node.right = Node.new(key)
          break
        end
      end
    end
  end
  
  def preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key = $<.gets.split
  case com
  when "insert" then t.insert(key.to_i)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  end
end

2.33秒かかった。

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

別様にやってみた。(2019/3/12)

#二分探索木II
Node = Struct.new(:key, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key)
    unless @root
      @root = Node.new(key)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key)
          break
        end
      else
        if node.right
          node = node.right
        else
          node.right = Node.new(key)
          break
        end
      end
    end
  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 preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key = $<.gets.split
  case com
  when "insert" then t.insert(key.to_i)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  when "find"
    puts t.search(key.to_i) ? "yes" : "no"
  end
end

2.04秒かかった。

ALDS1_8_C

#二分探索木III
Node = Struct.new(:key, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key)
    unless @root
      @root = Node.new(key)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key)
          break
        end
      else
        if node.right
          node = node.right
        else
          node.right = Node.new(key)
          break
        end
      end
    end
  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 delete(key)
    delete_min = ->(node) {
      return node.right unless node.left
      node.left = delete_min.(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.right = delete_min.(node.right)
          end
        elsif key < node.key
          node.left  = del.(node.left)
        else
          node.right = del.(node.right)
        end
      end
      return node
    }
    
    @root = del.(@root)
  end
  
  def preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  private
  
  def search_min(node)
    node = node.left while node.left
    node
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key = $<.gets.split
  key = key.to_i
  case com
  when "insert" then t.insert(key)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  when "find"
    puts t.search(key) ? "yes" : "no"
  when "delete" then t.delete(key)
  end
end

2.15秒かかった。

ALDS1_8_D

#Treap
Node = Struct.new(:key, :priority, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key, priority)
    unless @root
      @root = Node.new(key, priority)
      return
    end
    insert = ->(node) {
      return Node.new(key, priority) unless node
      return node if key == node.key
      if key < node.key
        node.left  = insert.(node.left)
        node = right_rotate(node) if node.priority < node.left.priority
      else
        node.right = insert.(node.right)
        node = left_rotate(node)  if node.priority < node.right.priority
      end
      node
    }
    @root = insert.(@root)
  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 delete(key)
    delete1 = nil
    
    delete = ->(node) {
      return nil unless node
      if key < node.key
        node.left  = delete.(node.left)
      elsif key > node.key
        node.right = delete.(node.right)
      else
        return delete1.(node)
      end
      node
    }
    delete1 = ->(node) {
      return nil if !node.left and !node.right
      node = if node.left.nil?
        left_rotate(node)
      elsif node.right.nil?
        right_rotate(node)
      else
        if node.left.priority > node.right.priority
          right_rotate(node)
        else
          left_rotate(node)
        end
      end
      delete.(node)
    }
    @root = delete.(@root)
  end
  
  def right_rotate(node)
    tmp = node.left
    node.left = tmp.right
    tmp.right = node
    tmp
  end
  
  def left_rotate(node)
    tmp = node.right
    node.right = tmp.left
    tmp.left = node
    tmp
  end
  
  def preorder
    traverse = ->(node) {
      if node
        yield(node.key)
        traverse.(node.left)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
  
  def inorder
    traverse = ->(node) {
      if node
        traverse.(node.left)
        yield(node.key)
        traverse.(node.right)
      end
    }
    traverse.(@root)
  end
end

t = Tree.new

$<.gets.to_i.times do
  com, key, priority = $<.gets.split
  key = key.to_i
  priority = priority.to_i
  case com
  when "insert" then t.insert(key, priority)
  when "print"
    t.inorder  {|key| print " #{key}"}
    puts
    t.preorder {|key| print " #{key}"}
    puts
  when "find"
    puts t.search(key) ? "yes" : "no"
  when "delete" then t.delete(key)
  end
end

2.32秒かかった。できているのは Ruby で 3人だけ。よくできたな。