# Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

# This theme

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

This theme, hash sorting Ruby Duplicate elements, it's a hash, isn't it? The solution is similar to the previous * AtCoder ABC 113 C in Ruby, Perl and 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
``````

In ABC113C, it was a * Perl * -like sort, but this time I tried a * Ruby * -like sort. 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 * hashes have a simple and fast image. 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);
}
}
``````

Sorting * Java * hashes is very difficult to implement. If you usually do * Java *, do you sort by class?

Ruby Perl Java
Code length 694 Byte 808 Byte 2646 Byte
Execution time 164 ms 131 ms 649 ms
memory 24808 KB 28616 KB 54320 KB

# Summary

• Solved ABC 111 C
• Become familiar with Ruby
• Become familiar with Perl
• Become familiar with Java
• Familiar with hash sorting

Referenced site