Résolution avec Ruby, Perl, Java et Python AtCoder ARC 086 C Hash Sorting

introduction

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

Ce thème

AtCoder Regular Contest 086 C - Not so Diverse Difficulty: 431

Ce thème, une sorte de hachage Ruby En parlant de listes en double, c'est un hachage.

ruby.rb

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.each do |x|
  h[x] += 1
end
puts n - h.values.sort.reverse[0, k].inject(:+)

before.rb

h.sort_by{|key, v| -v}.each do |key, v|

after.rb

puts n - h.values.sort.reverse[0, k].inject(:+)

~~ * Ruby * ne fournit pas de tri destructif des hachages, mais il semble que ces utilisations soient peu nombreuses. ~~ ** Addenda ** Le code original était de trier les hachages, mais dans les commentaires, j'ai eu l'idée de prendre le côté des valeurs sous forme de tableau, de tri, de découpage et de sommation. Python

python.py

from collections import defaultdict

n, k = map(int, input().split())
a = list(map(int, input().split()))
h = defaultdict(int)
for x in a:
    h[x] += 1
ans = 0
i = 0
for key, v in sorted(h.items(), key=lambda x: -x[1]):
    i += 1
    if i > k:
        ans += v
print(ans)

sort.py

for key, v in sorted(h.items(), key=lambda x: -x[1]):

Pour * Python *, cela s'appelle un dictionnaire plutôt qu'un hachage. De plus, de nombreux joueurs utilisent «Counter» au lieu de «defaultdict». Perl

perl.pl

chomp (my ($n, $k) = split / /, <STDIN>);
chomp (my @a = split / /, <STDIN>);
my %h;
$h{$_}++ for @a;
my ($c, $ans) = (0, 0);
for my $v (sort {$b <=> $a} values %h) {
  $c++;
  $ans += $v if $c > $k;
}
print "$ans\n";

sort.pl

for my $v (sort {$b <=> $a} values %h) {

Le tri * Perl * est simple. Java

java.java

import java.util.*;
import java.util.stream.Collectors;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        HashMap<Integer, Integer> h = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sc.next());
            h.merge(a, 1, Integer::sum);
        }
        sc.close();
        List<Integer> s = new ArrayList<>(h.values());
        Collections.sort(s);
        int ans = 0;
        for (int i = s.size() - k - 1; i >= 0; i--) {
            ans += s.get(i);
        }
        System.out.println(ans);
    }
}

sort.java

        List<Integer> s = new ArrayList<>(h.values());
        Collections.sort(s);

Pour * Java *, il est converti en liste et trié. ** Addenda ** J'ai modifié le code à partir des commentaires.

Résumé

• ARC 086 C résolu
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java

Site référencé

• Résumé du tri Python (liste, type de dictionnaire, série, DataFrame) *