Résolution avec Ruby, Perl et Java AtCoder ABC 113 C Reference

introduction

• Problèmes AtCoder * Utilise les recommandations pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder Beginner Contest 113 C - ID Difficulty: 877

Ce thème, référence Ruby C'est un problème qui a rendu * AtCoder Judge System Update Test Contest 202004 B * résolu avant * un peu plus difficile.

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

Si l'intérieur du tableau p vient à l'esprit, alors ce niveau de problème est la graduation.

Ruby (version Hash)

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

Je résolve en utilisant un hachage au lieu d'une variable de nombre. C'est un peu plus rapide car la longueur du code est plus courte et les conditions de tri sont une. ~~ La version Java est TLE, donc je l'ai ajoutée. ~~ 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;

Il s'agit également d'un tri à conditions multiples en appliquant * article précédent *.

array.pl

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

Cependant, la structure du tableau est différente de celle de * Ruby * et elle est plate. 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;
        }
    }
}

• La classe ~~ structure ~~ semblable à Java * est utilisée, mais comme il devient difficile d'implémenter le tri multi-conditions, le hachage est utilisé.

flush.java

import java.io.PrintWriter;

Si vous n'utilisez pas «PrintWriter», ce sera «TLE».

Résumé

• Résolu ABC 113 C
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java

Site référencé instance method String#rjust