Ruby と Perl と Java で解く AtCoder ARC 081 C ハッシュ

はじめに

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

今回のお題

AtCoder Regular Contest C - Make a Rectangle
Difficulty: 538

今回のテーマ、ハッシュ

Ruby

ruby.rb

n = gets.to_i
c = gets.split.map(&:to_i)
h = {}
n.times do |i|
  if h[c[i]]
    h[c[i]] += 1
  else
    h[c[i]] = 1
  end
end
s = h.select{|k, v| v >= 4}.keys.sort{|a, b| b<=>a}
t = h.select{|k, v| v >= 2}.keys.sort{|a, b| b<=>a}
ans = 0
ans = s[0] * s[0] if s.size > 0
ans = [ans, t[0] * t[1]].max if t.size > 1
puts ans

ハッシュを利用して、出現回数を調べます。
俺環 Ruby (2.7.1) では filter メソッドが使用可能なのですが、AtCoder の旧環境 Ruby (2.3.3) では RE になりますので、select メソッドを使用しています。

Perl

perl.pl

use v5.18; # strict say state
use warnings;
use List::Util qw(max);

chomp (my $n = <STDIN>);
chomp (my @a = split / /, <STDIN>);
my %h;
$h{$_}++ for @a;
my @s = sort {$b <=> $a} grep {$h{$_} >= 4} keys %h;
my @t = sort {$b <=> $a} grep {$h{$_} >= 2} keys %h;
my $ans = 0;
$ans = $s[0] * $s[0] if @s > 0;
$ans = max($ans, $t[0] * $t[1]) if @t > 1;
say $ans;

Perl の常套句を使用しています。

hash.pl

$h{$_}++ for @a;

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 a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        Map<Integer, Integer> h = new TreeMap<>(Comparator.reverseOrder());
        for (int i = 0; i < n; i++) {
            if (h.containsKey(a[i])) {
                h.put(a[i], h.get(a[i]) + 1);
            } else {
                h.put(a[i], 1);
            }
        }
        List<Integer> s = h.entrySet().stream()
                .filter(x -> x.getValue() >= 4)
                .map(x -> x.getKey())
                .collect(Collectors.toList());
        List<Integer> t = h.entrySet().stream()
                .filter(x -> x.getValue() >= 2)
                .map(x -> x.getKey())
                .collect(Collectors.toList());
        long ans = 0;
        if (s.size() > 0) {
            ans = (long) s.get(0) * s.get(0);
        }
        if (t.size() > 1) {
            ans = Math.max(ans, (long) t.get(0) * t.get(1));
        }
        System.out.println(ans);
    }
}

Java のラムダ式を使用しています。
TreeMap はハッシュですが、Comparator.reverseOrder() により Key を自動的に降順に並び替えることができます。
整数のオーバーフロー対策として long に変換する必要があります。

	Ruby	Perl	Java
コード長	336 Byte	370 Byte	1199 Byte
実行時間	140 ms	135 ms	664 ms
メモリ	14988 KB	28196 KB	48532 KB

まとめ

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

参照したサイト
サンプルコードでわかる！Ruby 2.6の主な新機能と変更点