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人だけ。よくできたな。