Code Festival 2015 予選 B

CodeFes20115-QualB-a-DoubleString.rb.rb

# [A: ダブル文字列/Double String - CODE FESTIVAL 2015 予選B | AtCoder](http://code-festival-2015-qualb.contest.atcoder.jp/tasks/codefestival_2015_qualB_a)
s = gets.chomp
puts s.split("").uniq.join("")*2

CodeFes20115-QualB-b-Grading.rb

# [B: 採点/Grading - CODE FESTIVAL 2015 予選B | AtCoder](http://code-festival-2015-qualb.contest.atcoder.jp/tasks/codefestival_2015_qualB_b)
n, m = gets.chomp.split(" ").map(&:to_i)
dic = Hash.new(0)
ans = false
gets.chomp.split(" ").map(&:to_i).each do |a|
  dic[a] += 1
  if dic[a] > n/2 then
    ans = a
  end
end
if ans then
  puts ans
else
  puts "?"
end

CodeFes20115-QualB-c-Hotel.rb

# [C: 旅館/Hotel - CODE FESTIVAL 2015 予選B | AtCoder](http://code-festival-2015-qualb.contest.atcoder.jp/tasks/codefestival_2015_qualB_c)
n, m = gets.chomp.split(" ").map(&:to_i)
d = n - m
flag = true
if d < 0 then
  puts "NO"
else
  rooms = gets.chomp.split(" ").map(&:to_i).sort
  groups = gets.chomp.split(" ").map(&:to_i).sort
  j = 0
  groups.each_with_index do |group, i|
    if rooms[j].nil? then
      puts "NO"
      flag = false
      break
    end
    if group > rooms[j] then
      j += 1
      redo
    end
    j += 1
    if i - j > d then
      puts "NO"
      flag = false
      break
    end
  end
  puts "YES" if flag
end

CodeFes20115-QualB-d-SquaresPiecesColoring.rb

# [D: マスと駒と色塗り/Squares, Pieces and Coloring - CODE FESTIVAL 2015 予選B | AtCoder](http://code-festival-2015-qualb.contest.atcoder.jp/tasks/codefestival_2015_qualB_d)
class PriorityQueue
  # [Implementing a Priority Queue in Ruby](http://www.brianstorti.com/implementing-a-priority-queue-in-ruby/)
  def initialize
    @elements = [nil]
  end
  def elements
    @elements
  end
  def <<(element)
    @elements << element
    bubble_up(@elements.size - 1)
    element
  end
  def bubble_up(index)
    parent_index = (index / 2)
    return if index <= 1
    return if @elements[parent_index] <= @elements[index]
    exchange(index, parent_index)
    bubble_up(parent_index)
  end
  def exchange(source, target)
    @elements[source], @elements[target] = @elements[target], @elements[source]
  end
  def pop
    exchange(1, @elements.size - 1)
    min = @elements.pop
    bubble_down(1)
    return min
  end
  def bubble_down(index)
    child_index = (index * 2)
    return if child_index > @elements.size - 1
    not_the_last_element = child_index < @elements.size - 1
    left_element = @elements[child_index]
    right_element = @elements[child_index + 1]
    child_index += 1 if not_the_last_element && right_element < left_element
    return if @elements[index] <= left_element
    exchange(index, child_index)
    bubble_down(child_index)
  end
  def first
    @elements[1]
  end
  def empty?
    return @elements.size == 1
  end
end

n = gets.chomp.to_i
s, c, ans = Array.new(n, 0), Array.new(n, 0), Array.new(n, 0)
ts = (0...n).to_a
ts.each do |i|
  s[i], c[i] = gets.chomp.split(" ").map(&:to_i)
end
ts = ts.sort_by{|i| s[i]}.reverse
pos = 0
pq = PriorityQueue.new
while not ts.empty? or not pq.empty?
  if pq.empty? then
    i = ts.pop
    pos = s[i]
    pq << i
  elsif ts.empty? then
      i = pq.pop
      pos += c[i]
      ans[i] = pos - 1
  else
    i1 = ts[-1]
    i2 = pq.first
    if s[i1] < pos + c[i2] then
      c[i2] -= s[i1] - pos
      pos = s[i1]
      ts.pop
      pq << i1
    else
      pq.pop
      pos += c[i2]
      ans[i2] = pos - 1
    end
  end
end
puts ans

• A
• B
• C
• D

CODE FESTIVAL 2015 予選B 解説