AOJ（ALDS）その2

AIZU ONLINE JUDGE: Programming Challenge
　

ALDS1_9_A Complete Binary Tree

#完全二分木
$<.gets
given = [nil] + $<.gets.split.map(&:to_i)
a = nil
 
given.drop(1).each_with_index do |key, i|
  j = i + 1
  str = "node #{j}: key = #{key}, "
  str += "parent key = #{a}, " if (a = given[j / 2])
  str += "left key = #{a}, "   if (a = given[j * 2])
  str += "right key = #{a}, "  if (a = given[j * 2 + 1])
  puts str
end

ALDS1_9_B Maximum Heap

#最大ヒープ
h = $<.gets.to_i
given = [nil] + $<.gets.split.map(&:to_i)
 
max_heapify = ->(i) {
  l, r = i * 2, i * 2 + 1
  largest = (l <= h and given[l] > given[i]) ? l : i
  largest = r if r <= h and given[r] > given[largest]
  unless largest == i
    given[i], given[largest] = given[largest], given[i]
    max_heapify.(largest)
  end
}
 
(h / 2).downto(1) {|i| max_heapify.(i)}
puts given.drop(1).map {|i| " #{i}"}.join

ALDS1_9_C Priority Queue

#優先度付きキュー
class MaxHeap
  def initialize
    @heap = [nil]
    @size = 0
  end
   
  def insert(key)
    @heap << key
    @size += 1
    up_heap(@size / 2)
  end
   
  def up_heap(i)
    return if i.zero?
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      up_heap(i / 2)
    end
  end
   
  def remove_root
    a = @heap[1]
    @heap[1] = @heap.pop
    @size -= 1
    down_heap(1)
    a
  end
   
  def down_heap(i)
    return if i > @size
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      down_heap(largest)
    end
  end
end
 
 
h = MaxHeap.new
 
$<.readlines.map {|l| l.chomp.split}.each do |command|
  case command[0]
  when "insert" then h.insert(command[1].to_i)
  when "extract" then puts h.remove_root
  when "end" then break
  else raise "error"
  end
end

ALDS1_10_A Fibonacci Number

#フィボナッチ数列
fib = Enumerator.new do |y|
  a, b = 1, 1
  loop do
    y << a
    a, b = b, a + b
  end
end
 
puts fib.take($<.gets.to_i + 1).last

ALDS1_10_B: Matrix Chain Multiplication

連鎖行列積問題（Matrix-Chain Multiplication problem）。

INF = (1 << 31) - 1

n = gets.to_i
ms = n.times.map {gets.split.map(&:to_i)}

dp = Array.new(n + 1) {Array.new(n + 1, 0)}
dim = [ms[0][0]] + ms.map(&:last)

2.upto(n) do |l|
  1.upto(n - l + 1) do |i|
    j = i + l - 1
    dp[i][j] = INF
    i.upto(j - 1) do |k|
      tmp = dp[i][k] + dp[j][k] + dp[k + 1][j] + dim[i - 1] * dim[k] * dim[j]
      dp[i][j] = [dp[i][j], tmp].min
    end
  end
end

puts dp[1][n]

ここのパクリ。むずかしい。
※参考
連鎖行列積問題 - Qiita
動的計画法４ 連鎖行列積 - Daily Tech Blog
連鎖行列積問題 : がぶ飲みミルク珈琲
※追記
わたしがパクったコードは、じつは『アルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書)』のパクリだったことがわかった。