AOJ(問題集)10

AIZU ONLINE JUDGE: Programming Challenge
 

0091 Blur

L = 10
table = [[[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2], [-1, 2], [-2, 2], [1, 2],
  [2, 2], [0, 3], [-1, 3], [1, 3], [0, 4]],
  [[0, 0], [1, 0], [2, 0], [0, 1], [1, 1], [2, 1], [0, 2], [1, 2], [2, 2]],
  [[0, 0], [0, 1], [-1, 1], [1, 1], [0, 2]]]

n = $<.gets.to_i
cloth = $<.readlines.map {|l| l.split.map(&:to_i)}

copy = ->(ary) { ary.map {|l| l.dup} }
form = ->(x, y, i) {
  case (j = 3 - i)
  when 1 then "#{x} #{y + 1} #{j}"
  when 2 then "#{x + 1} #{y + 1} #{j}"
  when 3 then "#{x} #{y + 2} #{j}"
  else nil
  end
}

try = ->(place, field, co, order = []) {
  # にじみがあるまでスキップ
  x = y = nil
  loop do
    return false if place >= L * L
    x, y = place % L, place / L
    break if field[y][x].nonzero?
    place += 1
  end
  
  result = false
  # 大、中、小の滴を順に試す
  table.each_with_index do |drip, i|
    tmp = copy.(field)
    
    catch(:jump) do
      # 滴を試す(適合しなければ大域脱出で次の滴へ)
      drip.each do |po|
        x1, y1 = x + po[0], y + po[1]
        throw(:jump) if x1 < 0 or x1 >= L or y1 >= L or tmp[y1][x1].zero?
        tmp[y1][x1] -= 1
      end
      
      # 滴が適合した場合の処理
      co -= 1
      prc = form.(x, y, i)
      if co.zero?
        if tmp.flatten.map(&:zero?).all?
          return order + [prc]    #解が発見された場合(一気にリターン)
        else
          co += 1
          throw(:jump)
        end
      end
      
      result = try.(place, tmp, co, order + [prc])
      return result if result
      co += 1
    end
    
  end
  result
}
puts try.(0, cloth, n)

よくこんなのできたな。いまのところ Ruby で解けたのは 5人だけで、タイムは自分が最速。うれしい。
 

0092 Square Searching

until (n = $<.gets.to_i).zero?
  field = Array.new(n) {$<.gets.chomp}
  max = 0
  
  check = ->(x, y, num) {
    num.times do |i|
      num.times do |j|
        return false if x + j >= n or y + i >= n
        return false if field[y + i][x + j] == "*"
      end
    end
    true
  }
  
  (0...n * n).each do |i|
    x, y = i % n, i / n
    (max + 1..n - x).each do |width|
      max = width if check.(x, y, width)
    end
  end
  puts max
end

これだと時間オーバー。ちょっと素朴すぎるか。
高速化に挑戦。チェックをビット演算に切り替える。

until (n = $<.gets.to_i).zero?
  field = Array.new(n) {$<.gets.chomp}
  field.map! {|st| eval("0b" + st.gsub(/\./, "0").gsub(/\*/, "1"))}
  max = 0
  
  n.times do |y|
    l = field[y]
    break unless n - y > max
    (n - y).times do |i|
      l |= field[y + i]
      if l.to_s(2).rjust(n, "0").include?("0" * (i + 1))
        max = i + 1 if i + 1 > max
      end
    end
  end
  puts max
end

いちおう通ったけれども、3.91秒もかかってしまった。判定時にわざわざ文字列に直しているのがよくないのだけれど。
判定時に文字列を使わないバージョンも作ってみたのだが、余計に遅くなってしまった。正解者の結果を見ると 3.91秒というのは真ん中くらいで、そんなに悪い数字ではなかったようだ。Ruby だとしようがないのね。
 

0093 Leap Year

stack = []
until (years = $<.gets.split.map(&:to_i)) == [0, 0]
  is_uruu = ->(year) {
    (year % 4).zero? and ((year % 100).nonzero? or (year % 400).zero?)
  }
  result = (years.first..years.last).map {|i| is_uruu.(i) ? i : nil}.compact
  result << "NA" if result.empty?
  stack << result.join("\n") 
end
print stack.join("\n\n") + "\n"

 

0094 Calculation of Area

a, b = $<.gets.split.map(&:to_i)
printf "%.5f\n", a * b / 3.305785

 

0095 Surf Smelt Fishing Contest

$<.gets
data = $<.readlines.map {|l| l.split.map(&:to_i)}.sort_by(&:last)
max = data.last.last
num = data.select {|a| a.last == max}.sort_by(&:first).first.first
puts "#{num} #{max}"

sort_bysort と書くタイポがあって、なかなか気づけなかった。
 

0096 Sum of 4 Integers II

L = 1000
@memo = {}

def doit(s, n = 1)
  return (s <= L) ? 1 : 0 if n == 4
  key = [s, n]
  return @memo[key] if @memo.has_key?(key)
  co = 0
  a = (s <= L) ? s : L
  (0..a).each do |i|
    co += doit(s - i, n + 1)
  end
  @memo[key] = co
end

$<.readlines.map(&:to_i).each do |s|
  puts doit(s)
end

これだと時間オーバー。メモ化はしているのだけれど、もっと工夫しないといけない。

L = 1000
memo = {}

f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6}
f2 = ->(n) {(n ** 2 + 3 * n + 2) / 2}
f3 = ->(n) {n + 1}

f = ->(s, n) {
  case n
  when 1 then f1.(s)
  when 2 then f2.(s)
  when 3 then f3.(s)
  when 4 then 1
  else nil
  end
}

doit = ->(s, n = 1) {
  co = 0
  return f.(s, n) if s <= L
  return 0 if n == 4
  
  key = [s, n]
  return memo[key] if memo.has_key?(key)
  
  (0..L).each do |i|
    co += doit.(s - i, n + 1)
  end
  memo[key] = co
}

$<.readlines.map(&:to_i).each do |s|
  puts doit.(s)
end

これも時間オーバーだが、正しい答えを出すようだ。これがひな型になる。

f1 = ->(n) {(n ** 3 + 6 * n ** 2 + 11 * n + 6) / 6}
f2 = ->(n) {
  n1 = n - 1000
  (335337002 + 1004001 * n1 + 998 * n1 ** 2 - n1 ** 3) / 2
}
f3 = ->(n) {
  n1 = n - 2001
  (1337336000 - 4002 * n1 - 1999 * n1 ** 2 + n1 ** 3) / 2
}
f4 = ->(n) {
  n1 = n - 3002
  (999999000 - 2999999 * n1 + 3000 * n1 ** 2 - n1 ** 3) / 6
}

$<.readlines.map(&:to_i).each do |s|
  result = case s
           when    0..1000 then f1.(s)
           when 1001..2001 then f2.(s)
           when 2002..3002 then f3.(s)
           when 3003..4000 then f4.(s)
           end
  puts result
end

ほとんどインチキ。瞬殺である。WolframAlpha に助けを借りたのはナイショ。
他の人の回答。

MAX_SUM = 4000
MAX_I = 1000
K = 4
 
$sn_cache = Array.new(K + 1) {[]}
 
def check_sum(k, n)
  unless $sn_cache[k][n]
    count = 0
    max_i = [MAX_I, n].min
 
    (0..max_i).each do |i|
      count += check_sum(k - 1, n - i)
    end
 
    $sn_cache[k][n] = count
  end
  
  $sn_cache[k][n]
end
 
$sn_cache[1] = Array.new(MAX_I + 1, 1) + Array.new(MAX_SUM - MAX_I, 0)
 
while (line = gets)
  n = line.chomp.to_i
  puts check_sum(K, n)
end

これで 0.81秒なのだが、自分の最初の答えとよく似ている。しかし、自分のだと 6.51秒で時間オーバー。どこがちがうのだろう。
わかった、メモ化の際の配列の作り方がちがっているのだ。ハッシュを多重配列に直す。

L = 1000
@memo = Array.new(3) {[]}

def doit(s, n = 1)
  return (s <= L) ? 1 : 0 if n == 4
  return @memo[n - 1][s] if @memo[n - 1][s]
  co = 0
  a = (s <= L) ? s : L
  (0..a).each do |i|
    co += doit(s - i, n + 1)
  end
  @memo[n - 1][s] = co
end

$<.readlines.map(&:to_i).each do |s|
  puts doit(s)
end

これだけのことで 0.83秒で解けた。うーん、めっちゃ勉強になるなあ。
この最後のコードがいちばん好きだな。
なお、メモ化をハッシュにして、キーを key = "#{s},#{n}" という感じにしてやってもまあまあいけて、2.25秒で出来た。しかし、数字でいける場合はやはり配列が速いのは当り前か。
 

0097 Sum of Integers II

L = 100
@memo = Array.new(9) {Array.new(101) {[]}}

def solve(num, start, sum)
  return 0 if sum < 0 or start > L
  return (start <= sum and sum <= L) ? 1 : 0 if num == 1
  a = @memo[num - 1][start][sum]
  return a if a
  
  co = 0
  lim = [L, (2 * sum - num ** 2 + num) / (2 * num)].min
  (start..lim).each do |i|
    co += solve(num - 1, i + 1, sum - i)
  end
  @memo[num - 1][start][sum] = co
end
  
until (a = $<.gets.split.map(&:to_i)) == [0, 0]
  puts solve(a.first, 0, a.last)
end

1.11秒かかった。lim を求めるのは少し凝ってみた。lim = [L, sum].min とやるより少し効率がよい。
 

0098 Maximum Sum Sequence II

matrix = Array.new(n = $<.gets.to_i) {$<.gets.split.map(&:to_i)}
max = -Float::INFINITY
memo = {}

try = ->(x, y, w, h) {
  return 0 if x >= n or y >= n or w <= 0 or h <= 0
  key = "#{x},#{y},#{w},#{h}"
  return memo[key] if memo[key]
  
  if h == 1 and w == 1
    num = matrix[y][x]
  else
    try.(x, y + 1, w, h - 1)
    try.(x, y    , w, h - 1)
    try.(x + 1, y, w - 1, h)
    try.(x    , y, w - 1, h)
    num = try.(x, y, 1, 1) + try.(x + 1, y, w - 1, 1) +
          try.(x, y + 1, 1, h - 1) + try.(x + 1, y + 1, w - 1, h - 1)
  end
  max = num if num > max
  memo[key] = num
}

try.(0, 0, n, n)
puts max

メモ化しても時間オーバー。
他の人の回答(参照)を見る。コードは自分の好みに改変してあります。

n = $<.gets.to_i
matrix = (1..n).map { $<.gets.split.map(&:to_i) }
# 各行の数字を左から加算していった配列
accum = matrix.map {|row| row.inject([0]) {|s, x| s + [s[-1] + x]} }
 
max = 0 
[*1..n].repeated_combination(2) do |i, j|
  sum = 0 
  (0..n - 1).each do |k|
    sum += accum[k][j] - accum[k][i - 1]
    max = sum if sum > max
    sum = 0 if sum < 0
  end
end
 
matrix.flatten!
puts matrix.any? {|x| x >= 0} ? max : matrix.max

瞬殺。うーん、すごい、これは思いつかなかった。でもあらかじめ数字を加算しておいた配列を作るのいうのは、確かに時々見る手法。
 

0099 Surf Smelt Fishing Contest II

Node = Struct.new(:key, :value, :left, :right)

class Tree
  def initialize
    @root = nil
  end
  
  def insert(key, value)
    unless @root
      @root = Node.new(key, value)
      return
    end
    node = @root
    while node
      if key < node.key
        if node.left
          node = node.left
        else
          node.left = Node.new(key, value)
          break
        end
      elsif key > node.key
        if node.right
          node = node.right
        else
          node.right = Node.new(key, value)
          break
        end
      else
        if block_given?
          node.value = yield(key, node.value, value)
        else
          node.value = value
        end
        break
      end
    end
  end
  
  def []=(key, value)
    insert(key, value)
  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 [](key)
    search(key)&.value
  end
  
  def delete(key)
    delete_min = ->(node) {
      return node.right unless node.left
      node.left = delete_min.(node.left)
      node
    }
    search_min = ->(node) {
      node = node.left while 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.value = min_node.value
            node.right = delete_min.(node.right)
          end
        elsif key < node.key
          node.left  = del.(node.left)
        else
          node.right = del.(node.right)
        end
      end
      node
    }
    
    @root = del.(@root)
  end
  
  def maximum
    search_max = ->(node) {
      node = node.right while node.right
      node
    }
    raise "error" unless @root
    node = search_max.(@root)
    raise "error" unless node
    node.key
  end
end

n, q = $<.gets.split.map(&:to_i)
entry = []
fish_num = Hash.new(0)
t = Tree.new

delete = ->(fish, member) {
  t[fish] -= [member]
  t.delete(fish) if t[fish].empty?
}

q.times do
  member, fs = $<.gets.split.map(&:to_i)
  tmp = fish_num[member]
  fish_num[member] += fs
  t.insert(fish_num[member], [member]) {|k, v1, v2| v1 + v2}
  if entry.include?(member)
    delete.(tmp, member)
  else
    entry << member
  end
  max_fish = t.maximum
  puts "#{t[max_fish].sort.first} #{max_fish}"
end

惜しい、22課題中21課題までいって時間オーバー(9秒99)。二分探索木を実装して頑張った。しかしこれではダメのようだから、平衡二分探索木を実装しないといけないのか。
いや、シンプルに考え直してみる。

fish = Hash.new(0)
max = 0
max_fishers = []
selected_fisher = nil

n, q = $<.gets.split.map(&:to_i)
q.times do
  a, v = $<.gets.split.map(&:to_i)
  fish[a] += v
  if v > 0
    if fish[a] > max
      max = fish[a]
      puts "#{a} #{max}"
      max_fishers = [a]
      selected_fisher = a
    elsif fish[a] == max
      max_fishers << a
      puts "#{selected_fisher = max_fishers.min} #{max}"
    else
      puts "#{selected_fisher} #{max}"
    end
  else
    if fish[a] - v == max
      if max_fishers.size == 1
        max = fish.values.max
        max_fishers = fish.keys.select {|k| fish[k] == max}
        puts "#{selected_fisher = max_fishers.min} #{max}"
      else
        max_fishers.delete(a)
        puts "#{selected_fisher = max_fishers.min} #{max}"
      end
    else
      puts "#{selected_fisher} #{max}"
    end
  end
end

これで 0.23秒で通った。なんと Ruby での通過者中最速だった。C と C++ 以外には負けないぜ!