Ruby と Perl と Java と Python で解く AtCoder ARC 086 C ハッシュのソート

はじめに

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

今回のお題

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

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

Ruby

重複したリストと言えば、ハッシュですよね。

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 にはハッシュの破壊的ソートは準備されていないのですが、そういう用途が少ないものと思われます。
追記
元のコードはハッシュをソートするものでしたが、コメントにてvalues側を配列として取り出しソートしてスライスして合計するアイデアをいただきました。

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]):

Pythonの場合、ハッシュではなく辞書型と呼ばれます。
また、defaultdictではなくCounterを使用されているプレイヤーが多いです。

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) {

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

Java の場合、リストに変換してソートしています。
追記
コメントよりコードを修正しました。

	Ruby	Python	Perl	Java
コード長	156 Byte	286 Byte	226 Byte	723 Byte
実行時間	187 ms	261 ms	214 ms	620 ms
メモリ	32880 KB	39352 KB	46668 KB	70772 KB

まとめ

• ARC 086 C を解いた
• Ruby に詳しくなった
• Python に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった

参照したサイト
Python sortのまとめ (リスト、辞書型、Series、DataFrame)