AtCoder ABC127 D hash to solve with Ruby 2.7.1

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

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

Referenced site

Recommended Posts

AtCoder ABC127 D hash to solve with Ruby 2.7.1
Solving with Ruby AtCoder ACL Beginner Contest C Union Find (DSU)
Solve with Ruby AtCoder ABC177 D UnionFind
AtCoder ABC127 D hash to solve with Ruby 2.7.1
[ruby] Double hash
Ruby setting 2
Ruby problem ⑦
Ruby learning 2
Ruby learning 6
Ruby settings 1
Ruby learning 1
AtCoder ABC127 D hash to solve with Ruby 2.7.1
AtCoder ARC 081 C hash to solve in Ruby, Perl and Java
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 1)
Sorting AtCoder ABC 111 C hashes to solve in Ruby, Perl and Java
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 2) Dynamic programming
AtCoder ABC127 D hash to solve with Ruby 2.7.1
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 1)
atcoder ABC115 C problem
AtCoder Beginner Contest 132 D Problem
AtCoder ABC127 D hash to solve with Ruby 2.7.1
ABC --129- A & B & C & D
ABC --122 --A & B & C & D
ABC --125- A & B & C & D
ABC --130- A & B & C & D
ABC --126 --A & B & C & D
Solving with Ruby, Perl and Java AtCoder ABC 136 D Breadth-first search
ABC --131- A & B & C & D & E
AtCoder Beginner Contest 167 C Problem (Java)
Learning Ruby with AtCoder 11 How to receive frequently used standard input
[Ruby] How to retrieve the contents of a double hash
Ruby setting 2
Ruby problem ⑦
Ruby learning 2
Ruby learning 6
Ruby settings 1
Ruby learning 1
AtCoder ABC127 D hash to solve with Ruby 2.7.1
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 2) Dynamic programming
Convert JSON to TSV and TSV to JSON with Ruby
[Ruby] Hash retrieval
[ruby] Double hash
[Ruby] Notes on gets method
java notes
Ruby setting 2
Ruby problem ⑦
Ruby learning 2
Ruby learning 6
synchronized notes
Ruby settings 1
Ruby learning 1
AtCoder ABC127 D hash to solve with Ruby 2.7.1