Ruby と Perl と Java で解く AtCoder ABC 111 C ハッシュのソート

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

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

今回のテーマ、ハッシュのソート

Ruby

重複した要素、とくればハッシュですよね。
解法は前回の、Ruby と Perl と Java で解く AtCoder ABC 113 C に似た問題です。

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

ABC113C では Perl 風のソートでしたが、今回は 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;

Perl のハッシュは、シンプルかつ速いイメージがあります。

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);
    }
}

Java ハッシュのソートは、実装がすごく大変。普段 Java やっている方は、クラスでソートしているのでしょうか。

	Ruby	Perl	Java
コード長	694 Byte	808 Byte	2646 Byte
実行時間	164 ms	131 ms	649 ms
メモリ	24808 KB	28616 KB	54320 KB

まとめ

• ABC 111 C を解いた
• Ruby に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった
• ハッシュのソートに詳しくなった

参照したサイト
Stream API を使用して Map をソートする