Tri par hachage AtCoder ABC 111 C résolu en Ruby, Perl et Java

introduction

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

Ce thème

AtCoder Beginner Contest 111 C - //// Difficulty: 822

Ce thème, une sorte de hachage Ruby Dupliquer des éléments, c'est un hachage, n'est-ce pas? La solution est similaire à la précédente * AtCoder ABC 113 C en Ruby, Perl et Java *.

ruby.rb

n = gets.to_i
v = gets.split.map(&:to_i)
p = Hash.new(0)
q = Hash.new(0)
n.times do |i|
  p[v[i]] += 1 if i.even?
  q[v[i]] += 1 if i.odd?
end
ps = Hash[p.sort_by{|k, v| -v}].keys
qs = Hash[q.sort_by{|k, v| -v}].keys
x, y, ans = 0, 0, n / 2
f = false
ps.size.times do |i|
  x = ps[i]
  qs.size.times do |j|
    if x != qs[j]
      y = qs[j]
      f = true
      break
    end
  end
  break if f
end
ans = n - p[x] - q[y] if f
x, y = 0, 0
f = false
qs.size.times do |i|
  x = qs[i]
  ps.size.times do |j|
    if x != ps[j]
      y = ps[j]
      f = true
      break
    end
  end
  break if f
end
ans = n - q[x] - p[y] if f && ans > n - q[x] - p[y]
puts ans

hash.rb

ps = Hash[p.sort_by{|k, v| -v}].keys

Dans ABC113C, c'était une sorte de * Perl *, mais cette fois j'ai essayé une sorte de * Ruby *. Perl

perl.pl

chomp (my $n = <STDIN>);
chomp (my @v = split / /, <STDIN>);
my (%p, %q);
for my $i (0..$n-1) {
  if ($i % 2 == 0) {
    $p{$v[$i]}++;
  } else {
    $q{$v[$i]}++;
  }
}
my @ps = sort {$p{$b}<=>$p{$a}} keys %p;
my @qs = sort {$q{$b}<=>$q{$a}} keys %q;
my ($x, $y) = (0, 0);
my $ans = $n / 2;
my $f = 0;
for my $i (0..$#ps) {
  $x = $ps[$i];
  for my $j (0..$#qs) {
    if ($x != $qs[$j]) {
      $y = $qs[$j];
      $f = 1;
      last;
    }
  }
  last if $f;
}
$ans = $n - $p{$x} - $q{$y} if $f;
($x, $y) = (0, 0);
my $f = 0;
for my $i (0..$#qs) {
  $x = $qs[$i];
  for my $j (0..$#ps) {
    if ($x != $ps[$j]) {
      $y = $ps[$j];
      $f = 1;
      last;
    }
  }
  last if $f;
}
$ans = $n - $q{$x} - $p{$y} if $f && $ans > $n - $q{$x} - $p{$y};
print "$ans\n";

hash.pl

my @ps = sort {$p{$b}<=>$p{$a}} keys %p;

Le hachage * Perl * a une image simple et rapide. 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());
        Map<Integer, Integer> p = new HashMap<>();
        Map<Integer, Integer> q = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int v = Integer.parseInt(sc.next());
            if (i % 2 == 0) {
                if (p.containsKey(v)) {
                    p.put(v, p.get(v) + 1);
                } else {
                    p.put(v, 1);
                }
            } else {
                if (q.containsKey(v)) {
                    q.put(v, q.get(v) + 1);
                } else {
                    q.put(v, 1);
                }
            }
        }
        sc.close();

        Map<Integer, Integer> ps = p.entrySet().stream()
                .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed()
                        .thenComparing(Map.Entry.comparingByKey()))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
        Map<Integer, Integer> qs = q.entrySet().stream()
                .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed()
                        .thenComparing(Map.Entry.comparingByKey()))
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

        List<Integer> pss = new ArrayList<>(ps.keySet());
        List<Integer> qss = new ArrayList<>(qs.keySet());
        int x = 0, y = 0, ans = n / 2;
        boolean f = false;
        for (int i = 0; i < pss.size(); i++) {
            x = pss.get(i);
            for (int j = 0; j < qss.size(); j++) {
                if (x != qss.get(j)) {
                    y = qss.get(j);
                    f = true;
                    break;
                }
            }
            if (f)
                break;

        }
        if (f)
            ans = n - p.get(x) - q.get(y);
        x = 0;
        y = 0;
        f = false;
        for (int i = 0; i < qss.size(); i++) {
            x = qss.get(i);
            for (int j = 0; j < pss.size(); j++) {
                if (x != pss.get(j)) {
                    y = pss.get(j);
                    f = true;
                    break;
                }
            }
            if (f)
                break;

        }
        if (f && ans > n - q.get(x) - p.get(y))
            ans = n - q.get(x) - p.get(y);
        System.out.println(ans);
    }
}

Le tri des hachages * Java * est très difficile à implémenter. Si vous utilisez habituellement * Java *, faites-vous un tri par classe?

Résumé

• Résolu ABC 111 C
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java
• Familier avec le tri par hachage

Site référencé

• Trier la carte à l'aide de l'API Stream *