Ruby と Perl と Java で解く AtCoder ABC 113 C リファレンス

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Beginner Contest 113 C - ID](https://atcoder.jp/contests/abc113/tasks/abc113_c)*
<font color="green">Difficulty: 877</font>

今回のテーマ、リファレンス
# Ruby
以前に解きました、*[Ruby で解く AtCoder Judge System Update Test Contest 202004 B](https://qiita.com/superrino130/items/e01284f926f45be5427b)* を少し難しくした様な問題です。

```ruby.rb
n, m = gets.split.map(&:to_i)
p = []
m.times do |i|
  y = gets.split.map(&:to_i)
  p[i] = [i, y, ""]
end
p.sort! {|a, b| (a[1][0]<=>b[1][0]).nonzero? || (a[1][1]<=>b[1][1])}
pref = 0
cnt = 1
m.times do |i|
  if pref == p[i][1][0]
    cnt += 1
  else
    cnt = 1
    pref = p[i][1][0]
  end
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(cnt.to_s.rjust(6, "0"))
end
p.sort! {|a, b| a[0]<=>b[0]}
m.times do |i|
  puts p[i][2]
end
```
```array.rb
  p[i] = [i, y, ""]
  # => [[0, [1, 32], ""], [1, [2, 63], ""], [2, [1, 12], ""]]
  p.sort! {|a, b| (a[1][0]<=>b[1][0]).nonzero? || (a[1][1]<=>b[1][1])}
  # => [[2, [1, 12], ""], [0, [1, 32], ""], [1, [2, 63], ""]]
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(cnt.to_s.rjust(6, "0"))
  # => [[2, [1, 12], "000001000001"], [0, [1, 32], "000001000002"], [1, [2, 63], "000002000001"]] 
```
配列 p の中が頭に浮かぶようであれば、このレベルの問題は卒業でしょう。
# Ruby (Hash版)
```RubyHash.rb
n, m = gets.split.map(&:to_i)
p = []
h = Hash.new(0);
m.times do |i|
  y = gets.split.map(&:to_i)
  p[i] = [i, y, ""]
  h[y[0]] +=1
end
p.sort! {|a, b| b[1][1]<=>a[1][1]}
m.times do |i|
  p[i][2] = p[i][1][0].to_s.rjust(6, "0").concat(h[p[i][1][0]].to_s.rjust(6, "0"))
  h[p[i][1][0]] -= 1
end
p.sort! {|a, b| a[0]<=>b[0]}
m.times do |i|
  puts p[i][2]
end
```
カウント変数の代わりにハッシュを使用して解いています。
コード長が短くなった事と、ソートの条件が一つになっていることが特徴で、若干速くなっています。
~~Java 版が`TLE`なので追加しました。~~
# Perl
```perl.pl
chomp (my ($n, $m) = split / /, <STDIN>);
my @p;
for my $i (0..$m-1) {
  chomp (my @in = split / /, <STDIN>);
  $p[$i] = [$i, @in];
}
@p = sort {$$a[1]<=>$$b[1] || $$a[2]<=>$$b[2]} @p;
my ($pref, $cnt) = (0, 0);
for my $i (0..$m-1) {
  if ($pref == $p[$i][1]) {
    $cnt++;
  } else {
    $pref = $p[$i][1];
    $cnt = 1;
  }
  $p[$i][3] = sprintf("%06s", $p[$i][1]) . sprintf("%06s", $cnt);
}
@p = sort {$$a[0]<=>$$b[0]} @p;
print $$_[3], "\n" for @p;
```
こちらも、*[前回記事](https://qiita.com/superrino130/items/de5b67a81cceaf8a7c10)*の応用で複数条件のソートになります。

```array.pl
[0, 1, 32], [1, 2, 63], [2, 1, 12]
```
但し、*Ruby* とは配列の中の構造が異なって、フラットになっています。
# Java
```java.java
import java.io.PrintWriter;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        Map<Integer, Integer> h = new HashMap<>();
        List<City> city = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int Pref = Integer.parseInt(sc.next());
            int Year = Integer.parseInt(sc.next());
            city.add(new City(i, Pref, Year));
            if (h.containsKey(Pref)) {
                h.put(Pref, h.get(Pref) + 1);
            } else {
                h.put(Pref, 1);
            }
        }
        sc.close();
        city.sort((o1, o2) -> Integer.compare(o2.Year, o1.Year));
        for (City c : city) {
            c.Num = h.get(c.Pref);
            h.put(c.Pref, h.get(c.Pref) - 1);
        }
        city.sort((o1, o2) -> Integer.compare(o1.ID, o2.ID));
        PrintWriter pw = new PrintWriter(System.out);
        for (City c : city) {
            pw.printf("%06d%06d\n", c.Pref, c.Num);
        }
        pw.flush();
    }

    static class City {
        int ID;
        int Pref;
        int Year;
        int Num;

        City(int ID, int Pref, int Year) {
            this.ID = ID;
            this.Pref = Pref;
            this.Year = Year;
            this.Num = 0;
        }
    }
}
```
*Java* らしく~~構造体~~クラスを利用していますが、複数条件のソートの実装が大変になりますので、ハッシュを使用しています。

```flush.java
import java.io.PrintWriter;
```
`PrintWriter`を使用しないと`TLE`になります。

||Ruby|Ruby(Hash)|Perl|Java|
|:--:|:--:|:--:|:--:|:--:|
|コード長|450 Byte|372 Byte|470 Byte|1444 Byte|
|実行時間|943 ms|880 ms|1079 ms|1615 ms|
|メモリ|27376 KB|33900 KB|45168 KB|107864 KB|
# まとめ
+ ABC 113 C を解いた
+ Ruby に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった

参照したサイト
*[instance method String#rjust](https://docs.ruby-lang.org/ja/latest/method/String/i/rjust.html)*