Ruby 2.7.1 で解く AtCoder ABC127 D ハッシュ

# はじめに
AtCoder の過去問題の環境がバージョンアップされました。
# 今回のお題
*[AtCoder Beginner Contest D - Integer Cards](https://atcoder.jp/contests/abc127/tasks/abc127_d)*
<font color="green">Difficulty: 891</font>

今回のテーマ、ハッシュ

問題からは優先度付きキューなのですが、制約が緩いようでソートでも解けます。
# 解法１　ハッシュ(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
```
`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
```
ブロック内のパラメータを番号で指定することができます。
`sort_by`の記述方法は不明です。
# 解法２　ハッシュ
```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
```
`2.3.3`でも通る書き方です。
# 解法３　配列
```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(:+)
```
5月頃に通したものです。
これを今回通しますと若干速くなっているようです。

||2.3.3|2.7.1|
|:--:|:--:|:--:|
|実行時間 (ms)|296|230|

# 解法４　優先度付きキュー
```ruby.rb
class Heap
  attr_reader :size
  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
```
ヒープの最小値を取り出して、比較して戻します。

||_1|_2|_3|_4|
|:--:|:--:|:--:|:--:|:--:|
|コード長 (Byte)|342|342|319|1236|
|実行時間 (ms)|822|288|296|773|
|メモリ (KB)|34416|39264|21776|20824|
番号指定パラメータ（numbered parameter）が便利そうです。
# まとめ
+ ABC 127 D を解いた
+ Ruby に詳しくなった

参照したサイト
*[サンプルコードでわかる！Ruby 2.7の主な新機能と変更点 Part 1 - 番号指定パラメータ（numbered parameter](https://qiita.com/jnchito/items/79f0172e60f237e2c542)*