Qiita Teams that are logged in
You are not logged in to any team

Community
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@superrino130

# はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

# 今回のお題

AtCoder CODE FESTIVAL 2016 qual C B - K個のケーキ
Difficulty: 905

# Ruby 数学的解法

ruby.rb
``````k = gets.to_i
a = gets.split.map(&:to_i).max
puts [0, 2 * a - k - 1].max
``````

# Ruby Heap

ruby.rb
``````class Heap
def initialize(up: false)
@up = up
@heap = []
@size = 0
end
def sum
x = 0
@size.times do |i|
x += @heap[i]
end
x
end
def push(n)
n = -n if @up
i = @size
while i > 0
pid = (i - 1) / 2
break if n >= @heap[pid]
@heap[i] = @heap[pid]
i = pid
end
@heap[i] = n
@size += 1
end
def pop
return nil if @size == 0
top = @heap[0]
@size -= 1
n = @heap[@size]
i = 0
while i * 2 + 1 < @size
cid1 = i * 2 + 1
cid2 = cid1 + 1
if cid2 < @size && @heap[cid2] < @heap[cid1]
cid1 = cid2
end
break if @heap[cid1] >= n
@heap[i] = @heap[cid1]
i = cid1
end
@heap[i] = n
if @up
-top
else
top
end
end
end

gets
a = gets.split.map(&:to_i)
h = Heap.new(up: true)
a.each do |x|
h.push(x)
end
while h.size > 1
u = h.pop
v = h.pop
h.push(u - 1) if u - 1 > 0
h.push(v - 1) if v - 1 > 0
end
if h.size == 0
puts "0"
else
puts h.pop - 1
end
``````
up.rb
``````  def initialize(up: false)
@up = up
``````

heap.rb
``````while h.size > 1
u = h.pop
v = h.pop
h.push(u - 1) if u - 1 > 0
h.push(v - 1) if v - 1 > 0
end
``````

2つ取り出して減算した後、1以上であればキューに戻します。

# Python　数学的解法

python.py
``````from sys import stdin

def main():
k, _ = map(int, input().split())
a = max(map(int, input().split()))
print(max(0, 2 * a - k - 1))
main()
``````

# Python heapq

python.py
``````from sys import stdin

def main():
import heapq
input()
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
while len(a) > 1:
u = heapq.heappop(a)
v = heapq.heappop(a)
if u + 1 < 0:
heapq.heappush(a, u + 1)
if v + 1 < 0:
heapq.heappush(a, v + 1)
if len(a) == 0:
print(0)
else:
print(abs(a[0] + 1))
main()
``````

Ruby 数学的解法 Ruby Heap Python 数学的解法 Python heapq
コード長 (Byte) 76 1120 184 458

メモリ (KB) 1788 1788 2940 3064

# まとめ

• AtCoder CODE FESTIVAL 2016 qual C B を解いた
• Ruby に詳しくなった
• Python に詳しくなった

[競プロ用]優先度付きキュー(heapq)まとめ

0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away