Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing

Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

This theme

AtCoder Beginner Contest D - Powerful Discount Tickets Difficulty: 826

This theme, priority queue Ruby The operation itself is simple: take the most expensive item out of the queue, apply a discount voucher and put it back in the queue. In each case, perform the same operation for the most expensive item until the discount ticket runs out. However, in the implementation that simply sorts as follows, it will be TLE.

ruby_tle.rb

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
a.sort_by!{|x| -x}
m.times do
  b = a.shift
  b /= 2
  a << b
  a.sort_by!{|x| -x}  
end
puts a.inject(:+)

Priority queues allow you to find the most expensive items with less computation than sorting. It is heapq in Python and PriorityQueue in Java, but it is not in Ruby, so * I want to implement Priority Queue in Ruby * I borrowed the code from, and modified it a little.

ruby.rb

class PriorityQueue
  def initialize(array = [])
    @data = []
    array.each{|a| push(a)}
  end

  def push(element)
    @data.push(element)
    bottom_up
  end

  def pop
    if size == 0
      return nil
    elsif size == 1
      return @data.pop
    else
      min = @data[0]
      @data[0] = @data.pop
      top_down
      return min
    end
  end

  def size
    @data.size
  end

  private

  def swap(i, j)
    @data[i], @data[j] = @data[j], @data[i]
  end

  def parent_idx(target_idx)
    (target_idx - (target_idx.even? ? 2 : 1)) / 2
  end

  def bottom_up
    target_idx = size - 1
    return if target_idx == 0
    parent_idx = parent_idx(target_idx)
    while (@data[parent_idx] > @data[target_idx])
      swap(parent_idx, target_idx)
      target_idx = parent_idx
      break if target_idx == 0
      parent_idx = parent_idx(target_idx)
    end
  end

  def top_down
    target_idx = 0

    while (has_child?(target_idx))

      a = left_child_idx(target_idx)
      b = right_child_idx(target_idx)

      if @data[b].nil?
        c = a
      else
        c = @data[a] <= @data[b] ? a : b
      end

      if @data[target_idx] > @data[c]
        swap(target_idx, c)
        target_idx = c
      else
        return
      end
    end
  end

  # @param Integer
  # @return Integer
  def left_child_idx(idx)
    (idx * 2) + 1
  end

  # @param Integer
  # @return Integer
  def right_child_idx(idx)
    (idx * 2) + 2
  end

  # @param Integer
  # @return Boolent
  def has_child?(idx)
    ((idx * 2) + 1) < @data.size
  end
end

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
e = a.map{|x| -x}
b = PriorityQueue.new(e)
m.times do
  c = b.pop
  b.push(-(-c / 2))
end
ans = 0
while b.size > 0
  ans -= b.pop
end
puts ans

Even this is the last minute. Python

python.py

import heapq
import math

n, m = map(int, input().split())
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for _ in range(m):
    b = heapq.heappop(a)
    heapq.heappush(a, math.ceil(b / 2))
print(-1 * sum(a))

Python's heapq takes the minimum value, so you need to add a minus sign. Also, since negative division by // returns the value with the larger absolute value, ceil is used here. Java

java.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
        PriorityQueue<Long> A = new PriorityQueue<>(Collections.reverseOrder());
        for (int i=0; i<N; i++) {
            A.add(Long.parseLong(sc.next()));
        }
        sc.close();

        for (int i=0; i<M; i++) {
            long new_price = (long)A.poll()/2;
            A.add(new_price);
        }

        long sum = 0;
        for (long a : A) {
            sum += a;
        }
        System.out.println(sum);
    }
}

        PriorityQueue<Long> A = new PriorityQueue<>(Collections.reverseOrder());

Java supports the maximum value with reverseOrder ().

Summary

• Solved ABC 141 D
• Become familiar with Ruby
• Become familiar with Python
• Become familiar with Java

Referenced site

• I want to implement Priority Queue in Ruby *
• [Implementation of [ruby] Priority Queue *