# Introduction

AtCoder's past problem environment has been upgraded.

# This theme

AtCoder Beginner Contest D - Integer Cards Difficulty: 891

This theme, hash

From the problem, it is a priority queue, but it seems that the constraint is loose and it can be solved by sorting.

# Solution 1 hash (2.7.1)

#### `ruby.rb`

``````
n, m = gets.split.map(&:to_i)
h = gets.split.map(&:to_i).tally
m.times do
b, c = gets.split.map(&:to_i)
if h.key?(c)
h[c] += b
else
h[c] = b
end
end
ans = 0
cnt = 0
h.sort{_2 <=> _1}.each do |k, v|
if cnt + v < n
ans += k * v
cnt += v
else
ans += k * (n - cnt)
break
end
end
puts ans
``````

#### `tally.rb`

``````
h = gets.split.map(&:to_i).tally
``````

The hash is generated from the array with `tally`.

#### `numberedparameter.rb`

``````
h.sort{_2 <=> _1}.each do |k, v|       # after 2.7.1

h.sort{|a, b| b <=> a}.each do |k, v|  # before
``````

You can specify the parameters in the block by number. The description method of `sort_by` is unknown.

# Solution 2 hash

#### `ruby.rb`

``````
n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.each do |x|
h[x] += 1
end
m.times do
b, c = gets.split.map(&:to_i)
h[c] += b
end
ans = 0
cnt = 0
h.sort_by{|k, v| -k}.each do |k, v|
if cnt + v < n
ans += k * v
cnt += v
else
ans += k * (n - cnt)
break
end
end
puts ans
``````

It is a writing style that can be passed even with `2.3.3`.

# Solution 3 array

#### `ruby.rb`

``````
n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
h = []
m.times do
h << gets.split.map(&:to_i)
end
i = 0
h.sort_by{|u, v| -v}.each do |x, y|
break if a[i] >= y
x.times do
a[i] = y
i += 1
break if i >= n
break if a[i] >= y
end
break if i >= n
end
puts a.inject(:+)
``````

I passed it around May. It seems that it is a little faster if you pass this this time.

2.3.3 2.7.1
Execution time(ms) 296 230

# Solution 4 Priority queue

#### `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

_, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = Array.new(m){gets.split.map(&:to_i)}
h = Heap.new(up: false)
a.each do |x|
h.push(x)
end
f = false
b.sort_by{|x, y| -y}.each do |x, y|
x.times do
u = h.pop
if y > u
h.push(y)
else
h.push(u)
f = true
end
break if f
end
break if f
end
puts h.sum
``````

Takes the minimum heap value, compares it, and returns it.

_1 _2 _3 _4
Code length(Byte) 342 342 319 1236
Execution time(ms) 822 288 296 773
memory(KB) 34416 39264 21776 20824

The numbered parameter seems to be useful.

# Summary

• Solved ABC 127 D
• Become familiar with Ruby

Referenced site

• [Understand with sample code! Major new features and changes in Ruby 2.7 Part 1 --numbered parameter (https://qiita.com/jnchito/items/79f0172e60f237e2c542) *