AOJ（問題集）26

0272: The Lonely Girl's Lie

むずかしそうだったが、よく考えたら解けてうれしい。

while true
  n = gets.to_i
  break if n.zero?
  as = gets.split.map(&:to_i).sort
  bs = gets.split.map(&:to_i).sort
  
  try = ->{
    (1...n).each do |k|
      l = (k / 2r).ceil
      min1 = bs[n - l]
      min2 = as[n - k]
      return k if min1 < min2
    end
    "NA"
  }
  puts try.()
end

kの過半数をlとすると、相手のmax(l)の最小値min1よりも、こちらのmax(k)の最小値min2が大きければいい。ソートしておけば、実際には Array#max を使わなくて済む。
　

0273: Cats Going Straight II

これはまず、柱と壁から、部屋をデータ化しないといけない。あとはグラフの問題に帰着できそう。
　

0275: Railroad

ダイクストラ法？
　

0276: Temperature Difference

abs = Array.new(7) { gets.split.map(&:to_i) }
puts abs.map { |a, b| a - b }

0277: Ticket Sales

data = Array.new(4) { gets.split.map(&:to_i) }

table = [6000, 4000, 3000, 2000]
puts data.map { |t, n| table[t - 1] * n }

0278: Admission Fee

n = gets.to_i
days = Array.new(n) { gets.split.map(&:to_i) }

puts days.map {|x, y, b, p|
  fee1 = x * b + y * p
  fee2 = (x * [b, 5].max + y * [p, 2].max) * 4 / 5
  [fee1, fee2].min
}

0279: A Pair of Prizes

while true
  n = gets.to_i
  break if n.zero?
  capsule = gets.split.map(&:to_i)
  
  result = 
    if capsule.all? { |n| n <= 1 }
      "NA"
    else
      capsule.count { |n| n >= 1 } + 1
    end
  puts result
end

0280: The Outcome of Bonze

百人一首の「坊主めくり」。Playerクラスを作って、なかなかきれいに書けた。

class Player
  @@field = nil
  def self.clear
    @@field = 0
  end
  
  def self.field
    @@field
  end
  
  def initialize
    @num = 0
  end
  attr_reader :num
  
  def draw(card)
    case card
    when "M"
      @num += 1
    when "S"
      @@field += @num + 1
      @num = 0
    when "L"
      @num += @@field + 1
      @@field = 0
    else
      raise
    end
  end
end

while true
  n = gets.to_i
  break if n.zero?
  deck = gets.chomp
  
  Player.clear
  players = Array.new(n) { Player.new }
  player = players.cycle
  
  deck.each_char { |card| player.next.draw(card) }
  puts (players.map(&:num).sort + [Player.field]).join(" ")
end

0281: Formation

素朴なDFSで解いてみたが、当然のようにTLE。

q = gets.to_i
data = Array.new(q) { gets.split.map(&:to_i) }

table = [[2, 1, 0], [3, 0, 0], [1, 1, 1]]
puts data.map {|rest0|
  max = 0
  try = ->(rest, team=0) {
    max = [max, team].max
    3.times do |i|
      nxt = rest.zip(table[i]).map { |a, b| a - b }
      if nxt.all? { |e| e >= 0 }
        try.(nxt, team + 1)
      end
    end
  }
  try.(rest0)
  max
}

　
どうやら、CAN→CCA→CCC の順に詰めていけばいいらしい。そういやそうか。