AOJ（問題集）24

0230 Ninja Climbing

WA。いいと思うんだけれどなあ。

KABE = 0
HASHIGO = 1
SUBERU = 2

loop do
  n = gets.to_i
  break if n.zero?
  bils = Array.new(2) { gets.split.map(&:to_i) }
  
  bil_ck_init = Array.new(n)    #trueだと到達済み
  
  #aがいま居るビル、bが反対側のビル（0 or 1）。nowは階数、coはジャンプした回数
  try = ->(a, b, now, a_bil_ck, b_bil_ck, co) {
    return nil if a_bil_ck[now]
    a_bil_ck[now] = true
    return co if now >= n - 1 && bils[a][now] != SUBERU
    
    jump = ->{
      f1 = try.(b, a, now + 2, b_bil_ck, a_bil_ck, co + 1) if now + 2 < n
      f2 = try.(b, a, now + 1, b_bil_ck, a_bil_ck, co + 1) if now + 1 < n
      f3 = try.(b, a, now, b_bil_ck, a_bil_ck, co + 1)
      if f1 || f2 || f3
        [f1, f2, f3].compact.min
      else
        nil
      end
    }
    
    case bils[a][now]
    when KABE
      jump.()
    when HASHIGO
      if bils[a][now + 1] != HASHIGO
        jump.()
      else
        try.(a, b, now + 1, a_bil_ck, b_bil_ck, co)
      end
    when SUBERU
      try.(a, b, now - 1, a_bil_ck, b_bil_ck, co)
    else
      raise "Error"
    end
  }
  
  n1 = try.(0, 1, 0, bil_ck_init.dup, bil_ck_init.dup, 0)
  n2 = try.(1, 0, 0, bil_ck_init.dup, bil_ck_init.dup, 0)
  
  puts n1 || n2 ? [n1, n2].compact.min : "NA"
end

再帰版もWA。

KABE = 0
HASHIGO = 1
SUBERU = 2

loop do
  n = gets.to_i
  break if n.zero?
  bils = Array.new(2) { gets.split.map(&:to_i) }
  
  bil_ck_init = Array.new(n)
  stack = [[0, 0, bil_ck_init.dup, bil_ck_init.dup, 0],
           [1, 0, bil_ck_init.dup, bil_ck_init.dup, 0]]
  result = Float::INFINITY
           
  while (tmp = stack.pop)
    bil, now, a_bil_ck, b_bil_ck, co = tmp
    
    loop do
      break if a_bil_ck[now]
      a_bil_ck[now] = true
      if now >= n - 1 && bils[bil][now] != SUBERU
        result = [result, co].min
        break
      end
      
      jump = ->{
        stack << [1 - bil, now + 2, b_bil_ck, a_bil_ck, co + 1] if now + 2 < n
        stack << [1 - bil, now + 1, b_bil_ck, a_bil_ck, co + 1] if now + 1 < n
        stack << [1 - bil, now, b_bil_ck, a_bil_ck, co + 1]
      }
      
      case bils[bil][now]
      when KABE
        jump.()
        break
      when HASHIGO
        if bils[bil][now + 1] != HASHIGO
          jump.()
          break
        else
          now += 1
        end
      when SUBERU
        now -= 1
      else
        raise "Error"
      end
    end
  end
  
  result = "NA" if result == Float::INFINITY
  puts result
end

0231 Dangerous Bridge

loop do
  n = gets.to_i
  break if n.zero?
  persons = Array.new(n) { gets.split.map(&:to_i) }
  
  dp = Hash.new(0)
  persons.each do |m, a, b|
    dp[a] += m
    dp[b] -= m
  end
  weight = 0
  result = "OK"
  dp.sort.each do |t, w|
    weight += w
    if weight > 150
      result = "NG"
      break
    end
  end
  puts result
end

0232 Life Game

素朴なDFS。TLE。

loop do
  x, y, z = gets.split.map(&:to_i)
  break if x + y + z == 0
  vs = gets.split.map(&:to_i)
  nea = Array.new(z) { gets.split.map(&:to_i) }
  
  events = Array.new(y + 1, 0)
  nea.each do |n, e, a|
    events[n] = case e
                when 1 then a * 1000
                when 2 then a
                when 3 then -a
                else raise "Error"
                end
  end
  
  q = [[0, 1.0, 0]]
  mean = 0
  while (now = q.pop)
    pos, p, money = now
    next if pos >= y
    
    e = events[pos]
    if e >= 1000
      q << [pos + e / 1000, p, money]
      next
    elsif e.nonzero?
      tmp = money + e
      money = [tmp, 0].max
      mean += p * e if money > 0
    end
    
    p /= x
    vs.each do |step|
      q << [pos + step, p, money]
    end
  end
  puts mean.to_i
end

0238 Time to Study

while true
  t = gets.to_i
  break if t.zero?
  n = gets.to_i
  sfs = Array.new(n) { gets.split.map(&:to_i) }
  
  dif = t - sfs.sum { |s, f| f - s }
  puts dif <= 0 ? "OK" : dif
end

0239 Calorie Counting

while true
  n = gets.to_i
  break if n.zero?
  sweets = Array.new(n) { gets.split.map(&:to_i) }
  limit = gets.split.map(&:to_i)
  
  result = sweets.select {|swt|
    cal = [4, 9, 4].zip(swt[1, 3]).inject(0) { |acc, (a, b)| acc + a * b }
    [*swt[1, 3], cal].zip(limit).all? { |a, b| a <= b }
  }
  puts result.empty? ? "NA" : result.map { |e| e[0] }
end

0240 Interest Rates

f1 = ->(y, r) { 1.0 + y * (r / 100.0) }
f2 = ->(y, r) { (1.0 + r / 100.0) ** y }

while true
  n = gets.to_i
  break if n.zero?
  y = gets.to_i
  banks = Array.new(n) { gets.split.map(&:to_i) }
  
  max = 0
  bank_num = nil
  
  banks.each do |b, r, t|
    gold = [f1, f2][t - 1].call(y, r)
    if max < gold
      max = gold
      bank_num = b
    end
  end
  puts bank_num
end

0241 Quaternion Multiplication

四元数の積を求める問題。実装は悩んだが、四元数をクラスにして、和と積を定義した。

class Q
  def initialize(r, i, j, k)
    @ary = [r, i, j, k]
  end
  attr_reader :ary
  
  def +(obj)
    Q.new(*ary.zip(obj.ary).map { |a, b| a + b })
  end
  
  def *(obj)
    x = ary.product(obj.ary).map { |a, b| a * b }
    e = x.each_slice(4).to_a
    ans = Array.new(4)
    ans[0] = Q.new(*e[0])
    ans[1] = Q.new(-e[1][1],e[1][0],-e[1][3],e[1][2])
    ans[2] = Q.new(-e[2][2],e[2][3],e[2][0],-e[2][1])
    ans[3] = Q.new(-e[3][3],-e[3][2],e[3][1],e[3][0])
    ans.inject(:+)
  end
end


while true
  n = gets.to_i
  break if n.zero?
  data_n = Array.new(n) { gets.split.map(&:to_i) }
  
  puts data_n.map {|data|
    a = Q.new(*data[0, 4])
    b = Q.new(*data[4, 4])
    (a * b).ary.join(" ")
  }
end

0242 Input Candidates

最初、問題の意図を読み違えていた。

while true
  n = gets.to_i
  break if n.zero?
  lines = Array.new(n) { gets.split }
  k0 = gets.chomp
  
  tally = Hash.new(0)
  lines.inject(:concat).each do |word|
    tally[word] += 1
  end
  result = tally.select { |k, v| k.start_with?(k0) }
    .sort_by { |k, v| [-v, k] }
    .take(5)
    .map { |e| e[0] }
    .join(" ")
  puts result.empty? ? "NA" : result
end

0243 Filling Game

頑張ったがTLE。Ruby では通過者なし。

def all?(field)
  tmp = field.join
  tmp[0..-2] == tmp[1..-1]
end

def copy(field)
  field.map { |row| row.dup }
end

def push_button(w, h, col0, field)
  checked = copy(field)
  q = [[0, 0]]
  while (po = q.shift)
    x, y = po
    checked[y][x] = "."
    col = field[y][x]
    field[y][x] = col0
    [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
      x1 = x + dx
      y1 = y + dy
      next if x1 < 0 || y1 < 0 || x1 >= w || y1 >= h
      next if checked[y1][x1] == "."
      q << [x1, y1] if  field[y1][x1] == col
    end
  end
end


while true
  x, y = gets.split.map(&:to_i)
  break if (x + y).zero?
  field0 = Array.new(y) { gets.split.join }
  
  if all?(field0)
    puts 0
    next
  end
  
  table = %w(R G B)
  q = []
  (table - [field0[0][0]]).each { |col| q << [col, 1, copy(field0)] }
  while (e = q.shift)
    col, n, field = e
    push_button(x, y, col, field)
    if all?(field)
      puts n
      break
    end
    (table - [field[0][0]]).each { |col| q << [col, n + 1, copy(field)] }
  end
end