Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Code Festival 2015 予選 B
# [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
# [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
# [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
# [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
Owner

whatalnk commented Nov 7, 2015

  • A
  • B
  • C
  • D
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment