Solving in Ruby, Perl and Java AtCoder ABC 113 C Reference

Introduction

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

This theme

AtCoder Beginner Contest 113 C - ID Difficulty: 877

This theme, reference Ruby It's a problem that I solved before, * AtCoder Judge System Update Test Contest 202004 B * is a little difficult.

ruby.rb

n, m = gets.split.map(&:to_i)
p = []
m.times do |i|
  y = gets.split.map(&:to_i)
  p[i] = [i, y, ""]
end
p.sort! {|a, b| (a[1][0]<=>b[1][0]).nonzero? || (a[1][1]<=>b[1][1])}
pref = 0
cnt = 1
m.times do |i|
  if pref == p[i][1][0]
    cnt += 1
  else
    cnt = 1
    pref = p[i][1][0]
  end
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(cnt.to_s.rjust(6, "0"))
end
p.sort! {|a, b| a[0]<=>b[0]}
m.times do |i|
  puts p[i][2]
end

array.rb

  p[i] = [i, y, ""]
  # => [[0, [1, 32], ""], [1, [2, 63], ""], [2, [1, 12], ""]]
  p.sort! {|a, b| (a[1][0]<=>b[1][0]).nonzero? || (a[1][1]<=>b[1][1])}
  # => [[2, [1, 12], ""], [0, [1, 32], ""], [1, [2, 63], ""]]
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(cnt.to_s.rjust(6, "0"))
  # => [[2, [1, 12], "000001000001"], [0, [1, 32], "000001000002"], [1, [2, 63], "000002000001"]] 

If the inside of the array p comes to mind, then this level of problem is graduation.

Ruby (Hash version)

RubyHash.rb

n, m = gets.split.map(&:to_i)
p = []
h = Hash.new(0);
m.times do |i|
  y = gets.split.map(&:to_i)
  p[i] = [i, y, ""]
  h[y[0]] +=1
end
p.sort! {|a, b| b[1][1]<=>a[1][1]}
m.times do |i|
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(h[p[i][1][0]].to_s.rjust(6, "0"))
  h[p[i][1][0]] -= 1
end
p.sort! {|a, b| a[0]<=>b[0]}
m.times do |i|
  puts p[i][2]
end

We are solving using a hash instead of a count variable. It is a little faster because the code length is shorter and the sorting condition is one. ~~ The Java version is TLE, so I added it. ~~ Perl

perl.pl

chomp (my ($n, $m) = split / /, <STDIN>);
my @p;
for my $i (0..$m-1) {
  chomp (my @in = split / /, <STDIN>);
  $p[$i] = [$i, @in];
}
@p = sort {$$a[1]<=>$$b[1] || $$a[2]<=>$$b[2]} @p;
my ($pref, $cnt) = (0, 0);
for my $i (0..$m-1) {
  if ($pref == $p[$i][1]) {
    $cnt++;
  } else {
    $pref = $p[$i][1];
    $cnt = 1;
  }
  $p[$i][3] = sprintf("%06s", $p[$i][1]) . sprintf("%06s", $cnt);
}
@p = sort {$$a[0]<=>$$b[0]} @p;
print $$_[3], "\n" for @p;

This is also a multi-condition sort by applying * previous article *.

array.pl

[0, 1, 32], [1, 2, 63], [2, 1, 12]

However, the structure in the array is different from * Ruby *, and it is flat. Java

java.java

import java.io.PrintWriter;
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());
        Map<Integer, Integer> h = new HashMap<>();
        List<City> city = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int Pref = Integer.parseInt(sc.next());
            int Year = Integer.parseInt(sc.next());
            city.add(new City(i, Pref, Year));
            if (h.containsKey(Pref)) {
                h.put(Pref, h.get(Pref) + 1);
            } else {
                h.put(Pref, 1);
            }
        }
        sc.close();
        city.sort((o1, o2) -> Integer.compare(o2.Year, o1.Year));
        for (City c : city) {
            c.Num = h.get(c.Pref);
            h.put(c.Pref, h.get(c.Pref) - 1);
        }
        city.sort((o1, o2) -> Integer.compare(o1.ID, o2.ID));
        PrintWriter pw = new PrintWriter(System.out);
        for (City c : city) {
            pw.printf("%06d%06d\n", c.Pref, c.Num);
        }
        pw.flush();
    }

    static class City {
        int ID;
        int Pref;
        int Year;
        int Num;

        City(int ID, int Pref, int Year) {
            this.ID = ID;
            this.Pref = Pref;
            this.Year = Year;
            this.Num = 0;
        }
    }
}

• Java * -like ~~ structure ~~ class is used, but since it becomes difficult to implement multi-condition sorting, hash is used.

flush.java

import java.io.PrintWriter;

If you do not use PrintWriter, it will be TLE.

Summary

• Solved ABC 113 C
• Become familiar with Ruby
• Become familiar with Perl
• Become familiar with Java

Referenced site instance method String#rjust