Skip to content

Instantly share code, notes, and snippets.

Embed
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
@whatalnk

This comment has been minimized.

Copy link
Owner Author

commented Nov 7, 2015

  • A
  • B
  • C
  • D
@whatalnk

This comment has been minimized.

Copy link
Owner Author

commented Nov 7, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.