AOJ（問題集）19

AIZU ONLINE JUDGE: Programming Challenge
　

0180 Demolition of Bridges

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  n, m = given
  bridges = m.times.map {$<.gets.split.map(&:to_i)}.sort_by(&:last)
  city = Array.new(n, false)
  city[0] = true
  appearance = 1
  total_cost = 0
  
  while appearance < n
    bridges.each_index do |i|
      a, b, cost = bridges[i]
      if city[a] or city[b]
        if !city[a]
          city[a] = true
          appearance += 1
          total_cost += cost
        elsif !city[b]
          city[b] = true
          appearance += 1
          total_cost += cost
        end
        bridges.delete_at(i)
        break
      end
    end
  end
  
  puts total_cost
end

「0072 Carden Lantern」とほぼ同じ問題（最小全域木を求める）。ここで使ったのは「プリム法」というらしい。
　

0181 Bookshelf

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  book = n.times.map {$<.gets.to_i}
  narrowest = Limit
  pool = []
  
  try = ->(from, h, pool) {
    return if !pool.empty? and pool.last > narrowest
    if h > m
      if from == n
        a = pool.max
        narrowest = a if a < narrowest
      end
    else
      width = 0
      (from...n).each do |i|
        width += book[i]
        try.(i + 1, h + 1, pool + [width])
      end
      if narrowest == Limit
        a = pool.max
        narrowest = a if a < narrowest
      end
    end
  }
  try.(0, 1, [])
  puts narrowest
end

7.73秒で時間オーバー。

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  smallest = 1500000
  m = n if n < m
  
  if m == 1
    puts books.sum
    next
  end
  
  [*1..n - 1].combination(m - 1) do |sep|
    i = 0
    shelf = []
    sep.each do |j|
      shelf << books[i...j]
      i = j
    end
    shelf << books[i..-1]
    
    len = shelf.map {|a| a.sum}.max
    smallest = len if len < smallest
  end
  puts smallest
end

10秒で時間オーバー。
他の人の回答を見る。

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  memo = Array.new(m + 1) {[]}
  
  shelf = ->(h, from) {
    return 0 if from >= n
    return memo[h][from] if memo[h][from]
    
    if h == 1
      width = books[from...n].sum
      return memo[h][from] = width
    end
    
    narrowest = Limit
    width = 0
    to = n - h + 1
    
    (from..to).each do |i|
       width1 = shelf.(h - 1, i)
       wider = [width, width1].max
       narrowest = wider if narrowest > wider
       
       width += books[i]
       break if narrowest <= width
    end
    memo[h][from] = narrowest
  }
  
  puts shelf.(m, 0)
end

0.06秒ですよ。すごいなあ。
いやこれ、2分探索の典型的な問題なのだった。

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  
  f = ->(width) {
    need = 1
    sum = 0
    books.each do |book|
      return false if book > width
      sum += book
      if sum > width
        need += 1
        sum = book
      end
    end
    need <= m    
  }
  
  l = 1
  r = Limit
  
  while l <= r
    mid = l + (r - l) / 2
    if !f.(mid)
      l = mid + 1
    else
      r = mid - 1
    end
  end
  puts l
end

0.04秒で正解なのだが、バグって死んだ。「まめめも」参照。2分探索超むづかしい。
Ruby の組み込みメソッドを使ってみた。

Limit = 1500000

until (given = $<.gets.split.map(&:to_i)) == [0, 0]
  m, n = given
  books = n.times.map {$<.gets.to_i}
  
  f = ->(width) {
    need = 1
    sum = 0
    books.each do |book|
      return false if book > width
      sum += book
      if sum > width
        need += 1
        sum = book
      end
    end
    need <= m    
  }
  puts (1..Limit).bsearch {|width| f.(width)}
end

0183 Black-and-White

loop do
  board = Array.new(3)
  break if (board[0] = $<.gets.chomp) == "0"
  board[1] = $<.gets.chomp
  board[2] = $<.gets.chomp
  
  check = ->(c) {
    gl = c * 3
    return true if board.map {|b| b == gl}.any?
    return true if 3.times.map {|i| board.map {|b| b[i]}.join == gl }.any?
    return true if board[0][0] + board[1][1] + board[2][2] == gl 
    return true if board[0][2] + board[1][1] + board[2][0] == gl
    false
  }
  str = case
        when check.("b") then "b"
        when check.("w") then "w"
        else "NA"
        end
  puts str
end

0184 Tsuruga Castle

table = 6.times.map {|i| [i * 10, (i + 1) * 10 - 1]} + [[60, 120]]

until (n = $<.gets.to_i).zero?
  count = Array.new(7, 0)
  n.times.map {$<.gets.to_i}.each do |age|
    idx = table.index {|a, b| age.between?(a, b)}
    count[idx] += 1
  end
  puts count
end

0185 Goldbach's Conjecture II

N = 1000000

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?}

def 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?
  i, step = 5, 2
  guard = Math.sqrt(n).to_i
  while i <= guard
    return false if (n % i).zero?
    i += step
    step = 6 - step
  end
  true
end

until (n = $<.gets.to_i).zero?
  co = 0
  i = 0
  loop do
    a = sieve[i]
    break if a > n / 2
    co += 1 if prime?(n - a)
    i += 1
  end
  puts co
end

1.49秒かかった。標準添付ライブラリの Prime クラスを使うより高速な素数判定をしている。
さらに高速に。うまくエラトステネスの篩を使えばもっと速い。

N = 1000000

sieve = Array.new(N + 1, 0)
2.upto(Math.sqrt(N).to_i) do |i|
  next if sieve[i].nonzero?
  2.upto(N / i) {|j| sieve[i * j] = 1}
end

num = (2..N).select {|i| sieve[i].zero?}

until (n = $<.gets.to_i).zero?
  co = 0
  num.each do |a|
    b = n - a
    break if a > b
    co += 1 if sieve[b].zero?
  end
  puts co
end

これで 0.26秒。
　

0186 Aizu Chicken

until (given = $<.gets.split.map(&:to_i)) == [0]
  q1, b, c1, c2, q2 = given
  limit = [q2, b / c1].min
  str = "NA"
  limit.downto(1) do |aizu|
     tori = (b - aizu * c1) / c2
     if tori >= 0 and aizu + tori >= q1
       str = "#{aizu} #{tori}"
       break
     end
  end
  puts str
end

これ、簡単そうなのにわからなかった。ここを参考にした。
　

0187 Stoning Fortune

require 'matrix'

def cross(x1, y1, x2, y2, x3, y3, x4, y4)
  a = Matrix[[x2 - x1, x3 - x4], [y2 - y1, y3 - y4]].lup.solve([x3 - x1, y3 - y1]) rescue nil
  return false unless a
  s, t = a[0], a[1]
  f = ((0 <= s and s <= 1) and (0 <= t and t <= 1))
  f ? Vector[x1 + s * (x2 - x1), y1 + s * (y2 - y1)] : false
end

until (given = $<.gets.split.map(&:to_i)) == [0] * 4
  x, y = [], []
  x[0], y[0], x[1], y[1] = given
  x[2], y[2], x[3], y[3] = $<.gets.split.map(&:to_i)
  x[4], y[4], x[5], y[5] = $<.gets.split.map(&:to_i)
  p1 = cross(x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]) 
  p2 = cross(x[2], y[2], x[3], y[3], x[4], y[4], x[5], y[5]) 
  p3 = cross(x[4], y[4], x[5], y[5], x[0], y[0], x[1], y[1])
  str = "kyo"
  if p1 and p2 and p3
    v1 = p2 - p1
    v2 = p3 - p1
    s = Rational((v1[0] * v2[1] - v1[1] * v2[0]).abs, 2)
    if s.nonzero?
      idx = nil
      [Float::INFINITY, 1_900_000, 1_000_000, 100_000, 0].each_cons(2).with_index do |a, i|
        idx = i if a[1] <= s and s < a[0]
      end
      str = %w(dai-kichi chu-kichi kichi syo-kichi)[idx]
    end
  end
  puts str
end

つまらぬバグを取るのが大変だった。f = true and false は false なのだけれど、f = true になるのか。
　

0188 Search

until (n = $<.gets.to_i).zero?
  a = n.times.map {$<.gets.to_i}
  k = $<.gets.to_i
  co = 0
  
  f = ->(from, to) {
    return co if from > to
    mid = (from + to) / 2
    co += 1
    return co if a[mid] == k
    (a[mid] < k) ? f.(mid + 1, to) : f.(from, mid - 1)
  }
  puts f.(0, n - 1)
end

2分探索はどうもよくわからない。
　

0189 Convenient Location

until (n = $<.gets.to_i).zero?
  e = n.times.map {$<.gets.split.map(&:to_i)}
  edges = (e.map {|a, b, c| [[a, b], c]} + e.map {|a, b, c| [[b, a], c]}).to_h
  h = Hash.new([])
  edges.keys.each {|a, b| h[a] += [b]}
  
  try = ->(start) {
    shortest = Hash.new(Float::INFINITY)
    done = h.keys.map {|k| [k, false]}.to_h
    shortest[start] = 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] + edges[[u, v]]) < shortest[v]
          shortest[v] = a
        end
      end
    end
    
    shortest.values.sum
  }
  puts h.keys.map {|k| [try.(k), k]}.sort.first.reverse.join(" ")
end

ダイクストラ法。